How Hash Tables Work: Writing Your Own HashMap in C#, Collisions and Load Factor

Version note: The code in this post was built with .NET 10 and C# 14 and verified with xUnit v3 4.0.2 tests; measurements were taken with BenchmarkDotNet 0.15.8.

Guess First

A developer wrote a key class that wraps an ISBN (International Standard Book Number). Equals is correct, but to get it done quickly, GetHashCode always returns 42. That is not against the rules: two equal keys give the same hash code, so the contract is not broken. The tests are green.

Bookstore puts 10,000 books into a Dictionary with this key and looks each one up once. If the job takes 0.3 ms with a proper GetHashCode, how long does it take with the version that returns 42: twice as long, 10 times, 1,000 times?

From Hash Function to Bucket

The idea of a hash table is simple: derive an integer from the key (the hash code), reduce it to the array size, and put the element in the "bucket" at that index. A lookup repeats the same calculation and goes straight to that bucket without looking at any other element. That is why a Dictionary is O(1) on average.

The problem: there are infinitely many possible keys but the array is finite, so two different keys landing in the same bucket is unavoidable. That is called a collision. It even happens much sooner than you would expect: put 23 random keys into a table with 365 buckets and the probability of at least one collision passes 50 percent (the birthday paradox). Designing a hash table means deciding how to resolve collisions. There are two main ways: separate chaining and open addressing.

Separate Chaining: the Same Internals as Dictionary

With separate chaining, each bucket keeps the chain of elements that fall into it. In textbooks that chain is usually a linked list, with the per-node allocation and cache cost we saw in the series' third post. .NET's Dictionary takes a smarter route, and our version copies it: all elements live in a single Entry[] array, and the chain is built with array indexes instead of node references.

namespace Algorithms.Hashing;

// Separate chaining in the same shape as .NET's Dictionary:
// buckets[] holds 1-based indexes into entries[], entries are chained with a "next" index.
public sealed class ChainedHashMap<TKey, TValue> where TKey : notnull
{
    private struct Entry
    {
        public uint HashCode;
        public int Next;      // index of the next entry in the same bucket, -1 = end of chain
        public TKey Key;
        public TValue Value;
    }

    private int[] _buckets;
    private Entry[] _entries;
    private int _count;       // slots used in _entries (including freed ones)
    private int _freeList = -1;
    private int _freeCount;
    private readonly IEqualityComparer<TKey> _comparer;

    public ChainedHashMap(int capacity = 0, IEqualityComparer<TKey>? comparer = null)
    {
        int size = Primes.AtLeast(Math.Max(capacity, 3));
        _buckets = new int[size];
        _entries = new Entry[size];
        _comparer = comparer ?? EqualityComparer<TKey>.Default;
    }

    public int Count => _count - _freeCount;
    public int BucketCount => _buckets.Length;

    private ref int Bucket(uint hashCode) => ref _buckets[hashCode % (uint)_buckets.Length];

    public bool TryGetValue(TKey key, out TValue value)
    {
        uint hashCode = (uint)_comparer.GetHashCode(key);
        for (int i = Bucket(hashCode) - 1; i >= 0; i = _entries[i].Next)
        {
            ref Entry entry = ref _entries[i];
            // compare the cached hash first: a cheap int compare filters most non-matches
            if (entry.HashCode == hashCode && _comparer.Equals(entry.Key, key))
            {
                value = entry.Value;
                return true;
            }
        }
        value = default!;
        return false;
    }

    public void Set(TKey key, TValue value)
    {
        uint hashCode = (uint)_comparer.GetHashCode(key);
        for (int i = Bucket(hashCode) - 1; i >= 0; i = _entries[i].Next)
        {
            if (_entries[i].HashCode == hashCode && _comparer.Equals(_entries[i].Key, key))
            {
                _entries[i].Value = value; // overwrite existing key
                return;
            }
        }

        int index;
        if (_freeCount > 0)
        {
            index = _freeList;
            _freeList = -3 - _entries[index].Next; // same free-list encoding trick as Dictionary
            _freeCount--;
        }
        else
        {
            if (_count == _entries.Length) Resize(); // load factor 1.0: one entry per bucket on average
            index = _count++;
        }

        ref int bucket = ref Bucket(hashCode);
        _entries[index] = new Entry { HashCode = hashCode, Next = bucket - 1, Key = key, Value = value };
        bucket = index + 1; // new entry becomes the head of its chain
    }

    public bool Remove(TKey key)
    {
        uint hashCode = (uint)_comparer.GetHashCode(key);
        ref int bucket = ref Bucket(hashCode);
        int previous = -1;
        for (int i = bucket - 1; i >= 0; previous = i, i = _entries[i].Next)
        {
            ref Entry entry = ref _entries[i];
            if (entry.HashCode != hashCode || !_comparer.Equals(entry.Key, key)) continue;

            if (previous < 0) bucket = entry.Next + 1;
            else _entries[previous].Next = entry.Next;

            entry.Key = default!;
            entry.Value = default!;
            entry.Next = -3 - _freeList; // values below -1 mark a free slot
            _freeList = i;
            _freeCount++;
            return true;
        }
        return false;
    }

    private void Resize()
    {
        int newSize = Primes.AtLeast(_count * 2);
        Entry[] entries = new Entry[newSize];
        Array.Copy(_entries, entries, _count);
        _buckets = new int[newSize];
        // re-link every entry: its bucket depends on the new length; the cached hash avoids GetHashCode calls
        for (int i = 0; i < _count; i++)
        {
            ref int bucket = ref _buckets[entries[i].HashCode % (uint)newSize];
            entries[i].Next = bucket - 1;
            bucket = i + 1;
        }
        _entries = entries;
    }

    public int LongestChain()
    {
        int longest = 0;
        foreach (int head in _buckets)
        {
            int length = 0;
            for (int i = head - 1; i >= 0; i = _entries[i].Next) length++;
            longest = Math.Max(longest, length);
        }
        return longest;
    }
}

There are three tricks in this code, all taken from Dictionary.cs in dotnet/runtime. The first is 1-based buckets: new int[size] starts every slot at 0; storing index + 1 in the bucket makes 0 mean "empty bucket", so there is no need to fill the array with -1. Bucket(hashCode) - 1 gives -1 for an empty bucket and the loop never starts. The second is the hash code cached in each entry: a lookup first compares two uint values and only calls the potentially expensive Equals when the hashes match; during a resize GetHashCode is never called. The third is the free list: so that a removed entry's slot is not wasted, free slots are chained to each other and the Next field is encoded as -3 - nextIndex. Every value below -1 then means "this slot is free", and the enumerator can skip those slots.

Keeping entries in a single array has two benefits: there is no separate object per element (just one large array for the GC (Garbage Collector)), and walking a chain means jumping within the same array. Compared with classic chaining using linked lists, it uses less memory and behaves better in the cache.

How .NET's Dictionary Grows: Prime Sizes

Our Resize grows to the first prime above twice the size. Dictionary makes the same decision but takes primes from a ready-made table instead of computing them. Because EnsureCapacity(0) returns the current capacity without growing, we can see the values the capacity goes through while adding 2,000 elements:

Dictionary capacity steps: 3 -> 7 -> 17 -> 37 -> 89 -> 197 -> 431 -> 919 -> 1931 -> 4049

After 37 comes 89, not 79, because HashHelpers.ExpandPrime in dotnet/runtime doubles the size (74) and takes the first number greater than or equal to it from the Primes table, which goes 3, 7, 11, 17, 23, 29, 37, 47, 59, 71, 89, ... Why prime? The bucket index is computed with hash % size. If size were a power of two, only the last few bits of the hash would be used, and hashes with similar low bits (for example values that are always multiples of 8) would pile up in the same buckets. A prime size takes all the bits of the hash into account. In 64-bit processes Dictionary does not even use the expensive %: HashHelpers.FastMod finds the same result with a multiplication and a shift using a precomputed multiplier.

The load factor is the ratio of elements to buckets. Both our version and Dictionary grow when the entries array is completely full, so the load factor is at most 1.0. For chaining that is a comfortable value: on average one element per bucket, and short chains. Every resize relinks all entries and is O(n), but because the size doubles each time, the amortized cost is constant. It is the same calculation as the dynamic array in the series' second post; the proof is in the Big-O and Complexity series post "Amortized Analysis".

Open Addressing: Linear Probing and Tombstones

The second way keeps no chains: on a collision, put the element in the next free slot of the table. A lookup follows the same path: start at the slot the hash points to, and move forward until you find the key or hit a truly empty slot.

namespace Algorithms.Hashing;

// Open addressing: every key lives in the slots array itself; collisions move to the next slot.
public sealed class LinearProbingHashMap<TKey, TValue> where TKey : notnull
{
    private enum SlotState : byte { Empty, Occupied, Deleted }

    private struct Slot
    {
        public SlotState State;
        public TKey Key;
        public TValue Value;
    }

    private const double MaxLoad = 0.5; // probing degrades quickly as the table fills
    private Slot[] _slots = new Slot[8];
    private int _occupied;
    private int _deleted; // tombstones also lengthen probe sequences, so they count toward the load

    public int Count => _occupied;

    private int IndexFor(TKey key) => (EqualityComparer<TKey>.Default.GetHashCode(key) & 0x7FFF_FFFF) % _slots.Length;

    public bool TryGetValue(TKey key, out TValue value)
    {
        for (int i = IndexFor(key); ; i = (i + 1) % _slots.Length)
        {
            ref Slot slot = ref _slots[i];
            if (slot.State == SlotState.Empty) break;        // a truly empty slot ends the search
            if (slot.State == SlotState.Occupied && EqualityComparer<TKey>.Default.Equals(slot.Key, key))
            {
                value = slot.Value;
                return true;
            }
            // Deleted: keep walking, the key may sit further along the probe sequence
        }
        value = default!;
        return false;
    }

    public void Set(TKey key, TValue value)
    {
        if (_occupied + _deleted + 1 > _slots.Length * MaxLoad) Resize();

        int firstTombstone = -1;
        for (int i = IndexFor(key); ; i = (i + 1) % _slots.Length)
        {
            ref Slot slot = ref _slots[i];
            if (slot.State == SlotState.Occupied && EqualityComparer<TKey>.Default.Equals(slot.Key, key))
            {
                slot.Value = value;
                return;
            }
            if (slot.State == SlotState.Deleted && firstTombstone < 0) firstTombstone = i;
            if (slot.State == SlotState.Empty)
            {
                int target = firstTombstone >= 0 ? firstTombstone : i; // reuse a tombstone if we passed one
                if (target == firstTombstone) _deleted--;
                _slots[target] = new Slot { State = SlotState.Occupied, Key = key, Value = value };
                _occupied++;
                return;
            }
        }
    }

    public bool Remove(TKey key)
    {
        for (int i = IndexFor(key); ; i = (i + 1) % _slots.Length)
        {
            ref Slot slot = ref _slots[i];
            if (slot.State == SlotState.Empty) return false;
            if (slot.State == SlotState.Occupied && EqualityComparer<TKey>.Default.Equals(slot.Key, key))
            {
                // tombstone, not Empty: an Empty slot here would cut the probe chain of later keys
                slot = new Slot { State = SlotState.Deleted };
                _occupied--;
                _deleted++;
                return true;
            }
        }
    }

    private void Resize()
    {
        Slot[] old = _slots;
        // grow only if live keys need it; if tombstones caused the pressure, rebuilding at the same size cleans them
        int newSize = _occupied + 1 > old.Length * MaxLoad / 2 ? old.Length * 2 : old.Length;
        _slots = new Slot[newSize];
        _occupied = _deleted = 0;
        foreach (Slot slot in old)
            if (slot.State == SlotState.Occupied) Set(slot.Key, slot.Value);
    }
}

The subtlest point of open addressing is removal. In an 8-slot table, int keys hash to themselves; 1, 9 and 17 all start at slot 1 and settle into slots 1, 2 and 3. Remove 9 and mark its slot Empty, and the code looking for 17 sees 1 at slot 1, moves on, hits an empty slot at 2 and says "17 is not here", even though 17 sits one step further. The fix is to mark the removed slot with a "tombstone": a lookup does not stop at a tombstone, and an insert can reuse it.

[Fact]
public void LinearProbing_RemoveMiddleOfCluster_LaterKeyStillFound()
{
    // ints hash to themselves: 1, 9 and 17 all start at slot 1 of an 8-slot table
    LinearProbingHashMap<int, string> map = new();
    map.Set(1, "a");
    map.Set(9, "b");
    map.Set(17, "c");

    map.Remove(9); // tombstone between 1 and 17

    Assert.True(map.TryGetValue(17, out string? value));
    Assert.Equal("c", value);
}

Tombstones have a price too: over time they fill the table and lengthen probe sequences. That is why Set counts tombstones when computing the load, and Resize rebuilds the table cleanly at the same size without growing when tombstones are the source of the pressure. Linear probing's performance drops quickly once the load factor passes 0.5–0.7; collisions form adjacent clusters (primary clustering), and clusters merge and grow. That is why probing grows at a lower threshold while chaining is comfortable at 1.0. In return, open addressing has no pointers; elements sit one after another in the array, which is cache-friendly for small, fixed-size keys.

We test both implementations the same way: apply 20,000 random Set, Remove and TryGetValue operations to both our map and a Dictionary, and check at every step that they give the same answer:

[Fact]
public void ChainedHashMap_SetGetRemove_BehavesLikeDictionary()
{
    ChainedHashMap<string, int> map = new();
    Dictionary<string, int> reference = [];
    Random random = new(1);

    for (int step = 0; step < 20_000; step++)
    {
        string key = "isbn-" + random.Next(2_000);
        switch (random.Next(3))
        {
            case 0:
                map.Set(key, step);
                reference[key] = step;
                break;
            case 1:
                Assert.Equal(reference.Remove(key), map.Remove(key));
                break;
            default:
                Assert.Equal(reference.TryGetValue(key, out int expected), map.TryGetValue(key, out int actual));
                Assert.Equal(expected, actual);
                break;
        }
    }
    Assert.Equal(reference.Count, map.Count);
}

$ dotnet test --project tests/Algorithms.Tests -- --filter-class Algorithms.Tests.HashingTests
tests/Algorithms.Tests/bin/Debug/net10.0/Algorithms.Tests.dll (net10.0|arm64) passed (611ms)

Test run summary: Passed!
  total: 6
  failed: 0
  succeeded: 6

The GetHashCode and Equals Contract

A hash table's correctness hangs on one rule: two keys that are equal according to Equals must return the same GetHashCode. The reverse is not required; different keys with the same hash are a collision, not a bug. Break the rule and an equal key goes to a different bucket, and Dictionary cannot find the existing entry.

When writing it by hand, use HashCode.Combine; it mixes several fields into a single, well-distributed hash. Records generate Equals and GetHashCode from all their fields automatically and come ready to use as keys:

public sealed record OrderLineKey(int OrderId, string Isbn);

public sealed class ShelfLocation(string aisle, int shelf) : IEquatable<ShelfLocation>
{
    public string Aisle { get; } = aisle;
    public int Shelf { get; } = shelf;
    public bool Equals(ShelfLocation? other) => other is not null && other.Aisle == Aisle && other.Shelf == Shelf;
    public override bool Equals(object? obj) => Equals(obj as ShelfLocation);
    public override int GetHashCode() => HashCode.Combine(Aisle, Shelf);
}

A class that does not override them uses reference equality: two different instances with the same values count as different keys. Changing the hashed fields of an object used as a key is the most common way of "losing" an entry in a dictionary; that trap was covered in detail in the C# Collections series post "C# Dictionary and HashSet: TryGetValue, Key Equality and Comparers".

A Bad Hash: Everything in One Bucket

Back to the opening question. A GetHashCode that returns 42 does not break the contract, but it turns the hash table into a single long chain. The test shows it directly: with 1,000 keys the longest chain in our map is 1,000:

public sealed class BadIsbnKey(string isbn) : IEquatable<BadIsbnKey>
{
    public string Isbn { get; } = isbn;
    public bool Equals(BadIsbnKey? other) => other is not null && other.Isbn == Isbn;
    public override bool Equals(object? obj) => Equals(obj as BadIsbnKey);
    // legal (equal keys have equal hashes) but useless: every key lands in the same bucket
    public override int GetHashCode() => 42;
}

[Fact]
public void ChainedHashMap_ConstantHash_SingleLongChain()
{
    ChainedHashMap<BadIsbnKey, int> bad = new();
    ChainedHashMap<GoodIsbnKey, int> good = new();
    for (int i = 0; i < 1_000; i++)
    {
        bad.Set(new BadIsbnKey($"978{i:D10}"), i);
        good.Set(new GoodIsbnKey($"978{i:D10}"), i);
    }

    Assert.Equal(1_000, bad.LongestChain());
    Assert.True(good.LongestChain() <= 8, $"longest chain {good.LongestChain()}");
}

The benchmark puts N keys into a Dictionary and looks each one up once:

BenchmarkDotNet v0.15.8, macOS 27.0.1 (26A434) [Darwin 27.0.0]
Apple M5, 1 CPU, 10 logical and 10 physical cores
.NET SDK 10.0.402
  [Host] : .NET 10.0.13 (10.0.13, 10.0.1326.50504), Arm64 RyuJIT armv8.0-a

| Method             | N     | Mean          | Ratio  | Allocated |
|------------------- |------ |--------------:|-------:|----------:|
| GoodHash           | 1000  |      24.65 us |   1.00 |  30.21 KB |
| ConstantHash       | 1000  |   2,861.57 us | 116.10 |  30.21 KB |
| OwnChainedGoodHash | 1000  |      15.64 us |   0.63 |   27.7 KB |
|                    |       |               |        |           |
| GoodHash           | 10000 |     304.83 us |   1.00 | 276.43 KB |
| ConstantHash       | 10000 | 294,835.74 us | 967.33 | 276.38 KB |
| OwnChainedGoodHash | 10000 |     286.57 us |   0.94 | 273.78 KB |

With 10,000 keys the 0.3 ms job becomes 295 ms: 967 times. Every insert walks the whole chain to see whether the key already exists, and so does every lookup. The total number of comparisons is around n², so a structure that is O(1) on average falls to O(n). When the number of keys grows 10 times, the ratio goes from 116 to 967; that is quadratic growth itself. The Allocated column is the same: the problem is not memory but the number of comparisons. Our own chaining version comes out slightly faster than the BCL (Base Class Library) with a good hash; Dictionary does work we skip, such as enumerator protection, alternate lookup and the randomized string switch. The measurement ran while other work was running on the machine.

Security: Hash Flooding and Randomized String Hashing

A bad hash is not just a performance bug; it is an attack surface. If attackers know the hash function, they can produce thousands of different keys that land in the same bucket (form field names, JSON (JavaScript Object Notation) properties, query string parameters) and turn the server's hash tables into a single chain. This DoS (Denial of Service) attack, which locks up the CPU (Central Processing Unit) with little traffic, is called hash flooding; it hit many web platforms in 2011.

.NET Core's defence is to compute string hashes with a random seed in every process. Run the same program twice and you see it:

$ dotnet Algorithms.Demos.dll string-hash
"Dune".GetHashCode() = -1172752349
42.GetHashCode()     = 42
$ dotnet Algorithms.Demos.dll string-hash
"Dune".GetHashCode() = 1391195764
42.GetHashCode()     = 42

Because the attacker does not know the seed, colliding keys cannot be computed in advance. This has a consequence: never write string.GetHashCode() to disk, put it in a database or compare it across processes; it is different on the next run. Dictionary goes one step further: with string keys and the default comparer it first uses a faster, non-randomized hash, and if it sees more than 100 collisions in a single chain (HashHelpers.HashCollisionThreshold) it switches to the randomized comparer and rehashes the whole table.

Further Note: the Bloom Filter

Sometimes the answer "this key is definitely not here" is valuable on its own. Bookstore's sign-up form asks an in-memory filter whether the e-mail address entered has been used before, before asking the database. A Bloom filter uses a bit array and k hash functions: on insert it sets k bits to 1, on lookup it checks whether all k bits are 1. If even one bit is 0, the key is definitely absent; if all are 1, it is "probably present", because those bits may have been set by other keys. No false negatives, a controlled rate of false positives:

using System.Collections;

namespace Algorithms.Hashing;

// "Definitely not present" or "probably present": no false negatives, some false positives.
public sealed class BloomFilter(int bitCount, int hashCount)
{
    private readonly BitArray _bits = new(bitCount);

    public void Add(string item)
    {
        (uint h1, uint h2) = Hash(item);
        for (int i = 0; i < hashCount; i++) _bits[Index(h1, h2, i)] = true;
    }

    public bool MightContain(string item)
    {
        (uint h1, uint h2) = Hash(item);
        for (int i = 0; i < hashCount; i++)
            if (!_bits[Index(h1, h2, i)]) return false;
        return true;
    }

    // k hash functions from two: g_i = h1 + i * h2 (Kirsch and Mitzenmacher)
    private int Index(uint h1, uint h2, int i) => (int)((h1 + (uint)i * h2) % (uint)bitCount);

    // FNV-1a 64-bit: deterministic across processes, unlike string.GetHashCode
    private static (uint, uint) Hash(string item)
    {
        ulong hash = 14695981039346656037UL;
        foreach (char c in item)
        {
            hash ^= c;
            hash *= 1099511628211UL;
        }
        return ((uint)hash, (uint)(hash >> 32) | 1);
    }
}

 5 bits/item, k= 3:    61 KB, false positives 9,095/100,000 = 9.10%
10 bits/item, k= 7:   122 KB, false positives 810/100,000 = 0.81%
20 bits/item, k=14:   244 KB, false positives 9/100,000 = 0.01%

For 100,000 e-mail addresses, a 122 KB filter rules out 99.19 percent of absent addresses without ever going to the database. Keeping the same addresses in a HashSet<string> would take megabytes. We use FNV-1a from the FNV (Fowler–Noll–Vo) family for the hash because string.GetHashCode changes per process; if you want to save the filter to disk and load it later, you need a deterministic hash. Bloom filters are used in storage engines such as Cassandra and RocksDB (to avoid reading a file for a key that is not on disk) and in front of caches. The limit: you cannot remove elements, because clearing a bit also removes other keys.

In Production

If you write your own key type, measure its hash distribution. There is no diagnostic like our map's LongestChain in the BCL, but keys.GroupBy(k => k.GetHashCode()).Max(g => g.Count()) shows how many keys share the same hash. If the result is greater than 1, understand why.

If you know the capacity, pass it. new Dictionary<string, Book>(100_000) removes more than 10 resizes and the relinking in each of them. For dictionaries that stay in memory for a long time, are read often and never change, there is FrozenDictionary; it does more work at construction to make reads faster (C# Collections series post "C# 11–12 and .NET 7–8: Generic Math, Frozen and Collection Expressions").

Do not build dictionaries that grow without limit from outside keys. A Dictionary that opens an entry for every distinct value the user sends is a memory-exhausting attack surface even without hash flooding. Limit the count or use a real cache.

Common Pitfalls

Overriding Equals and forgetting GetHashCode. The compiler warns about it, but the result is silent: equal keys go to different buckets and ContainsKey returns false. Always write both together, or use a record.

Writing a constant or weak hash. A hash that returns 42 passes the tests and is 967 times slower in production. Similarly, hashing only one field, for keys where that field always has the same value (for example a country code that is always "TR"), produces the same result.

Emptying a removed slot in open addressing. Writing Empty instead of a tombstone makes later keys in the same cluster invisible. That is why the test removes from the middle of a cluster.

Persisting string.GetHashCode. The value differs in every process; on the next deploy every match is lost. If you need a persistent hash, use a deterministic algorithm such as SHA-256 from the SHA (Secure Hash Algorithm) family or XxHash.

A Small Experiment

★☆☆ Change BadIsbnKey.GetHashCode to return the value of the ISBN's last character (only 10 distinct hashes). What is the longest chain with 10,000 keys? Where does the time land in the benchmark?

★★☆ Make MaxLoad a parameter of LinearProbingHashMap and write a test that measures the average probe length for 0.5, 0.7 and 0.9. How does the length grow with the load factor?

★★★ For the Bloom filter, write a factory method that computes the number of bits and k from the expected number of elements n and a target false positive rate p (m = −n·ln p / (ln 2)², k = (m/n)·ln 2). With a 1% target for 100,000 addresses, how close is the rate you measure to the target?

We have seen the hash table from the inside. In the next post we use it as a tool: the frequency map that takes two sum from O(n²) to O(n), plus array and hashing patterns such as two pointers, sliding window and prefix sum, all on Bookstore's order and sales data.