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

Question

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

@OlegSklyar This question helped me because I had to implement a HashMap myself. — trinity420, May 12 '17 at 10:40
@trinity420 So this justifies not reading the API documentation when you have a question about the API? — Oleg Sklyar, May 12 '17 at 13:01
if worst case it's not O(1). check this: https://stackoverflow.com/questions/8923251/what-is-the-time-complexity-of-hashmap-containskey-in-java — Mohammad Yasin, Nov 24 '21 at 12:13

score 73 · Accepted Answer · answered Jan 19 '12 at 08:54

73

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

answered Jan 19 '12 at 08:54

Michael Borgwardt

335,521
76
467
706

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
@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

score 17 · Answer 2 · edited Sep 16 '16 at 20:33

17

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.

edited Sep 16 '16 at 20:33

Trey Keown

1,305
3
15
23

answered Jan 19 '12 at 08:54

mishadoff

10,583
2
32
54

score 12 · Answer 3 · edited Jul 23 '15 at 20:20

12

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       }

edited Jul 23 '15 at 20:20

Srini

1,588
2
14
24

answered Jan 19 '12 at 08:53

jmj

232,312
42
391
431

10

That would be `Ω(1)` and `O(n)` then. – Viruzzo Jan 19 '12 at 09:00
See Answer by mishadoff for explanation of the worst case. – cellepo Oct 22 '15 at 14:56
1

Java 1.8's worst case is O(log n). – Hanash Yaslem Oct 17 '20 at 12:17

Sleiman Jneidi · Answer 4 · 2016-01-19T10:28:04.790

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

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

4 Answers4

Linked