3 ms·
The reason the Java HashMap get() is not O(1) is because of separate chaining. The HashMap handles hash collisions by adding all colliding entries to a Linked L
by kt9 10y ago
The reason the Java HashMap get() is not O(1) is because of separate chaining. The HashMap handles hash collisions by adding all colliding entries to a Linked List and lookups have to hash to the correct bucket and then iterate over the linked list in that bucket. So the complexity of a get() is O(1)+O(k) where k is the number of items in the LinkedList.
https://en.wikipedia.org/wiki/Hash_table#Separate_chaining https://en.wikipedia.org/wiki/Hash_table#Separate_chaining
- jschmitz28 10y agoWouldn't this just simplify to O(n)? Consider a case where the keys are objects whose hashcode() is overridden to return a constant (while equals() still uses reference equality from Object.equals).
- justinhj 10y agohttp://stackoverflow.com/questions/4553624/hashmap-get-put-complexity http://stackoverflow.com/questions/4553624/hashmap-get-put-c... It's a dumb question to be authoritative about because there are different implementations of hashmap and hashcode meaning that you can't guarantee the runtime complexity. According to the SO answer above Java8 will be mostly O(1) but full buckets may be stored as trees meaning that they will be O(log n). But as the answer says "So no, O(1) certainly isn't guaranteed - but it's usually what you should assume when considering which algorithms and data structures to use." The interviewer could have explored the candidates knowledge of how hashmap is implemented, or could be implemented, which would be more rewarding than insulting and gloating.