What is the time complexity of HashMap.containsValue() in java?
Solution 1
To answer the question in the title - as mentioned by others, containsValue
is O(n), because without the key it doesn't know where it is and the algorithm has to go over all the values stored in the map.
To answer the question in the body of your question - on how to solve it - just consider whether you really need a general map which can count how many instances have you seen of each number. I mean, the only time you'd care if there's more than one appearance of a number is when it's x/2, right? That smells like a corner case to me. Just add a test that checks for that corner case - something like embedding if (numberList[i] == requiredSum/2) half++
during your set-construction loop, and then if (requiredSum % 2 == 0 && half == 2) return true
after it (see other variation below).
Then you can just iterate over the set and for each item check whether requiredSum-item
also appears in the set.
To summarize (with early exits when possible):
Set<Integer> seen = new HashSet<Integer>();
boolean halfSeen = false;
for (int num : numberList) {
if (num == requiredSum/2 && requiredSum % 2 == 0) {
if (halfSeen) return true;
halfSeen = true;
} else {
seen.add(num);
}
}
for (int num : seen) {
if (seen.contains(requiredSum - num)) return true;
}
return false;
Solution 2
The HashMap essentially is a key-value store, which can access it's keys with a complexity of O(1). Checking a value, however, there's nothing the HashMap can do but check all values and see if they're equal to the one you're searching. Therefore, the complexity is O(n) with n being the number of elements in the HashMap.
On a different note: You are looking up primitive values (int) in a collection of its boxed type (Integer). This means each time you are invoking a method on the HashMap, Java needs to box you primitive values: http://docs.oracle.com/javase/1.5.0/docs/guide/language/autoboxing.html
Solution 3
HashMap.containsValue complexity is O(n). But n is not exactly the map size but rather hash table size because containsValue goes thru all table elements if even map size = 0. Suppose we created an empty map with initial capacity = 1024. containsValue will have to go thru 1024 elements hash table array:
public boolean containsValue(Object value) {
if (value == null)
return containsNullValue();
Entry[] tab = table;
for (int i = 0; i < tab.length ; i++)
for (Entry e = tab[i] ; e != null ; e = e.next)
if (value.equals(e.value))
return true;
return false;
}
Vishnu Vedula
Updated on July 31, 2021Comments
-
Vishnu Vedula almost 3 years
I was given a problem to solve in
O(n)
time complexity :"Given a list of numbers and number x. Find if there any 2 numbers in the list that add up to x?"
And this is my solution :
public class SumMatchResult { public static void main(String[] args){ int[] numberList = {6,1,8,7,4,6}; int requiredSum = 8; boolean isSumPresent = checkSumPresentHash(numberList,requiredSum); if(isSumPresent) { System.out.println("Numbers exist"); }else { System.out.println("Numbers donot exist"); } } private static boolean checkSumPresentHash(int[] numberList, int requiredSum) { Map<Integer, Integer> m = new HashMap<Integer,Integer>(); int count = 0; for(int i=0;i<numberList.length;i++){ m.put(i, numberList[i]); } for(int i=0;i<numberList.length;i++){ if(m.containsValue(requiredSum - numberList[i])){ count++; } } if(count>1){ return true; } return false; } }
I am using
HashMap.containsValue()
instead of using aHashSet.contains()
which surely has a complexity ofO(1)
because, I have to account for the scenario where my input might contain identical values. For example, in the above case, I can have a set of input values{3,6,4,4,7}
to be matched for thesum 8
, which should returntrue
.My above solution's time complexity depends on the complexity of
HashMap.containsValue()
method. Please shed some light on the time complexity ofcontainsValue()
method and suggest me if there is any better solution for the above problem in terms of time complexity. Thank you.