Resizing of array table in HashMap implementation

user_13948608 0
Viewed 398

This one is simple question, for those who know internal implementation of HashMap :)

Initial size is 16 buckets, load factor is 0.75. Meaning when it gets (watch that word) 12, it resizes to 32 buckets.

My question is does it resize from 16 to 32 buckets when it gets 12 key-value pairs or when it gets 12 'filled' buckets? I am asking that because it could happen that from those 16 buckets all 12 key-value pairs get inserted to same bucket. In that case it would be weird to resize as other 15 are totally empty.

Thanks, any opinion on this would be appreciated :)

bucket hashmap java
2 Answers

From JavaDoc https://docs.oracle.com/javase/8/docs/api/java/util/HashMap.html#put-K-V-

When the number of entries in the hash table exceeds the product of the load factor and the current capacity, the hash table is rehashed (that is, internal data structures are rebuilt) so that the hash table has approximately twice the number of buckets.

So, HashMap resize when it has 12 key-value pairs. It isn't weird, because after resizing entries will change their bucket.

user_116533980

As mentioned in this link.

It represents that 12th key-value pair of hashmap will keep its size to 16. As soon as 13th element (key-value pair) will come into the Hashmap, it will increase its size from default 2^4 = 16 buckets to 2^5 = 32 buckets.

Independent where each key was inserted, when the product of load factor and current capacity exceed, the table will be resized.

The HashMap doesn't care about how many buckets were used until the load factor has been reached, it knows that the probability of having collisions is becoming too big, and the map should be resized. Even though many collisions already happened.

user_127550350
Related