A Dictionary-based cache in a .NET service gets slower and slower and sometimes "loses" entries that were definitely added. What could be wrong with the key type, and how would you debug and fix it?

1. What a constant hash does

Good hash:                       Constant hash (always 7):
bucket 0: A                      bucket 0:
bucket 1: B → F                  bucket 1:
bucket 2: C                      ...
bucket 3: D                      bucket 7: A → B → C → D → E → F → ... (n items)
bucket 4: E                      lookups compare against every key: O(n)

Inserting n items becomes O(n²) in total because each insert checks the chain for duplicates.

2. Mutable key failure

key = new OrderKey { Region = "AU", Id = 1 };   hash → bucket 2
dict.Add(key, order);
key.Region = "NZ";                               hash would now → bucket 5
dict.ContainsKey(key);   → looks in bucket 5 → not found
// The entry is still in bucket 2, unreachable, and still holds memory.

3. Inconsistent comparers

// Equals ignores case but GetHashCode does not
public override bool Equals(object? o) => o is Sku s && string.Equals(Code, s.Code, StringComparison.OrdinalIgnoreCase);
public override int GetHashCode() => Code.GetHashCode();   // ✘ "abc" and "ABC" hash differently
// Fix: StringComparer.OrdinalIgnoreCase.GetHashCode(Code)

4. Concurrency

Dictionary<TKey,TValue> supports multiple concurrent readers only if there are no writers. A write during a read or another write can corrupt buckets/entries. Symptoms are non-deterministic and can include infinite loops. Options:

5. How to debug

1. Profile: CPU samples inside Dictionary.FindValue/TryInsert with growing counts point to collisions.
2. Measure distribution: group keys by GetHashCode() and count distinct hashes vs keys.
3. Review the key type: Is it immutable? Are Equals and GetHashCode based on the same fields and the same comparison rules? Does it implement IEquatable<T>?
4. Check sharing: Is the dictionary static or a singleton? Who writes to it? Take a memory dump and look at threads stuck in dictionary methods.
5. Write a property test: for random pairs, a.Equals(b) implies equal hashes.

6. Try it yourself

1. Insert 100,000 keys with GetHashCode() => 1 and time it.
2. Reproduce a mutable key miss.
3. Run 8 threads writing to a plain Dictionary in a loop (in a test project) and observe exceptions or hangs; then switch to ConcurrentDictionary.

// Diagnose hash quality for a set of real keys
static void ReportHashQuality<T>(IEnumerable<T> keys, IEqualityComparer<T>? comparer = null)
{
    comparer ??= EqualityComparer<T>.Default;
    var list = keys.ToList();
    var groups = list.GroupBy(k => comparer.GetHashCode(k!)).ToList();
    Console.WriteLine($"keys: {list.Count:N0}, distinct hashes: {groups.Count:N0}, " +
                      $"largest collision group: {groups.Max(g => g.Count()):N0}");
}

// Before: mutable class, weak hash, shared Dictionary without locks
public class ClientKey
{
    public Guid TenantId { get; set; }
    public string ApiKey { get; set; } = "";
    public override bool Equals(object? o) => o is ClientKey k && k.TenantId == TenantId && k.ApiKey == ApiKey;
    public override int GetHashCode() => TenantId.GetHashCode();   // all keys of a tenant collide
}
private static readonly Dictionary<ClientKey, Counter> Counters = new();   // written from many threads

// After: immutable value key + thread-safe map + immutable value
public readonly record struct ClientKey(Guid TenantId, string ApiKey);  // IEquatable<ClientKey>, combined hash
public sealed record Counter(long Count);

private static readonly ConcurrentDictionary<ClientKey, Counter> SafeCounters = new();

public Counter Hit(Guid tenant, string apiKey) =>
    SafeCounters.AddOrUpdate(new ClientKey(tenant, apiKey),
        static _ => new Counter(1),
        // May run more than once under contention, so it must not mutate shared state:
        // it returns a new value and ConcurrentDictionary keeps the one that wins.
        static (_, existing) => existing with { Count = existing.Count + 1 });

// Property-style test: equal keys must have equal hashes
[Theory]
[InlineData("abc", "ABC")]
[InlineData("Sku-1", "sku-1")]
public void Equal_keys_have_equal_hashes(string a, string b)
{
    var x = new Sku(a);
    var y = new Sku(b);
    Assert.True(x.Equals(y));
    Assert.Equal(x.GetHashCode(), y.GetHashCode());
}