A Hashmap bucket can contain different hashcoded object. If so How hashmap achieves O(1)

Question

Hi I am trying to understand how hashmap working . Hashmap works based on hasing principle .

My doubt is Is it possible to contain different hashcoded object in same bucket ? If it is possible means how get(key) achieves O(1) time ? Because based on the hashcode and hashing , Bucket will be found . but One have to iterate through elements right . Then how it will be O(1).

For example My Bucket size is 4 I am going to put elements "X"( hashcode - 3) , "Y" ( hashcode - 7) , "Z"( hashcode - 11) . All these three elements bucket location will be 3 . If I am calling get("Z") means It have to traverse through elements in the bucket then only it can find . Then Then how it will be O(1).

Please anyone help me to clear my doubt. Thanks in Advance

Answer 1

Because the hashmap lookup algorithm works like this:

1. Derive an integer hash value from the object - O(1)
2. Locate the bucket for that hash - O(1)
3. Find the object in that bucket - O(number of collided hashes in that bucket)

Although the number of collided hashes in that bucket can increase towards n under extreme circumstances (such as we only have one bucket) those circumstances are not considered when deriving the Oness of the algorithm. This value is considered to be 1 because increasing n does not affect it's cost even lineraly under normal circumstances.