Hash table fundamentals and .NET Dictionary internals: buckets and entries, chaining, load and resizing, the GetHashCode/Equals contract, average vs worst-case cost, and hash flooding protection.
A hash table turns a key into an integer hash, maps it to a bucket (hash % bucketCount), and stores the entry there. Lookups compute the same hash, go straight to the bucket, and compare keys with Equals. Average cost is O(1); worst case (everything in one bucket) is O(n).
.NET's Dictionary<TKey,TValue> keeps an int[] buckets and an Entry[] entries array; colliding entries form a chain via a next index inside the entries array. When full, it resizes to roughly double (a prime size) and rehashes.
Contract: if a.Equals(b) then a.GetHashCode() == b.GetHashCode(), and a key's hash must not change while it is in the dictionary. Good hashes spread keys evenly.
key "SYD" ──GetHashCode()──► 0x5A3F91C2 ──% 7──► bucket 3 ──► compare keys ──► value
Dictionary<TKey, TValue>buckets (int[], 1-based index into entries, 0 = empty)
[0] [1] [2] [3] [4] [5] [6]
0 3 0 4 0 1 0
│ │ │
▼ ▼ ▼
#2 PER #3 BNE #0 MEL
│ next
▼
#1 SYD
entries (Entry[])
#0 { hashCode, next: -1, key: "MEL", value: .. } ← bucket 5
#1 { hashCode, next: -1, key: "SYD", value: .. } ← end of bucket 3's chain
#2 { hashCode, next: -1, key: "PER", value: .. } ← bucket 1
#3 { hashCode, next: 1, key: "BNE", value: .. } ← head of bucket 3's chain
entries, and link it at the head of the bucket's chain.Equals.entries is full (load factor 1.0), allocate the next prime of roughly double the size and rebuild the buckets from the stored hash codes.The load factor is entries ÷ buckets. With a good hash, chains average about one entry even at a load factor of 1.0, so lookups stay O(1). Clustering happens when the hash is poor (for example GetHashCode returning only an ID's low bits, or the same value for many keys): chains grow and lookups drift towards O(n). Open-addressing tables, which store entries in the bucket array itself and probe neighbouring slots, must resize earlier (around 0.7) because probe sequences lengthen rapidly as the table fills.
| Operation | Average | Worst case |
|---|---|---|
| Add / lookup / remove | O(1) | O(n) (all keys collide) |
| Resize | O(n), amortised away | |
| Enumerate | O(n), order not guaranteed |
A pricing service matched 200,000 incoming quotes against 50,000 products using products.First(p => p.Sku == quote.Sku), which is O(n) per quote: billions of comparisons in the worst case and a 40-second job. Building products.ToDictionary(p => p.Sku, StringComparer.OrdinalIgnoreCase) once and using TryGetValue made each match O(1). The job ran in 150 ms.
Checks one of the most important data structures and the .NET equality contract.
Green flags
Red flags
| Rule | Why |
|---|---|
| Equal objects must have equal hash codes | Otherwise lookup searches the wrong bucket and misses |
| Unequal objects may share a hash (collision) | Allowed; Equals resolves it |
| Hash must not change while the key is in the dictionary | The entry would be in the old bucket and become unfindable |
| Hash should be fast and well distributed | Clustering causes long chains |
Records and anonymous types generate value-based Equals/GetHashCode. For classes, override both together or use HashCode.Combine(a, b, c).
new Dictionary<string, T>(StringComparer.OrdinalIgnoreCase) makes keys case-insensitive; the comparer supplies both hash and equality.IEqualityComparer<T> for custom key semantics without changing the type.If attackers can choose keys (e.g. JSON property names, query strings), they can craft many strings with the same hash and turn O(1) into O(n), causing CPU denial of service. .NET randomises string hashing per process (Marvin hash). Dictionary<string, T> starts with a faster non-randomised comparer and switches to the randomised one if it detects too many collisions.
new Dictionary<K,V>(expectedCount) avoids rehashing.TryGetValue instead of ContainsKey + indexer; TryAdd; CollectionsMarshal.GetValueRefOrAddDefault for update-in-place counters.GetAlternateLookup<ReadOnlySpan<char>>() looks up string keys from spans without allocating strings.FrozenDictionary optimises for reads.| Separate chaining (.NET Dictionary) | Open addressing (linear/quadratic probing) | |
|---|---|---|
| Collisions | Chain via next index |
Probe next slots |
| Deletion | Easy | Needs tombstones |
| Locality | Good (entries array) | Very good |
| Load factor | Can approach 1 | Must stay lower (~0.7) |
GetHashCode returns 1 and insert 50,000 keys; time lookups vs a proper hash.ContainsKey.ContainsKey + indexer vs TryGetValue with BenchmarkDotNet.// Build the index once, then O(1) lookups
var bySku = products.ToDictionary(p => p.Sku, StringComparer.OrdinalIgnoreCase);
foreach (var quote in quotes)
{
if (bySku.TryGetValue(quote.Sku, out var product)) // one lookup, not ContainsKey + indexer
Match(quote, product);
}
// Counting without double lookups
var counts = new Dictionary<string, int>(StringComparer.Ordinal);
foreach (var word in words)
{
ref int count = ref CollectionsMarshal.GetValueRefOrAddDefault(counts, word, out _);
count++;
}
// Correct custom key: immutable, Equals and GetHashCode consistent
public readonly record struct RouteKey(string Origin, string Destination, DateOnly Date);
// records generate value equality and a combined hash
// Hand-written equivalent for a class
public sealed class FlightKey(string origin, string destination) : IEquatable<FlightKey>
{
public string Origin { get; } = origin;
public string Destination { get; } = destination;
public bool Equals(FlightKey? other) =>
other is not null &&
string.Equals(Origin, other.Origin, StringComparison.Ordinal) &&
string.Equals(Destination, other.Destination, StringComparison.Ordinal);
public override bool Equals(object? obj) => Equals(obj as FlightKey);
public override int GetHashCode() => HashCode.Combine(Origin, Destination);
}
Mistake: Searching a list with First or Where inside a loop when a dictionary would do.
Why it is wrong: Each search is O(n), so the loop becomes O(n × m).
Instead: Build a dictionary (or ToLookup for many values per key) once and use TryGetValue.
Mistake: Overriding Equals without GetHashCode (or the reverse).
Why it is wrong: Two equal keys produce different hashes, land in different buckets, and lookups silently miss or duplicates are added. No exception tells you.
Instead: Override both consistently, or use records and HashCode.Combine.
Mistake: Using mutable objects as keys and changing them after insertion. Why it is wrong: The entry stays in the bucket for its old hash, so it becomes unreachable but still uses memory. Instead: Use immutable keys (records, readonly structs, strings, IDs).
Mistake: Calling ContainsKey then the indexer.
Why it is wrong: It hashes and searches twice.
Instead: Use TryGetValue, TryAdd or GetValueRefOrAddDefault.
Mistake: Writing to a shared Dictionary from several threads.
Why it is wrong: A concurrent resize or insert can corrupt the chains, causing lost entries, exceptions or a thread spinning forever in a cyclic chain.
Instead: Use ConcurrentDictionary<TKey, TValue>, a lock, or build once and publish a FrozenDictionary.
Mistake: Relying on dictionary enumeration order.
Why it is wrong: It is unspecified and changes after removals reuse slots.
Instead: Sort explicitly, or use SortedDictionary or OrderedDictionary<TKey, TValue> when order matters.
A hash table trades memory for time: it gives O(1) average lookups as long as the hash function and the key contract hold. Most production bugs come from the contract (mutable keys, inconsistent Equals/GetHashCode, culture-sensitive string comparison) or from unsafe sharing between threads, not from the structure itself.
| Situation | Choice | Reason |
|---|---|---|
| Single-threaded or request-scoped | Dictionary<TKey, TValue> |
Fastest general-purpose map |
| Shared, many writers | ConcurrentDictionary<TKey, TValue> |
Fine-grained locking, lock-free reads |
| Built once at startup, read constantly | FrozenDictionary<TKey, TValue> |
Slower to build, faster lookups, safe to share |
| Snapshots that change occasionally | ImmutableDictionary swapped with Interlocked.Exchange |
Readers never see partial updates |
| Attacker-controlled string keys | Default string comparer (randomised) | Resists hash flooding |
I also think about who controls the keys. With attacker-controlled keys, worst-case behaviour becomes a denial-of-service risk, which is why .NET randomises string hashes. For hot paths I avoid double lookups, pre-size, choose ordinal comparers, and measure. When an O(n) scan shows up in a profile inside a loop, a dictionary is usually the cheapest big win available.
Likely causes, in order:
GetHashCode (e.g. returns 0, or hashes only a low-variety field): all keys collide, chains grow, lookups become O(n), so it gets slower as it grows.Equals/GetHashCode inconsistency: equal keys produce different hashes (e.g. case-insensitive Equals with case-sensitive hash).Dictionary from multiple threads, which can corrupt the internal arrays, lose entries, or even cause infinite loops.Debug by measuring hash distribution, checking the key type's Equals/GetHashCode and mutability, and looking for shared dictionaries without locks. Fix with immutable keys (records), consistent comparers, and ConcurrentDictionary or proper locking.
A map (associative array, dictionary) stores key → value pairs with unique keys. Choose the implementation by access pattern:
Dictionary<K,V>: hash table, O(1) average, unordered. The default.SortedDictionary<K,V>: red-black tree, O(log n), sorted by key, fast inserts/removes.SortedList<K,V>: two sorted arrays, O(log n) lookup but O(n) insert/remove; compact, indexable. Good for small or build-once sorted maps.OrderedDictionary<K,V> (.NET 9+): keeps insertion order with index access.ConcurrentDictionary<K,V>: thread-safe, lock-free reads.FrozenDictionary<K,V> (.NET 8+): built once, fastest reads.ImmutableDictionary<K,V>: immutable snapshots with cheap modified copies.ILookup<K,V> / Dictionary<K, List<V>>: multi-map (one key, many values).A set stores unique items and answers "is X in it?" quickly.
HashSet<T>: hash table without values. Add, Remove, Contains are O(1) average. No ordering.SortedSet<T>: red-black tree. O(log n) operations, items kept sorted, supports Min, Max and GetViewBetween ranges.FrozenSet<T> (.NET 8+): built once, optimised for fast reads; immutable.ImmutableHashSet<T>: immutable with cheap "modified copies", for snapshot-style sharing.Set algebra: UnionWith, IntersectWith, ExceptWith, SymmetricExceptWith, IsSubsetOf, Overlaps, SetEquals. The biggest everyday win is replacing List.Contains (O(n)) in loops with HashSet.Contains (O(1)).
How to tell it (STAR)
**S:** Our [pricing batch] took [40 seconds] and sometimes overlapped the next run. **T:** I was asked to make it reliable. **A:** The profiler showed a linear search for each quote across [50,000] products. I built a case-insensitive dictionary keyed by SKU once per run and used `TryGetValue`. **R:** The job dropped to [150 ms], CPU usage became negligible, and we added production-sized performance tests to catch similar regressions.
Last updated 23 Oct 2026.