68

I need to know: What is the time complexity of HashMap.containsKey() in java?

OmG
  • 18,337
  • 10
  • 57
  • 90
Hossein
  • 40,161
  • 57
  • 141
  • 175

4 Answers4

77

From the API doc ofHashMap:

This implementation provides constant-time performance for the basic operations (get and put), assuming the hash function disperses the elements properly among the buckets.

Since containsKey() is just a get() that throws away the retrieved value, it's O(1) (assuming the hash function works properly, again).

Michael Borgwardt
  • 342,105
  • 78
  • 482
  • 720
  • this is what I thought before. But it is not correct. Take a look on Jigar Joshi's answer. Your answer is correct for `Hashtable` that does not allow null values. – AlexR Jan 19 '12 at 09:03
  • 1
    @AlexR: I think you are completely misunderstanding the code in Jigar's answer. It has absolutely nothing to do with null values, and the for loop only loops through the linked list of entries in a single bucket, which is O(1) if, as stated twice in my answer, the hash function does its job. – Michael Borgwardt Jan 19 '12 at 09:18
  • @Tom Hawtin - tackline: I don't think that's a case most people need to worry about (no, that doesn't include people who write servlet containers). – Michael Borgwardt Jan 19 '12 at 09:33
  • 1
    @TomHawtin-tackline, it's a little weird there is no popular hash Map impl. that uses a tree for the collisions. So it's O(logN) in the worst case and O(1) otherwise. – bestsss Feb 04 '12 at 17:27
  • 2
    @bestsss Yeah. It's the obvious data structure, but does require the key type support both hash and ordering interfaces, and do it consistently. Also, the constants factors in performance are also important in real life. For well behaved situations, collisions will become slower. Still, it's a map implementation I'd like to see in java.util. – Tom Hawtin - tackline Feb 04 '12 at 20:58
  • @TomHawtin-tackline, pluggable comparator can take of the ordering. But collision dont need to be slower, say tree is employed only after 4+ collisions and it can be different type (subclass) of Entry when built on tree. – bestsss Feb 04 '12 at 22:08
  • Why are we talking about get() in this answer? ContainsKey() is very much not get() – sophia Sep 21 '22 at 12:17
  • It is “linear time in the size of the map” https://docs.oracle.com/en/java/javase/18/docs/api/java.base/java/util/AbstractMap.html#containsKey(java.lang.Object) as the docs say – sophia Sep 21 '22 at 12:26
  • @sophia you're linking to the API doc of AbstractMap, and it says "many implementations will override this method.", which HashMap indeed does - nobody would use it if it did't improve the performance of this key operations to something better than the (abysmally bad) O(n). And if you compare the implementations of HashMap.get() and HashMap.containsKey() you will notice that they are, as I wrote in my answer, identical except that the latter only checks whether the result is null null instead of returning it. – Michael Borgwardt Sep 21 '22 at 20:34
  • Thanks for checking, Michael! I remembered I could look at the source online for Android https://cs.android.com/android/platform/superproject/+/master:libcore/ojluni/src/main/java/java/util/HashMap.java;l=137?q=Hashmap&ss=android%2Fplatform%2Fsuperproject I am still reading the implementation but I can’t come up myself with an idea for how to find a specific key in the key set without iterating over it. TBD when I actually understand the source – sophia Sep 22 '22 at 08:07
  • @sophia: the basic idea of a hashtable is that if your keys are integers in a fixed range, a plain array is a very simple and efficient map implementation, just use the key as an array index. And when your keys are something else, you just cheat by mapping them to fixed-range integers via a hash function and come up with a way to deal with (now unavoidable) collisions. – Michael Borgwardt Sep 23 '22 at 09:52
16

Generally O(1), but if we're using a bad hashCode function, we need to add multiple elements to one bucket so it can be O(n) in worst case.

Trey Keown
  • 1,345
  • 3
  • 16
  • 23
mishadoff
  • 10,719
  • 2
  • 33
  • 55
11

The time complexity of containsKey has changed in JDK-1.8, as others mentioned it is O(1) in ideal cases. However, in case of collisions where the keys are Comparable, bins storing collide elements aren't linear anymore after they exceed some threshold called TREEIFY_THRESHOLD, which is equal to 8,

/**
 * The bin count threshold for using a tree rather than list for a
 * bin.  Bins are converted to trees when adding an element to a
 * bin with at least this many nodes. The value must be greater
 * than 2 and should be at least 8 to mesh with assumptions in
 * tree removal about conversion back to plain bins upon
 * shrinkage.
 */
static final int TREEIFY_THRESHOLD = 8;

In other word, TreeNodes will be used (similar to those in TreeMap) to store bins, (ie: a Red-Black tree structure) and this leaves us with an O(lgn) complexity in-case of collisions.

The same applies for get(key) where where both methods call getNode internally

Note: n here is the size of the bin and not the HashMap

Sleiman Jneidi
  • 22,907
  • 14
  • 56
  • 77
11

It is O(1) in general, however in worst case it is O(n)

 public boolean containsKey(Object key) {
  352           return getEntry(key) != null;
  353       }
  354   
  355       /**
  356        * Returns the entry associated with the specified key in the
  357        * HashMap.  Returns null if the HashMap contains no mapping
  358        * for the key.
  359        */
  360       final Entry<K,V> getEntry(Object key) {
  361           int hash = (key == null) ? 0 : hash(key.hashCode());
  362           for (Entry<K,V> e = table[indexFor(hash, table.length)];
  363                e != null;
  364                e = e.next) {
  365               Object k;
  366               if (e.hash == hash &&
  367                   ((k = e.key) == key || (key != null && key.equals(k))))
  368                   return e;
  369           }
  370           return null;
  371       }
Srini
  • 1,626
  • 2
  • 15
  • 25
jmj
  • 237,923
  • 42
  • 401
  • 438