CODEWITHSUNDEEP
javahashmaptime-complexityhashcode
Ramesh
Ramesh

Reputation: 1942

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

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

Upvotes: 0

Views: 108

Answers (2)

OldCurmudgeon
OldCurmudgeon

Reputation: 65811

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.

Upvotes: 4

TheLostMind
TheLostMind

Reputation: 36304

First of all get(Key)s time-complexity of HashMap is NOT always O(1). O(1) is the ideal case.

HashMap has an Array of instances Entry. HashCode of the object determines in which index of this array a "new entry" should go. If 2 Objects have to get into the same bucket / index (if there is a collision), then a LinkedList is used and the new Entry is added to the LinkedList. Worst case, all enteries could map to the same index (if there is only one bucket) and the time complexity will be O(n).

Upvotes: 0

Related Questions