Хеш-функция превращает любой ключ (строку, кортеж, число) в целое число фиксированного размера. Хеш-таблица использует его, чтобы выбрать место в массиве: index = h(key) % m, где m — размер массива. Чем лучше хеш-функция, тем равномернее распределяются ключи и тем ближе поиск к O(1).

Ключ проходит через хеш-функцию и выбирает ячейку массива через `% 8`
Ключ проходит через хеш-функцию и выбирает ячейку массива через % 8

Свойства хорошей хеш-функции

  • Детерминизм: один и тот же ключ всегда (в рамках процесса) даёт один и тот же хеш.
  • Согласованность: если a == b, то hash(a) == hash(b) (обратное неверно: хеши могут совпадать).
  • Равномерность: значения должны попадать в диапазон 0..m-1 с одинаковой плотностью.
  • Скорость: время линейно по размеру ключа.
  • Лавинный эффект: при изменении одного символа ключа хеш должен меняться сильно.

Хеш строки: сумма плоха, полином хорош

Если просто сложить коды символов (sum_hash), анаграммы получат одинаковый хеш. Полиномиальный хеш учитывает позицию: h = s[0]*p^(n-1) + ... + s[n-1] (по модулю m). По схеме Горнера он считается за O(n): h = h * p + ord(ch).

python
def sum_hash(s):
    return sum(ord(ch) for ch in s)

def poly_hash(s, p=31, m=2**32):
    h = 0
    for ch in s:
        h = (h * p + ord(ch)) % m
    return h

for w in ["listen", "silent", "enlist", "banana"]:
    print(w, sum_hash(w), poly_hash(w))
text
listen 655 3192458695
silent 655 3392640085
enlist 655 2996453575
banana 609 2898612069