I need to know: What is the time complexity of HashMap.containsKey() in java?
- 1@OlegSklyar This question helped me because I had to implement a HashMap myself.trinity420– trinity4202017-05-12 10:40:34 +00:00Commented May 12, 2017 at 10:40
- @trinity420 So this justifies not reading the API documentation when you have a question about the API?Oleg Sklyar– Oleg Sklyar2017-05-12 13:01:13 +00:00Commented May 12, 2017 at 13:01
- 1Java 8: Best case O(1), worst case O(log n)Hanash Abdurabuh– Hanash Abdurabuh2020-10-17 12:18:42 +00:00Commented Oct 17, 2020 at 12:18
- if worst case it's not O(1). check this: stackoverflow.com/questions/8923251/…Mohammad Yasin– Mohammad Yasin2021-11-24 12:13:04 +00:00Commented Nov 24, 2021 at 12:13
Add a comment |
4 Answers
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, 2012 at 8:54
Michael Borgwardt
347k81 gold badges491 silver badges726 bronze badges
11 Comments
AlexR
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.
Michael Borgwardt
@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
@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).
bestsss
@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.
Tom Hawtin - tackline
@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.
|
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.
Comments
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 } 
3 Comments
Viruzzo
That would be
Ω(1) and O(n) then.
cellepo
See Answer by mishadoff for explanation of the worst case.
Hanash Abdurabuh
Java 1.8's worst case is O(log n).
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
