Card 03/ 09
Hash Collisions: Two Keys in the Same Bucket
A collision is the normal state of a map; only an equal key ever replaces a value.
A hash collision is two different keys landing in the same bucket, one of the slots a hash map sorts its entries into. With billions of possible hash codes and sixteen buckets to start, collisions are the normal state of a map, not an edge case. The bucket holds both entries, and a lookup checks each with equals until it finds a match.
Two different keys, with two different hash codes, reduce to the same bucket index. Nothing is overwritten and nothing is an error. What put does depends on what the bucket already holds:
| The bucket holds | put does | size() changes |
|---|---|---|
| Nothing | Stores the entry | Yes |
An entry with a key that is not equals | Stores this one alongside it | Yes |
An entry with a key that is equals | Replaces that entry's value | No |
The third row is the only one that overwrites, and it is the behaviour people expect from a map: putting the same key twice keeps one entry with the second value. The first two rows are collisions, and both keys survive.
So a good hashCode is not one that never collides, which is impossible; it is one that spreads keys evenly, so that no bucket holds many more than its share.
← → move through sections and cards