Хеш и хеш-таблицы

Сначала главное

Хеш — это результат работы хеш-функции. Она берёт любые входные данные и превращает их в строку фиксированной длины.

Например, было слово:

дата инженер

После хеширования получаем:

MD5 -> f68037967d4e895df65c58377cc0f1bf
SHA-256 -> a3c013642e73253c940dcf2268b6c4eb22cd76dcabad7cb9373635b94fdbaea5

Важно:

одно и то же значение при одной и той же функции даёт один и тот же хеш;
если изменить хотя бы одну букву, хеш будет уже совсем другим;
длина результата фиксирована для конкретного алгоритма.

Хеширование и шифрование — это не одно и то же

Очень частая путаница:

шифрование нужно, чтобы данные можно было потом расшифровать обратно ключом;
хеширование нужно, чтобы получить отпечаток значения, а не спрятать его для обратного восстановления.

Простой пример:

пароль можно зашифровать и потом расшифровать;
пароль можно захешировать, и тогда хранится не сам пароль, а его отпечаток.

Когда пользователь вводит пароль:

система снова считает хеш;
сравнивает его с тем, что лежит в базе;
если совпало, значит пароль правильный.

Можно ли разхешировать?

В нормальном смысле слова — нет.

Хеш-функция работает в одну сторону:

из строки получить хеш легко;
из хеша восстановить исходную строку нельзя обычной обратной операцией.

Но есть важный нюанс:

если исходное значение простое и популярное, его могут угадать перебором;
поэтому для паролей просто MD5 использовать нельзя;
для паролей применяют bcrypt, scrypt, Argon2, плюс salt.

То есть:

разхешировать нельзя;
подобрать исходное значение иногда можно, если оно слабое.

Что такое хеш-таблица

Хеш-таблица — это структура данных, где по ключу быстро находится значение.

Идея очень простая:

берём ключ, например "apple";
считаем его хеш;
по этому хешу определяем, в какую ячейку положить значение;
потом по тому же ключу снова считаем хеш и сразу идём в нужное место.

Из-за этого средний поиск обычно называют O(1).

Это не значит "всегда одна операция". Это значит, что в среднем поиск очень быстрый и не зависит линейно от числа элементов.

Пример со словарём

Обычный словарь в программировании можно представить так:

prices = {
    "apple": 120,
    "banana": 80,
    "milk": 95
}

Когда мы пишем:

prices["banana"]

интерпретатор не перебирает весь словарь слева направо. Он использует хеш ключа "banana" и быстро идёт в нужную область памяти.

Поэтому словари так удобны для:

поиска по ID;
хранения настроек;
справочников;
проверки "видели ли мы такой ключ раньше".

Очень простой пример "на ящиках"

Представь шкаф из 10 ящиков.

кладём ключ "cat";
считаем хеш;
получаем, например, число 123;
берём остаток 123 % 10 = 3;
значит, кладём значение в ящик номер 3.

Потом ищем "cat":

снова считаем хеш;
снова получаем ящик 3;
сразу идём туда, а не смотрим все 10 ящиков подряд.

Именно на этой идее и работают хеш-таблицы.

Почему поиск называют O(1)

Если у тебя:

список из миллиона элементов, поиск может идти долго;
хеш-таблица, ты почти сразу прыгаешь в нужную корзину.

Поэтому часто говорят:

поиск в массиве без структуры: O(n)
поиск в хеш-таблице в среднем: O(1)

Но нужно помнить про коллизии. Если коллизий много, производительность ухудшается.

Что такое коллизия

Коллизия — это ситуация, когда разные ключи попадают в одну и ту же ячейку.

Например:

hash("cat") % 10 = 3
hash("dog") % 10 = 3

Ключи разные, а ящик один и тот же.

Это нормально. Полностью избежать коллизий в реальных системах нельзя, потому что входных значений очень много, а корзин ограниченное число.

Где это используется у Data Engineer

1) Словари, map, set

Самый базовый пример:

Python dict
Python set
Java HashMap
Java HashSet

Везде идея одна: быстрый доступ по ключу.

2) Hash Join

Hash Join часто используется в базах данных и движках вроде Spark.

Идея:

берём меньшую таблицу;
строим по ключу хеш-таблицу в памяти;
идём по большой таблице;
для каждой строки быстро проверяем, есть ли такой ключ в хеш-таблице.

Пример:

Таблица клиентов:

customer_id	name
1	Анна
2	Борис
3	Вика

Таблица заказов:

order_id	customer_id	amount
101	2	500
102	1	700
103	2	300

Что делает Hash Join:

по маленькой таблице customers строит хеш-таблицу по customer_id;
затем читает orders;
для customer_id = 2 сразу находит Борис;
для customer_id = 1 сразу находит Анна.

За счёт этого join работает быстро, если хеш-таблица помещается в память.

3) Разбиение данных по хешу

Это тоже частый кейс:

распределение строк по сегментам в MPP-системах;
партиционирование по хешу;
распределение Kafka-сообщений по партициям по ключу.

Идея везде одна: посчитать хеш и по нему выбрать, куда отправить запись.

Где хеш полезен, а где нет

Хеш отлично подходит для:

точного поиска по ключу;
JOIN по равенству;
распределения данных;
дедупликации;
проверки целостности.

Хеш плохо подходит для:

поиска диапазона id BETWEEN 10 AND 100;
сортировки;
условий вида "все значения больше X".

Поэтому, например:

B-Tree хорош для диапазонов;
hash-структуры хороши для точного совпадения.

Маленький пример с SQL-мышлением

Если запрос такой:

SELECT *
FROM users
WHERE user_id = 42;

то hash-структура может подойти хорошо.

Если запрос такой:

SELECT *
FROM users
WHERE user_id BETWEEN 10 AND 100;

то hash уже неудобен, потому что у него нет естественного порядка значений.

Методы разрешения коллизий

Ниже как раз то, что обычно выносят в самый конец темы.

1) Chaining

Самый популярный и самый понятный способ.

Если в одну корзину попало несколько ключей, мы храним там список элементов.

Например, корзина 3 содержит:

("cat", 10)
("dog", 20)

Тогда поиск идёт так:

по хешу находим корзину 3;
внутри неё уже смотрим маленький список;
сравниваем ключи и берём нужный.

Плюс:

просто реализовать.

Минус:

если список разрастается, поиск внутри корзины замедляется.

2) Open Addressing

Идея другая: если ячейка занята, ищем другую свободную ячейку прямо в той же таблице.

Варианты:

Linear Probing
Проверяем следующую ячейку: i, потом i+1, потом i+2.
Quadratic Probing
Проверяем с шагами по квадратам: i+1, i+4, i+9.
Double Hashing
Используем вторую хеш-функцию, чтобы определить шаг.

Плюс:

не нужны дополнительные списки.

Минус:

сложнее удаление;
возможны кластеры из занятых ячеек.

Итог

Если совсем коротко:

хеш — это отпечаток значения;
хеширование и шифрование — разные вещи;
хеш-таблица нужна для быстрого поиска по ключу;
поэтому словари часто дают средний поиск O(1);
та же идея используется в Hash Join;
у хеш-таблиц есть коллизии, и их надо уметь разрешать.

Что такое Data Vault Индексы