CODEWITHSUNDEEP
javahashmap
AdityaKapreShrewsburyBoston
AdityaKapreShrewsburyBoston

Reputation: 1143

Is retrieval order of elements in HashMap really randomized?

Is the retrieval of entries from HashMap really randomized? Or does it depend on buckets in which the entries are hashed and then these buckets are accessed in some predefined order ? or any other kind of order internally happening?

Upvotes: 2

Views: 219

Answers (2)

Andy Brown
Andy Brown

Reputation: 12999

What happens when you call the get method on a HashMap for a non-null key:

  1. The hashCode() method for your key is called.

  2. The hash bucket for that hash is obtained by simply and'ing the hash with the number of buckets - 1 which works because the implementation ensures that the number of buckets is always a power of 2. Because the buckets are simply a java array of HashMap.Entry objects the resulting integer can be used as a plain array index. This is where the O(1) complexity comes from.

  3. The entries in the bucket (a linked list) are iterated until one is found where the hash and the key match the one you want. This is where the O(1) complexity starts to deteriorate towards a worst case of O(n).

So you can see that an efficient use of the HashMap will try to minimise the number of entries that end up together in a bucket. All that matters in that respect is the distribution of the bits in your hashcode from bit 0 to bit N-1 where N is the power of 2 used to calculate the number of buckets. All bits in your hashcode above that limit are masked away and only get used again during the iteration of the bucket list.

Upvotes: 2

khelwood
khelwood

Reputation: 59113

Answer b - it depends on buckets in which the entries are hashed and then these buckets are accessed in some predefined order

Upvotes: 6

Related Questions