A hash collision occurs when distinct keys produce the same hash value, mapping them to the same dictionary bucket. section 10.1
Dictionary implementations handle collisions in different ways:
- Search for the next free slot, then search linearly from the hashed location when looking up a key. section 10.1
- Keep multiple entries in a bucket’s linked chain, following links until the key matches or the chain ends. section 10.1
Zombie and Vampire
If both enemy names hash to the same bucket, the dictionary can link their entries in a collision chain. section 10.1
Figure 10.4 When a key hashes to a bucket that already contains an entry, the new entry is added to the entries array and linked to the previous first entry in that bucket. The bucket is then updated to point to the new entry. In this case, Zombie hashed to the same value as Vampire and was placed after it. The bucket points to Zombie, which then points to Vampire, even though Vampire was there first.

See how a bucket links the newer Zombie entry to the existing Vampire entry. section 10.1





