How hash tables work

You have used Dictionary<TKey, TValue> and HashSet<T> since the C# course, and you know lookups are “instant”. Searching a list is O(n), binary search is O(log n), so how can a lookup take the same time for 10 keys and 10 million? The answer is the hash table, probably the most useful data structure in everyday programming.

The idea: compute where the key lives

An array gives O(1) access by index. A hash table turns any key into an index:

1. Compute the key’s hash code: a number made from the key’s contents (key.GetHashCode()). Equal keys always give the same number.
2. Turn it into a slot number: bucket = hash % bucketCount.
3. Store the entry in that bucket. To find the key later, compute the same bucket and look only there.

No scanning, no sorting: the key itself tells you where to look. That is why ContainsKey does not slow down as the dictionary grows.

Collisions are normal

There are far more possible keys than buckets, so two different keys will sometimes land in the same bucket. This is a collision, and every hash table must handle it. There are two common ways:

• Chaining: each bucket holds a small list of entries. A lookup goes to the bucket and compares the key with each entry in that list. .NET’s Dictionary and HashSet work this way (the chains are stored inside one array of entries for speed).
• Open addressing: if the slot is taken, try the next slot (or another computed one) until a free one is found. Python’s dict and many C++ tables use this.

Either way, a lookup is fast only if chains stay short. That depends on two things: a good hash function that spreads keys evenly, and enough buckets.

Load factor and resizing

The load factor is count / bucketCount, the average chain length. When it gets too high, the table allocates a bigger bucket array (.NET roughly doubles it, to a prime number) and re-inserts every entry, because hash % bucketCount changes when the bucket count changes. A resize is O(n), but it happens rarely, so like List<T> growth the average cost per insert stays O(1).

Keys must follow the equality rules

A hash table relies on two methods of the key: GetHashCode() to find the bucket and Equals() to compare entries inside it. The rule: if two keys are Equal, they must have the same hash code. By default a class uses reference equality: two separate objects with the same data are different keys. A record (or a struct) compares by value, and generates both methods for you.

1var byClass = new Dictionary<GridPointClass, string>();2byClass[new GridPointClass(2, 3)] = "Column C1";3Console.WriteLine(byClass.ContainsKey(new GridPointClass(2, 3)));   // a different object4 5var byRecord = new Dictionary<GridPoint, string>();6byRecord[new GridPoint(2, 3)] = "Column C1";7Console.WriteLine(byRecord.ContainsKey(new GridPoint(2, 3)));       // equal by value8 9class GridPointClass10{11    public int X { get; }12    public int Y { get; }13    public GridPointClass(int x, int y) { X = x; Y = y; }14}15 16record GridPoint(int X, int Y);

False
True

If you must use a class as a key, override both methods. HashCode.Combine mixes several fields into one good hash code:

1class GridPointClass : IEquatable<GridPointClass>2{3    public int X { get; }4    public int Y { get; }5    public GridPointClass(int x, int y) { X = x; Y = y; }6 7    public bool Equals(GridPointClass? other) => other is not null && X == other.X && Y == other.Y;8    public override bool Equals(object? obj) => Equals(obj as GridPointClass);9    public override int GetHashCode() => HashCode.Combine(X, Y);10}

1var set = new SimpleIntSet(4);2foreach (int x in new[] { 5, 9, 13, 2, 9 }) set.Add(x);3Console.WriteLine(set.Count);4Console.WriteLine(set.Contains(13));5Console.WriteLine(set.Contains(6));6 7class SimpleIntSet8{9    private readonly List<int>[] _buckets;10    public int Count { get; private set; }11 12    public SimpleIntSet(int bucketCount)13    {14        _buckets = new List<int>[bucketCount];15        for (int i = 0; i < bucketCount; i++) _buckets[i] = new List<int>();16    }17 18    private List<int> BucketFor(int x) => _buckets[(x.GetHashCode() & int.MaxValue) % _buckets.Length];19 20    public bool Contains(int x) => BucketFor(x).Contains(x);21 22    public bool Add(int x)23    {24        if (Contains(x)) return false;   // a set holds each value once25        BucketFor(x).Add(x);26        Count++;27        return true;28    }29}

4
True
False