Почему в хэш-таблицах ключ хранится в виде хэша?

Хранение ключа в виде хэша (точнее, использование хэш-кода ключа) — это фундаментальный принцип работы структур данных типа словаря (Dictionary<TKey, TValue>) или HashSet<T>, обеспечивающий высокую скорость операций поиска, вставки и удаления.

Как это работает?

1. При добавлении пары ключ-значение вызывается метод GetHashCode() ключа.
2. Полученный целочисленный хэш-код преобразуется в индекс внутри внутреннего массива (бакетов) структуры данных.
3. Значение сохраняется в ячейку (или цепочку ячеек), соответствующую этому индексу.

Преимущества использования хэша:

• Скорость доступа O(1) в среднем случае: Чтобы найти значение по ключу, не нужно перебирать все элементы. Достаточно вычислить хэш ключа, получить индекс и обратиться прямо к нужному бакету.
• Эффективное сравнение: Сначала сравниваются хэш-коды. Если хэши разные, ключи гарантированно разные, и дорогостоящее поэлементное сравнение (например, Equals) не требуется.

Пример на C#:

var inventory = new Dictionary<string, int>();
inventory.Add("apple", 10);
// 1. Вычисляется "apple".GetHashCode() -> получаем число, например, 12345.
// 2. Индекс = 12345 % (размер_внутреннего_массива).
// 3. Пара ("apple", 10) сохраняется в бакет под этим индексом.

int count = inventory["apple"]; // Поиск: тот же алгоритм ведёт прямо к нужному бакету.

Важные нюансы и требования:

• Коллизии: Разные ключи могут дать одинаковый хэш-код. Это решается методами разрешения коллизий (например, цепочки — хранение списка пар в одном бакете).
• Качество хэш-функции: Идеальная хэш-функция равномерно распределяет ключи по бакетам, минимизируя коллизии. Плохая хэш-функция сводит производительность к O(n).
• Контракт между GetHashCode() и Equals(): Если два объекта равны по Equals(), их GetHashCode() обязан возвращать одинаковое значение. Обратное не обязательно верно (коллизия).
• Нестабильность хэша: В .NET хэш-коды по умолчанию не гарантированы между разными запусками приложения (для безопасности). Для постоянных структур данных (сериализация) нужно использовать стабильные хэш-алгоритмы.