Inside a Dictionary: buckets and collisions

A dictionary turns the key into a number, uses that number to choose a bucket, and only searches inside that one bucket.

The idea

Hashing jumps straight to one bucket instead of scanning everything. Two keys that land in the same bucket are a collision, and they are kept in a short chain that is searched one by one.

Code

var map = new Dictionary<int, string>();
map[key] = value;
// What the indexer does inside:
//   int hash = key.GetHashCode();
//   int bucket = hash % buckets.Length;
//   walk the entries in that bucket:
//   same key found -> replace the value, otherwise add a new entry

Tips

• This picture uses 5 buckets and never resizes. The real Dictionary uses a prime number of buckets and grows when it fills up, which keeps chains short.
• If many keys share a bucket, lookups slow down towards O(n). A good GetHashCode spreads keys evenly.

In the .NET library

If you override Equals on a key type you must override GetHashCode too, and equal objects must return the same hash. record types do both for you.