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.