090 - Dictionary Internals · dotnetmadeeasy.com

A dictionary lookup doesn't search — it calculates exactly where to look, then checks one spot. That's the entire secret to O(1).

You've used Dictionary<TKey,TValue> since Foundations — prices["Widget"], instant answer, no matter how many thousands of entries the dictionary holds. It never seemed to matter whether the dictionary had 10 entries or 10 million; the lookup always just felt fast. That's not luck, and it's not because .NET secretly searches really quickly — it's because a dictionary lookup doesn't search at all, in the way a List<T> lookup does.

In this lesson, you'll see exactly how Dictionary<TKey,TValue> achieves average O(1) lookups — hash buckets, GetHashCode(), collision handling — and why a poorly-written GetHashCode/Equals pair can quietly wreck that performance. This sets up the next lesson, which covers writing that pair correctly on your own types.

What Is It?

The Simple Explanation

A Dictionary<TKey,TValue> is a hash table: instead of storing entries in a line and checking each one to find a match (like a List<T> would), it runs each key through a quick calculation that turns it into a number, uses that number to jump almost directly to the small area of memory where that key's entry belongs, and only then does the actual comparison — against a tiny handful of candidates, not the whole collection.

The Technical Definition

A hash table stores entries across an internal array of buckets. Every key is passed to GetHashCode(), producing a 32-bit integer called its hash code. That hash code is reduced (typically via a modulo operation) to an index within the bucket array's current size, determining which bucket the entry is placed in. On lookup, the same process runs on the key you're searching for, landing you directly at the correct bucket — collapsing what would otherwise be an O(n) scan into, on average, a small constant amount of work: O(1).

Why Does It Exist?

The Problem

Imagine looking up a key the way List<T>.Find would — walk every entry, one at a time, comparing keys until you find a match:

// A hypothetical "dictionary" backed by a plain list — O(n) lookup
List<(string Key, decimal Value)> prices = [ ("Widget", 9.99m), ("Anvil", 149.99m), /* ...thousands more... */ ];

decimal FindPrice(string key)
{
    foreach (var (k, v) in prices)
        if (k == key) return v;   // has to check every entry, in the worst case
    throw new KeyNotFoundException();
}

With 10 entries, that's fine — nobody notices a few microseconds. With 10 million entries, every single lookup potentially walks millions of comparisons. As the collection grows, lookups get proportionally slower — that's O(n) behavior, and it doesn't scale for the kind of fast, frequent key lookups real applications constantly need (looking up a user by ID, a product by SKU, a setting by name).

The Solution

A hash table sidesteps the scan entirely. Instead of asking "which of these thousands of entries matches?", it asks a single, cheap question up front — "given this key, which bucket should I even be looking in?" — and the answer to that question is a direct calculation, not a search. Once you're pointed at the right bucket, there are only ever a small handful of candidates to check, regardless of how large the dictionary as a whole has grown. This is precisely why Dictionary<TKey,TValue> lookups stay fast even as the collection scales into the millions.

Big Picture

How It Works

Simple Example

You can watch hash codes in action directly — string and every built-in type already override GetHashCode() correctly, so this works out of the box:

string keyA = "Widget";
string keyB = "Anvil";

Console.WriteLine(keyA.GetHashCode());   // some int, e.g. 1836792031 — varies per run for strings
Console.WriteLine(keyB.GetHashCode());   // a different int, in almost all cases

var prices = new Dictionary<string, decimal>
{
    ["Widget"] = 9.99m,
    ["Anvil"] = 149.99m
};

// Internally: prices["Widget"] computes "Widget".GetHashCode(), maps it to a bucket,
// jumps there directly, confirms with Equals("Widget", "Widget") == true, returns 9.99m.
decimal price = prices["Widget"];
Console.WriteLine(price);   // 9.99

Real-World Example

A Repository<T> caching customer records by ID relies entirely on this mechanism to stay fast, even as the cache grows to hold every customer the application has ever touched in a session.

public record Customer(int Id, string Name, string Email);

public class CustomerCache
{
    private readonly Dictionary<int, Customer> _cache = new();

    public void Add(Customer customer) => _cache[customer.Id] = customer;

    public Customer? Find(int id) =>
        _cache.TryGetValue(id, out Customer? customer) ? customer : null;
}

var cache = new CustomerCache();
for (int i = 1; i <= 500_000; i++)
    cache.Add(new Customer(i, $"Customer {i}", $"customer{i}@example.com"));

// Even with half a million entries, this lookup is just as fast as it would be with 5:
Customer? found = cache.Find(482_193);
Console.WriteLine(found?.Name);   // Customer 482193 — near-instant, regardless of cache size

Because int already has a fast, well-distributed GetHashCode() (for a reasonably small int, it's essentially the value itself), _cache[customer.Id] spreads customers evenly across buckets, and TryGetValue reaches any single customer in roughly the same, tiny amount of time — whether the cache holds 5 entries or 500,000.

Analogy

A Post Office's Sorting Bins

Think of a hash table as a post office with a wall of numbered sorting bins. Instead of dumping every letter into one giant pile and reading each one's address to find yours (that's the O(n) list-scan approach), the post office looks at just the ZIP code, uses it to compute a bin number, and drops the letter straight into that bin. When you come to pick up your mail, the clerk computes the same bin number from your ZIP code, walks straight to that one bin, and only then reads the names on the (hopefully very few) letters actually inside it to find yours.

The hash code is the ZIP code — a cheap, quick-to-compute number that narrows the search from "the entire building" down to "one small bin," before any real comparison ever happens.

Under the Hood

Common Confusion

1. "O(1)" doesn't mean "instant" or "guaranteed" — it means "average constant time"

O(1) describes how lookup time scales as the dictionary grows — it stays roughly flat, on average, rather than climbing with the number of entries, the way O(n) would. It's not a claim that every single lookup takes the exact same number of nanoseconds, nor a guarantee against the rare worst case (heavy collisions) degrading toward O(n). "Average" is doing real, important work in that phrase.

2. A hash code collision is not the same thing as two keys being "equal"

Two different keys sharing a hash code is completely normal and expected — the pigeonhole principle guarantees it will eventually happen, since there are far more possible keys than possible 32-bit hash codes. What would be a genuine bug is two keys that Equals() says are equal producing different hash codes — that specific failure is what the next lesson on the Equals/GetHashCode contract covers in full.

3. Buckets don't preserve insertion order — that's why Dictionary<TKey,TValue> iteration order isn't guaranteed

Because an entry's position is determined by its key's hash code, not by when it was added, iterating a dictionary visits entries in whatever order the buckets happen to lay them out — which can even change after a resize. If you need guaranteed order, reach for SortedDictionary<TKey,TValue> (from the previous lesson) or maintain a separate ordered structure alongside the dictionary.

Common Mistakes

Mistake 1 — Assuming dictionary iteration preserves insertion order

Relying on foreach (var kv in dictionary) to visit entries in the order they were added — this happens to often appear true for small dictionaries in practice, but it is explicitly not a documented guarantee, and can break after a resize or with different key distributions. Use SortedDictionary<TKey,TValue> if you need sorted order, or maintain a separate List<TKey> alongside the dictionary if you specifically need insertion order.

Mistake 2 — Mutating a key's fields after it's been used as a dictionary key

If a key's hash code can change after it's already placed in a bucket (say, because it's a mutable class and one of the fields GetHashCode() depends on gets modified), the dictionary will look for it in the new bucket that key would now hash to — but the entry is still sitting in the old bucket. The key effectively becomes unfindable.

public class MutableKey { public int Value; public override int GetHashCode() => Value; }
var key = new MutableKey { Value = 1 };
dict[key] = "data";
key.Value = 2;              //  hash code just changed out from under the dictionary
dict.TryGetValue(key, out var found);   // false — looks in the wrong bucket now

Keys should be effectively immutable — this is exactly why records and immutable value types make such natural dictionary keys.

Mistake 3 — Assuming every custom class already has a "good" hash code

Using a plain custom class as a dictionary key without overriding GetHashCode() and Equals() — by default, they're based on the object's memory reference, not its data, so two logically identical instances won't find each other in the dictionary. The next lesson covers exactly how to write this pair correctly for your own types.

When Should I Use It?

Reach for a Dictionary when

You need fast lookup by a key, and don't care about iteration order.
Your key type already has (or you've correctly written) a well-distributed GetHashCode().
You're doing lookups far more often than full-collection scans.

Reconsider when

You genuinely need entries in a specific order — reach for a sorted collection, or track order separately.
Your key type is mutable in ways that affect its hash code — fix that first, or the dictionary will silently misbehave.
You have only a handful of entries and never look them up by key — a simple list may be simpler and just as fast in practice.

Mental Model

GetHashCode() = turns a key into a number, cheaply
Bucket index = that number, mapped down to "which bin"
Collision = two keys sharing a bucket — normal, handled by a short chain within the bucket
Equals() = the final confirmation, checked only against the few candidates in that one bucket

Remember:
· A dictionary calculates where to look — it never scans the whole collection.
· "O(1) average" assumes a well-distributed hash code — a bad one degrades toward O(n).
· Dictionary iteration order is not guaranteed — never rely on it.

Key Takeaway

A Dictionary<TKey,TValue> is a hash table — it computes each key's hash code, maps that to a bucket, and jumps straight there instead of scanning.
This is why lookups stay close to O(1) on average as the dictionary grows, instead of the O(n) you'd get scanning a list.
Two different keys landing in the same bucket is a collision — normal, expected, and handled by chaining a few entries together within that bucket.
Equals() only ever needs to run against the small number of candidates in the correct bucket — the hash code already did the heavy lifting.
A poorly-written GetHashCode() — one that clusters many different keys into the same few buckets — silently degrades average O(1) performance toward O(n), which is exactly why the next lesson matters.

Check Your Understanding

You've seen exactly how a dictionary lookup avoids scanning. Let's check your understanding.

1. Why does a Dictionary<TKey,TValue> lookup stay fast even as the number of entries grows into the millions?

A) It secretly scans every entry, but modern CPUs are fast enough that you don't notice
B) It computes the key's hash code, jumps directly to the corresponding bucket, and only compares against the handful of entries in that one bucket
C) It keeps a sorted copy of every key and uses binary search
D) It only stores the most recently added entries in memory

Show answer

Correct: B

Why B is correct: As shown in "How It Works," the hash code lets the dictionary calculate exactly where to look, so it never touches unrelated buckets — this is what keeps lookup time from growing as the dictionary grows.

Why A is incorrect: No full scan happens at all — that's precisely the O(n) behavior a hash table exists to avoid.

Why C is incorrect: That describes a sorted, tree-like structure such as SortedDictionary<TKey,TValue>, which is O(log n), not the hash-bucket approach Dictionary<TKey,TValue> actually uses.

Why D is incorrect: A dictionary retains every entry you add — it doesn't discard older ones on its own.

Reinforcement: The hash code replaces "search" with "calculate," which is exactly what makes O(1) average lookups possible.

2. Two different keys happen to produce the same hash code and land in the same bucket. What does this mean?

A) This is a bug — a correctly implemented dictionary should never let this happen
B) This is a normal, expected collision — the dictionary handles it by chaining both entries in that bucket and using Equals() to tell them apart
C) The dictionary will throw an exception
D) One of the two keys will be silently discarded

Show answer

Correct: B

Why B is correct: As covered in "Under the Hood," collisions are expected — there are far more possible keys than 32-bit hash codes — and .NET's dictionary handles them by chaining entries within a bucket, then using Equals() to identify the actual match.

Why A is incorrect: Collisions are a normal, anticipated part of hashing, not evidence of a broken implementation.

Why C is incorrect: A collision is handled gracefully — it doesn't cause an exception, just a slightly longer (but still small) comparison within one bucket.

Why D is incorrect: Both entries remain fully present and retrievable — sharing a bucket doesn't cause data loss.

Reinforcement: A collision is not the same as a bug — it's an expected event that a well-implemented hash table is specifically designed to handle cheaply.

3. What happens if a dictionary key's fields (which its GetHashCode() depends on) are mutated after the key has already been added to the dictionary?

A) Nothing — the dictionary automatically re-buckets the entry whenever it detects a change
B) The entry can become effectively unfindable, because the dictionary computes a new bucket location from the mutated key, while the entry itself is still sitting in the old bucket it was originally placed in
C) The dictionary throws a compile-time error
D) The value associated with the key is automatically deleted

Show answer

Correct: B

Why B is correct: As shown in "Common Mistakes," a dictionary has no way to know a key's hash-relevant fields changed — it only recomputes the bucket location at lookup time, using the key's current state, which no longer matches where the entry actually lives.

Why A is incorrect: Dictionaries have no mechanism to detect or react to field mutations on their keys — this is exactly why the problem occurs.

Why C is incorrect: This is a runtime behavioral issue, not something the compiler can detect — the code compiles fine and simply misbehaves at runtime.

Why D is incorrect: The entry isn't deleted — it's still stored, just unreachable through normal lookup because the dictionary is now searching in the wrong bucket.

Reinforcement: Dictionary keys should be effectively immutable — mutating hash-relevant state after insertion silently breaks lookups.

4. What does "O(1) on average" actually promise about dictionary lookup performance?

A) Every single lookup takes exactly the same, guaranteed amount of time, no matter what
B) Lookup time stays roughly flat as the dictionary grows, assuming a reasonably well-distributed hash function — it is not a hard worst-case guarantee against all collisions
C) The dictionary can hold at most one entry
D) Lookups are always faster than any other collection type, in every situation

Show answer

Correct: B

Why B is correct: As explained in "Common Confusion," "average" is the key word — it describes typical behavior given a well-distributed hash function, not an absolute per-lookup guarantee, and heavy collisions can degrade performance toward O(n) in a poor implementation.

Why A is incorrect: Individual lookup times can vary (a bucket with several chained entries takes marginally longer than an empty one) — O(1) describes the overall scaling trend, not identical timing every time.

Why C is incorrect: This has nothing to do with Big-O notation or dictionary capacity — a dictionary can hold as many entries as memory allows.

Why D is incorrect: Other structures can be faster in specific scenarios (e.g. a plain array with a known index), and a badly-hashed dictionary can even be slower than expected — O(1) average is a strong guarantee, not a universal one.

Reinforcement: "Average constant time" describes how performance scales with size, not a promise that every operation takes identical, guaranteed time.

You now understand exactly how Dictionary<TKey,TValue> achieves its speed. Next: writing a correct Equals/GetHashCode pair on your own types — the contract every hash-based collection depends on.

What Is It?

The Simple Explanation

The Technical Definition

Why Does It Exist?

The Problem

The Solution

Big Picture

How It Works

Simple Example

Real-World Example

Analogy

Under the Hood

Common Confusion

1. "O(1)" doesn't mean "instant" or "guaranteed" — it means "average constant time"

2. A hash code collision is not the same thing as two keys being "equal"

3. Buckets don't preserve insertion order — that's why Dictionary<TKey,TValue> iteration order isn't guaranteed

Common Mistakes

Mistake 1 — Assuming dictionary iteration preserves insertion order

Mistake 2 — Mutating a key's fields after it's been used as a dictionary key

Mistake 3 — Assuming every custom class already has a "good" hash code

When Should I Use It?

Reach for a Dictionary when

Reconsider when

Mental Model

Key Takeaway

Check Your Understanding

3. Buckets don't preserve insertion order — that's why `Dictionary<TKey,TValue>` iteration order isn't guaranteed