CODEWITHSUNDEEP
javaperformancehashmaptime-complexity
Hossein
Hossein

Reputation: 41931

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

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

Upvotes: 70

Views: 100146

Answers (4)

mishadoff
mishadoff

Reputation: 10789

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.

Upvotes: 16

Sleiman Jneidi
Sleiman Jneidi

Reputation: 23339

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

Upvotes: 11

Jigar Joshi
Jigar Joshi

Reputation: 240948

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       }

Upvotes: 11

Michael Borgwardt
Michael Borgwardt

Reputation: 346476

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).

Upvotes: 79

Related Questions