C# Dictionary: Internal Structure and Resizing

This article explores the inner workings of Dictionary<TKey, TValue> in .NET, detailing how it stores data and expands under the hood. You will learn about the foundational dual-array layout used for collision resolution, how key lookups map to specific memory locations, and the step-by-step process the runtime executes when resizing and rehashing the dictionary to accommodate new elements.

The Internal Data Structure

The .NET Dictionary<TKey, TValue> is implemented as a hash table using a technique known as separate chaining via array indices. Unlike classic chaining implementations that use allocated linked-list nodes, the .NET dictionary achieves high cache locality and avoids garbage collection overhead by keeping all nodes inside contiguous arrays.

Internally, the dictionary is driven by two primary arrays and several supporting fields:

  • int[] _buckets: An array where each element stores a 1-based index (stored internally as 0-based index + 1, or -1 when empty) pointing to the head of a chain in the entries array.
  • Entry[] _entries: An array that holds the actual key-value data and collision chain metadata.
  • int _count: The number of valid items in the dictionary.
  • int _freeList: The index of the first available slot created by removed elements.
  • int _freeCount: The number of removed elements available for reuse.

Each element in the _entries array is a struct defined roughly as follows:

private struct Entry
{
    public uint HashCode;
    public int Next;
    public TKey Key;
    public TValue Value;
}
  • HashCode: The cached 31-bit positive hash code of the key, preventing redundant calls to GetHashCode().
  • Next: The index of the next entry in the same bucket collision chain, or -1 if it is the end of the chain.
  • Key and Value: The stored pair.

How Insertion and Lookup Work

When an item is added or retrieved:

  1. Hash Generation: The dictionary invokes the key's IEqualityComparer<TKey>.GetHashCode(key) to produce a 32-bit signed integer. The runtime casts or masks this to a uint to eliminate negative values.
  2. Bucket Mapping: The dictionary maps the hash code to a bucket index using the modulo operation: \[\text{bucketIndex} = \text{hashCode} \pmod{\text{\_buckets.Length}}\] (Note: Modern .NET Core / .NET 5+ versions optimize this operation using fast multiplication rather than native integer division).
  3. Traversal: The value in _buckets[bucketIndex] yields the index of the first Entry in _entries.
  4. Comparison: The runtime walks through the chain following the Next indices. For each entry, it first compares the cached HashCode (a fast integer comparison) and, if matching, calls IEqualityComparer<TKey>.Equals(entry.Key, key).
  5. Storage: For insertions, if the key is not found, the item is placed into the next available slot—either reclaimed from _freeList or appended at _count—and the new entry becomes the new head of the bucket chain.

The Resizing Mechanism

A dictionary cannot grow indefinitely without expanding its backing arrays. Resizing is triggered during an Add operation when _entries is full (_count == _entries.Length) and there are no free slots (_freeCount == 0).

The resize routine follows these distinct phases:

1. Determining the New Capacity

The dictionary requests a new capacity that is at least twice the current size. To reduce hash clustering and ensure an even distribution across buckets, the runtime uses the HashHelpers.GetPrime method to select the smallest prime number that is larger than double the current size.

2. Allocating New Arrays

Once the new prime capacity is determined:

  • A new _buckets array is allocated with the new prime length and initialized with -1 (indicating empty chains).
  • A new _entries array is allocated with the matching capacity.

3. Copying and Rehashing

Because bucket assignment relies on the total number of buckets via the modulo operation, altering the size of _buckets invalidates all existing bucket mappings. However, because each entry caches its original HashCode, the dictionary does not re-invoke GetHashCode() on the keys.

Instead, the dictionary executes a fast rehashing loop:

  1. Existing entries are copied into the new _entries array.
  2. The dictionary iterates through every valid entry in the copied array.
  3. It recalculates the bucket index: newBucket = entry.HashCode % newBuckets.Length.
  4. It updates entry.Next to point to whatever index is currently at newBuckets[newBucket].
  5. It sets newBuckets[newBucket] to the entry's current array index.

This rebuilds the collision chains inside the new bucket array in \(O(N)\) time.

Performance Impact

While resizing is an \(O(N)\) operation, it occurs exponentially less frequently as the collection grows, preserving an amortized \(O(1)\) time complexity for insertions. If the final collection size is known in advance, passing the expected capacity to the Dictionary<TKey, TValue>(int capacity) constructor avoids all intermediate allocations, rehashing cycles, and garbage collector pressure.