Хеш-таблицы: немного теории и кода часть 1⁠⁠

Хеш-таблица — это структура данных, которая хранит пары «ключ → значение» и позволяет почти мгновенно находить элемент по ключу. В отличие от обычного массива, где индекс — это готовое число 0, 1, 2 и т.д., в хеш-таблице индекс для нас считает специальная функция — хеш-функция.

По сути, у нас есть:
1️⃣ Массив ячеек, куда кладём значения.
2️⃣ Хеш-функция, которая берет ключ (число, строку, структуру) и превращает его в индекс этого массива.

Результат работы хеш-функции называется хеш-кодом — это «адрес» в таблице, где лежит наше значение. Когда нужно что‑то найти, мы снова берём ключ, прогоняем его через хеш-функцию и сразу прыгаем в нужную ячейку, без перебора всего массива. Если повезло с хеш-функцией и размером таблицы, доступ к данным получается очень быстрым.

🔢 Разбор кода: как считается хеш

Разберём простой пример на C#, который считает хеш-код для массива байтов и превращает его в индекс хеш-таблицы.

HashSize возвращает размер таблицы как степень двойки: 2n2n. Это удобно, потому что с размером вида 2ⁿ можно эффективно «укладывать» хеш в диапазон индексов с помощью побитовых операций, а не через медленное деление.

HashMask из размера делает маску. Если размер таблицы 2n2n, то маска будет 2n−12n−1 — это число, у которого в двоичном виде младшие n битов равны 1. Побитовое & с такой маской «обрезает» лишние биты хеша и даёт число от 0 до 2n−12n−1. Именно так из большого хеш-кода получают индекс:

Goat — это хеш-функция. Она идёт по всем байтам входного массива key и «замешивает» их в переменную hash:

• добавляет текущий байт,

• делает сдвиги влево и вправо,

• применяет XOR.

Такие операции нужны, чтобы биты исходных данных хорошо перемешались, и маленькое изменение входа давало сильно другой хеш. В конце функция применяет маску HashMask(bits) и возвращает уже готовый индекс для хеш-таблицы с размером 2bits2bits.

Здесь берётся массив snowflake из long и превращается в «сырой» массив байтов snowflakeBytes. Buffer.BlockCopy просто копирует байты из одного массива в другой, не меняя их содержимое. Потом этот байтовый массив отправляется в Goat, которая считает хеш-код всей последовательности.

Параметр bits = 17 означает, что таблица рассчитана на размер 217217 элементов, а результат code уже лежит в диапазоне от 0 до 131071 и может использоваться как индекс ячейки.