C# Dictionary: Hashing, Lookups, and Practical Examples

Are you sure your dictionary lookup is always O(1)? With a poor comparer or a mutable key it can degrade fast. Let me show you how to keep it quick and safe with code you can paste into your project today.

Why you should care

Dictionary<TKey,TValue> is the go‑to map in .NET. It stores pairs by key and gives you near constant‑time lookup, insert, and remove. This speed comes from a hash table under the hood. In short:

• Each key is turned into an integer (hash code).
• That number picks a bucket (index in an internal array).
• Items in the same bucket are linked together (collision chain).
• Lookup checks only that bucket’s chain instead of the whole collection.

When the table gets crowded, it grows and rehashes items into a bigger array. If you give it a good comparer and sane capacity, it screams. If not, it crawls.

Tiny diagram

Bucket index: 0      1      2      3      4      5
              |      |      |      |      |      |
              v      v      v      v      v      v
             [ ] -> [k2]   [ ]   [k9]->[k21]   [k5]

• [ ] means empty bucket.
• [k9]->[k21] means two keys landed in the same bucket (collision).

Big‑O at a glance

• Average case: Add, TryGetValue, Remove ≈ O(1).
• Worst case (bad hashing or all keys collide): O(n).
• Count is O(1).
• Iteration over all entries is O(n).

First steps: the right way to read, write, and check

var stock = new Dictionary<string, int>(StringComparer.OrdinalIgnoreCase)
{
    ["apples"] = 10,
    ["oranges"] = 5
};

// Add or update
stock["apples"] += 2;        // indexer updates
stock["bananas"] = 3;        // creates new key if missing

// Safer add (no throw if exists)
bool added = stock.TryAdd("pears", 4);

// Fast read pattern
if (stock.TryGetValue("apples", out int qty))
{
    Console.WriteLine($"Apples in stock: {qty}");
}

// Removal
stock.Remove("oranges");

// Iteration (order is not guaranteed across runs)
foreach (var (name, count) in stock)
{
    Console.WriteLine($"{name}: {count}");
}

Tips:

• Prefer TryGetValue over ContainsKey + indexer. It does one lookup, not two.
• Pass an appropriate comparer, e.g. StringComparer.OrdinalIgnoreCase for case‑insensitive keys.

Equality and hash codes: the make‑or‑break part

A dictionary trusts two facts about your key type TKey:

1. If Equals(a, b) is true, then GetHashCode(a) == GetHashCode(b).
2. The hash code should be stable while the key is in the dictionary.

Custom key example (struct) with correct equality

public readonly struct ProductKey : IEquatable<ProductKey>
{
    public string Sku { get; }
    public string Country { get; }

    public ProductKey(string sku, string country)
    {
        Sku = sku ?? throw new ArgumentNullException(nameof(sku));
        Country = country ?? throw new ArgumentNullException(nameof(country));
    }

    public bool Equals(ProductKey other)
        => StringComparer.OrdinalIgnoreCase.Equals(Sku, other.Sku)
           && StringComparer.OrdinalIgnoreCase.Equals(Country, other.Country);

    public override bool Equals(object? obj)
        => obj is ProductKey other && Equals(other);

    public override int GetHashCode()
        => HashCode.Combine(
            StringComparer.OrdinalIgnoreCase.GetHashCode(Sku),
            StringComparer.OrdinalIgnoreCase.GetHashCode(Country));
}

Usage:

var prices = new Dictionary<ProductKey, decimal>();
prices[new ProductKey("SKU-42", "us")] = 9.99m;
prices[new ProductKey("SKU-42", "US")] += 1.00m; // same key thanks to ignore‑case rules

A broken key (mutable) and how it bites

public sealed class BadKey
{
    public int Id; // mutable!
    public override bool Equals(object? obj) => obj is BadKey b && Id == b.Id;
    public override int GetHashCode() => Id; // depends on mutable field
}

var map = new Dictionary<BadKey, string>();
var key = new BadKey { Id = 1 };
map[key] = "hello";
key.Id = 2; // changed after insert

// Now the key lives in the wrong bucket. Lookup fails:
Console.WriteLine(map.ContainsKey(key)); // false

Rule: keys must be effectively immutable while stored. If your type is mutable, keep the fields used for equality readonly.

Picking the right comparer for strings

• StringComparer.Ordinal – fast, binary comparison, case‑sensitive.
• StringComparer.OrdinalIgnoreCase – fast and case‑insensitive (good default for keys users type).
• StringComparer.CurrentCulture – culture‑aware (slower, rarely needed for keys).

var users = new Dictionary<string,Guid>(StringComparer.OrdinalIgnoreCase);

Avoid ToLower()/ToUpper() before insert or lookup. Comparers do the right thing without extra allocations.

Capacity, growth, and memory

Creating a dictionary with the right initial capacity avoids repeated resizes.

int expected = 50_000;
var map = new Dictionary<int, string>(capacity: expected);

// .NET 6+
map.EnsureCapacity(expected);

// later, after removals
map.TrimExcess();

Notes:

• EnsureCapacity helps when you add in batches.
• Load factor is handled for you; when the table is too full, it grows and rehashes.
• TrimExcess packs the table to save memory after many deletions.

Fast read pattern: numbers that speak

Why avoid ContainsKey + indexer?

// Slower (two lookups)
if (map.ContainsKey(k))
{
    var v = map[k];
}

// Faster (one lookup)
if (map.TryGetValue(k, out var v))
{
    // use v
}

In my tests on a mid‑range laptop, TryGetValue shaved 30–40% from lookup time in a tight loop versus ContainsKey + indexer. Your numbers will vary, but one lookup is always better than two.

Safe updates with TryAdd, Add, and indexer

• Add(k, v) throws if the key exists.
• dict[k] = v overwrites or creates.
• TryAdd(k, v) returns false if the key exists.

if (!cache.TryAdd(key, value))
{
    // someone set it already
}

Iteration rules and gotchas

• You can iterate keys or values with foreach.
• You cannot modify the dictionary while iterating (write operations throw).
• Order is an implementation detail; do not rely on it for logic that needs stable order across runs.

foreach (var (k, v) in map.ToArray()) // copy to allow safe mutation
{
    if (ShouldRemove(k, v))
        map.Remove(k);
}

Threading: when you have many writers

Dictionary<TKey,TValue> is not safe for concurrent writes. For shared state, either:

1. Protect it with a lock:

private readonly object _gate = new();
private readonly Dictionary<string,int> _scores = new(StringComparer.OrdinalIgnoreCase);

public int AddScore(string user, int delta)
{
    lock (_gate)
    {
        _scores.TryGetValue(user, out int s);
        _scores[user] = s + delta;
        return _scores[user];
    }
}

2. Or use ConcurrentDictionary<TKey,TValue>:

var cd = new ConcurrentDictionary<string,int>(StringComparer.OrdinalIgnoreCase);
int newScore = cd.AddOrUpdate("anna", 10, (_, old) => old + 10);
int result = cd.GetOrAdd("peter", _ => ComputeInitial());

If you only have many readers and single writer guarded by a lock, a plain dictionary is fine.

Real use cases you can drop in today

1) Counting frequency of tokens

static Dictionary<string,int> CountWords(IEnumerable<string> words)
{
    var counts = new Dictionary<string,int>(StringComparer.OrdinalIgnoreCase);
    foreach (var w in words)
    {
        if (counts.TryGetValue(w, out int c)) counts[w] = c + 1;
        else counts[w] = 1;
    }
    return counts;
}

2) Index by id for O(1) lookups

var byId = users.ToDictionary(u => u.Id); // requires Id unique
var user = byId.TryGetValue(request.UserId, out var u) ? u : null;

3) Join two datasets quickly

// orders: IEnumerable<Order>  (Order has CustomerId)
// customers: IEnumerable<Customer> (Customer has Id)
var customersById = customers.ToDictionary(c => c.Id);

var enriched = orders.Select(o =>
{
    customersById.TryGetValue(o.CustomerId, out var c);
    return new { o.Id, o.Total, CustomerName = c?.Name };
});

4) Simple LRU cache (compact and fast)

public sealed class LruCache<TKey,TValue>
{
    private readonly int _capacity;
    private readonly Dictionary<TKey, LinkedListNode<(TKey Key, TValue Val)>> _map;
    private readonly LinkedList<(TKey Key, TValue Val)> _list = new();

    public LruCache(int capacity, IEqualityComparer<TKey>? cmp = null)
    {
        _capacity = capacity > 0 ? capacity : throw new ArgumentOutOfRangeException(nameof(capacity));
        _map = new Dictionary<TKey, LinkedListNode<(TKey, TValue)>>(capacity, cmp);
    }

    public bool TryGet(TKey key, out TValue value)
    {
        if (_map.TryGetValue(key, out var node))
        {
            _list.Remove(node);
            _list.AddFirst(node);
            value = node.Value.Val;
            return true;
        }
        value = default!;
        return false;
    }

    public void Set(TKey key, TValue value)
    {
        if (_map.TryGetValue(key, out var node))
        {
            node.Value = (key, value);
            _list.Remove(node);
            _list.AddFirst(node);
            return;
        }

        if (_map.Count == _capacity)
        {
            var last = _list.Last!;
            _map.Remove(last.Value.Key);
            _list.RemoveLast();
        }
        var newNode = new LinkedListNode<(TKey, TValue)>((key, value));
        _list.AddFirst(newNode);
        _map[key] = newNode;
    }
}

5) Group latest item per key

static Dictionary<string,Order> LatestOrderPerUser(IEnumerable<Order> orders)
{
    var last = new Dictionary<string,Order>(StringComparer.Ordinal);
    foreach (var o in orders)
    {
        if (!last.TryGetValue(o.UserId, out var prev) || o.CreatedAt > prev.CreatedAt)
            last[o.UserId] = o;
    }
    return last;
}

Working with value types and records

• Records already implement value‑based equality. Good default for keys composed of several fields.
• Small structs can be fine as keys (avoid large structs; copying cost matters).

public readonly record struct Point2D(int X, int Y);
var visited = new Dictionary<Point2D, bool>();
visited[new Point2D(3, 5)] = true;

Avoid these common traps

• Storing mutable keys. Values used in Equals/GetHashCode must not change.
• Using culture‑aware string rules for keys. Prefer ordinal comparers for speed and stability.
• Two lookups per read. Use TryGetValue.
• Tiny default capacity during bulk load. Pre‑size or call EnsureCapacity.
• Assuming order of iteration is stable. It is not a contract.
• Ignoring thread safety. Many writers require a lock or a concurrent collection.

Edge cases and advanced notes

• Resizing: growth is automatic and preserves correctness but costs time. Batch inserts benefit from pre‑sizing.
• Equals symmetry/transitivity: if you override, follow the rules or you’ll get hard‑to‑trace misses.
• Large keys: consider storing a compact key (e.g., stable id) instead of a large object.
• Read‑only maps: for static data, ReadOnlyDictionary wraps an existing dict; for high‑performance, System.Collections.Frozen.FrozenDictionary (when available) gives very fast reads for data that never changes.
• Compared to SortedDictionary: that one keeps keys ordered (tree based), with O(log n) operations. Use it when order by comparer is required.

Micro test you can run

using System;
using System.Collections.Generic;
using System.Diagnostics;

class Program
{
    static void Main()
    {
        var rnd = new Random(42);
        var dict = new Dictionary<int,int>(200_000);
        for (int i = 0; i < 200_000; i++) dict[i] = i;

        var keys = new int[1_000_000];
        for (int i = 0; i < keys.Length; i++) keys[i] = rnd.Next(0, 250_000);

        var sw = Stopwatch.StartNew();
        long sum = 0;
        foreach (var k in keys)
        {
            if (dict.TryGetValue(k, out int v)) sum += v;
        }
        sw.Stop();
        Console.WriteLine($"TryGetValue: {sw.ElapsedMilliseconds} ms, sum={sum}");

        sw.Restart();
        sum = 0;
        foreach (var k in keys)
        {
            if (dict.ContainsKey(k)) sum += dict[k];
        }
        sw.Stop();
        Console.WriteLine($"ContainsKey+indexer: {sw.ElapsedMilliseconds} ms, sum={sum}");
    }
}

Expect the first loop to be faster on most machines, sometimes by a large margin.

FAQ: common questions about Dictionary

Conclusion: keep lookups fast with the right keys and comparers

Use a proper comparer, keep key fields stable, and pre‑size when you can. Prefer TryGetValue for reads and TryAdd for safe writes. If many threads write at once, switch to a concurrent map. These small choices keep your code simple and your lookups quick.

What trick saved you from a slow lookup recently? Share it in the comments so others can learn too.