Как обеспечить корректную работу Dictionary в C# при коллизиях хэш-кодов?

Коллизия хэш-кодов — это ситуация, когда разные ключи дают одинаковый хэш. Dictionary<TKey, TValue> в C# обрабатывает это внутренне с помощью метода разрешения коллизий цепочками (separate chaining). Задача разработчика — минимизировать коллизии, правильно реализовав методы GetHashCode() и Equals() для пользовательских типов ключей.

Правила для создания хорошего ключа:

1. Equals() и GetHashCode() должны быть согласованы: Если два ключа равны по Equals(), они обязаны возвращать одинаковый GetHashCode(). Обратное не обязательно — одинаковый хэш не гарантирует равенство.
2. Хэш-код должен быть стабильным: Он не должен меняться за время жизни объекта, пока тот используется как ключ в словаре. Изменение ключа после добавления "сломает" словарь.
3. Хэш-функция должна давать равномерное распределение: Это минимизирует коллизии и сохраняет производительность словаря близкой к O(1).

Пример правильной реализации ключевого класса:

public class CustomerKey : IEquatable<CustomerKey>
{
    public int RegionId { get; } // Свойства только для чтения!
    public string Code { get; }  // Неизменяемость гарантирует стабильность хэша.

    public CustomerKey(int regionId, string code)
    {
        RegionId = regionId;
        Code = code;
    }

    // Реализация IEquatable<T> для типизированного сравнения (быстрее).
    public bool Equals(CustomerKey other)
    {
        if (other is null) return false;
        return RegionId == other.RegionId && Code == other.Code;
    }

    // Переопределение Object.Equals.
    public override bool Equals(object obj) => Equals(obj as CustomerKey);

    // Хэш-код, вычисляемый из всех полей, участвующих в сравнении в Equals.
    public override int GetHashCode()
    {
        // Используем HashCode.Combine для простоты и хорошего распределения.
        return HashCode.Combine(RegionId, Code);
    }
}

// Использование:
var dict = new Dictionary<CustomerKey, CustomerData>();
dict.Add(new CustomerKey(1, "ABC"), new CustomerData());

Что произойдет при коллизии: Внутри Dictionary для каждой корзины (bucket), определяемой хэш-кодом, хранится связный список пар ключ-значение. При поиске сначала вычисляется хэш, находится корзина, а затем в списке этой корзины выполняется линейный поиск с использованием Equals() для нахождения точного ключа. Качественный GetHashCode() сводит этот линейный поиск к минимуму.