Зачем data engineer’у понимать хеш-функцию

Хеш-таблица — главная структура данных в работе data engineer’а. Каждый dict в Python, каждый HashMap в Spark, каждый shuffle-этап в распределённой системе опирается на одну математическую операцию: превратить ключ произвольной формы в число фиксированной длины. Эта операция называется хеш-функция.

Если хеш-функция плохая, dict перестаёт давать вам O(1) lookup. Join двух датафреймов перестаёт распределяться равномерно по партициям. Один воркер получает 80% данных, остальные простаивают. Время выполнения job вырастает в 10 раз. Поэтому знать, что делает hash() и какие у неё свойства, — не теория, а инженерная гигиена.

Определение

Хеш-функция — это детерминированная функция, принимающая на вход данные любого размера (строка, число, кортеж, целый объект) и возвращающая целое число фиксированной длины. В Python это число типа int со знаком, в 64-битной системе — от -2^63 до 2^63 - 1.

print(hash(42))                  # 42
print(hash("hello"))             # -7146178545157038398 (зависит от запуска)
print(hash((1, 2, 3)))           # 529344067295497451
print(hash(3.14))                # 322818021289917443
print(hash(True))                # 1
print(hash(None))                # 0

Обратите внимание: входы разной длины (число, короткая строка, кортеж) — выход всегда одно целое число. Это и есть «фиксированная длина output».

Три свойства, на которых всё держится

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

1. Detereministic — детерминированность

Один и тот же вход всегда даёт один и тот же выход. Без этого hash-таблица не может найти ключ, который сама же положила.

print(hash(42) == hash(42))           # True — всегда
print(hash("data") == hash("data"))   # True — внутри одного запуска
print(hash((1, 2)) == hash((1, 2)))   # True

Тонкость: для строк Python применяет рандомизацию при старте процесса (защита от

2. Uniform — равномерность

Хеши должны распределяться равномерно по всему пространству 64-битных чисел. Если функция «любит» определённые остатки от деления, dict с такими ключами выродится — все элементы попадут в несколько одних и тех же слотов.

# хороший хеш — биты выглядят случайными
xs = [hash(f"user_{i}") for i in range(10)]
for h in xs:
    print(bin(h & 0xFFFFFFFF))   # последние 32 бита — мешанина 0/1

Грубая проверка: возьмите 1000 ключей, посчитайте остатки от деления hash(k) % 8. Должно быть примерно по 125 в каждой группе. Если в одной группе 900, а в остальных по 10 — функция неравномерна.

3. Fast — быстрота

Hash должен считаться за O(1) для маленьких объектов и за O(длины) для больших (строк/байт). Без этого dict теряет смысл — если посчитать хеш дороже, чем пройти список линейно, hash-таблица проигрывает.

Для сравнения:

Как Python хеширует разные типы

Каждый встроенный тип в Python имеет свою стратегию хеширования. Знать их полезно, чтобы понимать, какие ключи быстрые, а какие — нет.

int — тождество

Для маленьких целых чисел hash(n) == n. Это самая дешёвая операция в Python:

print(hash(0))         # 0
print(hash(1))         # 1
print(hash(42))        # 42
print(hash(-1))        # -2 — единственное исключение, -1 зарезервировано
print(hash(2**62))     # 4611686018427387904

Для больших чисел (выше 2^61 - 1) применяется деление по модулю простого числа PyHASH_MODULUS = 2^61 - 1. То есть хеш всегда укладывается в 61 бит, а -1 зарезервирован как маркер ошибки.

str и bytes — SipHash 1-3

Строки хешируются за O(длины) — это занимает примерно 1 наносекунду на байт. SipHash рандомизируется при старте процесса:

# в одном запуске
print(hash("data"))    # например, 3741209284756723
print(hash("data"))    # то же самое в этом запуске

# в новом запуске python — другое число

Эту рандомизацию можно отключить через PYTHONHASHSEED=0, но в продакшене не надо — это снимает защиту от hash-flooding.

tuple — рекурсивный комбинатор

Кортеж хешируется через комбинацию хешей элементов. Псевдокод:

def tuple_hash(t):
    h = INITIAL_VALUE
    for x in t:
        h = combine(h, hash(x))   # XOR + умножение + сдвиг
    return h

Это означает: tuple из неhashable элементов (list, dict) сам не hashable. И стоимость хеширования tuple = сумма стоимостей хеширования его элементов плюс константа на каждый.

print(hash((1, 2, 3)))           # OK
print(hash((1, [2, 3])))         # TypeError: unhashable type: 'list'

Что не хешируется

Любой mutable тип в Python неhashable: list, dict, set. Логика проста: если объект можно изменить после вставки в dict, его хеш изменится, и dict потеряет ключ. Чтобы такого не было, hash() для mutable типов поднимает TypeError.

try:
    hash([1, 2, 3])
except TypeError as e:
    print(e)   # unhashable type: 'list'

Измерим — посчитаем хеши

Откройте python -m timeit и сравните стоимость хеширования разных типов:

python -m timeit -s "x = 42" "hash(x)"
# 50 000 000 loops, best of 5: 6.8 nsec per loop

python -m timeit -s "x = 'hello world'" "hash(x)"
# 20 000 000 loops, best of 5: 18.4 nsec per loop

python -m timeit -s "x = 'a' * 10000" "hash(x)"
# 50 000 loops, best of 5: 6.7 usec per loop

python -m timeit -s "x = (1, 2, 3)" "hash(x)"
# 10 000 000 loops, best of 5: 32.1 nsec per loop

Тут видно: для int хеш почти бесплатный, для строки 10KB — 6.7 микросекунды (один lookup в dict — миллион таких операций в секунду максимум).

Практический вывод: не делайте длинные строки ключами dict, если можно сделать короткие. UUID длиной 36 символов хешируется в 5 раз медленнее, чем int.

Деревьеподобный хеш для составных ключей

В реальной работе DE часто хешируют составные ключи — (user_id, event_type, date). Это всегда tuple, не строка с конкатенацией:

# плохо — лишний alloc + длинная строка для хеширования
key = f"{user_id}|{event_type}|{date}"

# хорошо — рекурсивный хеш по элементам, без alloc промежуточной строки
key = (user_id, event_type, date)

На миллионах операций разница достигает секунд. Tuple-ключи быстрее, чем строки-ключи, и читаемее в коде.

Попробуй сам

Откройте REPL (uv run python или python) и проверьте:

# 1. Стабильность hash для int в разных запусках
# Запустите python дважды и проверьте, одинаков ли hash(123)
hash(123)

# 2. Рандомизация для str
# Запустите python дважды и проверьте hash("data") — разные числа
hash("data")

# 3. Tuple из mixed типов — работает, если все элементы hashable
hash((1, "two", 3.0, (4, 5)))

# 4. Хеш float — попробуйте NaN
import math
hash(math.nan)   # 0 — спецзначение
hash(math.inf)   # 314159

# 5. Хеш списка — TypeError
try:
    hash([1, 2, 3])
except TypeError as e:
    print(e)

Проверьте ваше понимание:

• Почему hash(1) == hash(True) (оба = 1)? Подсказка — True это подкласс int.
• Почему hash(1.0) == hash(1)? Подсказка — для dict «1.0 и 1 — один ключ», иначе сломались бы инварианты.
• Почему hash([1, 2, 3]) бросает TypeError, а hash((1, 2, 3)) — нет?

В следующем уроке разберём, что бывает с плохой хеш-функцией: коллизии, кластеризация, деградация O(1) до O(n). И почему SipHash вообще нужен — какие реальные атаки он предотвращает.