👾 Хеш-таблицы: немного теории и кода часть 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 и может использоваться как индекс ячейки.
Телеграм канал EasyProger - https://t.me/easyprogers