liveBook · Manning

Hash collision

As explained in High Performance Unity Game Development

A hash collision occurs when distinct keys produce the same hash value.

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

How High Performance Unity Game Development covers it

How deep it goes
Compares free-slot searching with bucket chains and describes lookup behavior, without detailing hash generation.
Examples
Uses Zombie and Vampire keys to illustrate entries that share a bucket.
What you can do after
Evaluate how collisions can lead to linear searches or linked-chain traversal during dictionary lookup.
How it connects
Connects hash collisions to dictionaries, hash values, buckets, and linked lists.

Also explained in

Compare how 6 books explain hash collision →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of High Performance Unity Game Development. The section links point to the parts of the book it draws on.