CODEWITHSUNDEEP
javahashmaphashtablehashsethashcode
amipro
amipro

Reputation: 386

Maximum length of linkedlist bucket in a hash set?

What is the maximum size of LinkedList in a HashSet and what happens when that max size is reached, if any? If all the n input elements have hash codes that store values in the same node array of the hash map. i.e what happens when due to a specific input , bucket 0 keeps on growing and rest of the buckets are unfilled.Is rehashing done in that case or is there a specific way to avoid this problem?

Upvotes: 3

Views: 1381

Answers (1)

Eugene
Eugene

Reputation: 120898

The strategy is somehow implementation specific, but in general when a HashMap (and HashSet is based on that) reaches 64 entries overall and 8 entries in a single bucket, it will be transformed to a Tree. Until than a resize happens, when a bucket is doubled in size, thus an extra bit is taken into consideration of where to place an entry - this is called rehash - this is done to try and move entries to different buckets.

See this and this for some implementation specifics.

Upvotes: 1

Related Questions