What is the time complexity of HashMap.containsValue() in java?

Question

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 a HashSet.contains() which surely has a complexity of O(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 the sum 8, which should return true.

My above solution's time complexity depends on the complexity of HashMap.containsValue() method. Please shed some light on the time complexity of containsValue() method and suggest me if there is any better solution for the above problem in terms of time complexity. Thank you.

Answer 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;

Answer 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

Answer 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;
}

Answer 4

There is no index that is tagged to any value in HashMap, so, to find a value using containsValue(), you have to go through all the values of the HashMap.

Be mindful that the complexity O(n) here is the number of values in the HashMap and not the keys/size with which we usually denote its complexity.