liveBook · Manning

Hash chain

As explained in High Performance Unity Game Development

A linked sequence of hash-table entries that share the same bucket because their keys produce colliding hash values.

A hash chain links dictionary entries that map to the same bucket. Each entry stores its key, value, hash code, and the index of the next entry; a terminal value marks the end. section 10.1

A dictionary uses the chain to resolve collisions and retrieve values:

  • On insertion, the new entry links to the previous first entry in the bucket, and the bucket points to the new entry. section 10.1
  • On lookup, the dictionary hashes the key to find a bucket, then follows entry links and compares keys until it finds a match or reaches the chain’s end. section 10.1

A collision between Zombie and Vampire

If both keys map to the same bucket, the bucket can point to Zombie, which links to Vampire. Looking up Vampire checks Zombie first, then follows the link to the matching entry. section 10.1

Figure 10.5 To retrieve a value from a C# Dictionary, the key is hashed to find the bucket. The bucket points to the first entry in the chain. If that entry’s key does not match, the dictionary follows the next index until it finds the matching key or reaches the end of the chain. In this case, "Vampire" hashes to bucket 2. Bucket 2 points to entry 0, where the dictionary compares the stored hash and key. Entry 0 belongs to "Zombie", not "Vampire", so the dictionary proceeds to the next link, entry 1. Entry 1 matches the key "Vampire", so the dictionary returns its value. Since VampireData is an object, the value stored in the entry is a reference, which points to the actual VampireData object in heap memory.

Trace how a C# Dictionary follows a bucket chain to retrieve Vampire’s value. section 10.1

How High Performance Unity Game Development covers it

How deep it goes
Details entry fields, insertion links, and lookup traversal, then compares dictionary access with array lookup and cache predictability.
Examples
Uses Zombie and Vampire keys to trace a collision chain and a successful lookup.
What you can do after
Understand how dictionaries resolve collisions and traverse chains during lookup.
How it connects
Connects hash tables, hashing, arrays, dictionary lookup, and CPU cache behavior.

Also explained in

Compare how 3 books explain hash chain →

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.