Хеш-таблица

Предпосылки: массив (индексация, формула адреса), связный список (для стратегии цепочек), ссылки, оценка сложности O(…), базовое чтение Ruby (методы, блоки, массивы и хеши).

← Стек, очередь, дек | LRU-кэш →

Массив и список работают с позицией: индекс, начало, конец. Ключ доступа всегда число. Но искать данные часто нужно по другому ключу — по строке или другому значению, а не по номеру места. Активные сессии веб-сервера хранятся по строковому идентификатору; кэш доменных имён ищет запись по самому имени. Чтобы найти такой ключ в массиве, приходится перебирать элементы по одному — O(n). Нужна структура, которая по произвольному ключу сразу попадает в нужное место, за одну-две операции вместо тысячи. Такая структура называется хеш-таблицей.

Хеш-таблица хранит пары «ключ — значение» и отвечает на четыре вопроса: по ключу получить значение, записать пару, удалить пару, проверить, есть ли ключ. В среднем каждая из операций — O(1):

Операция	Что делает	Сложность
`get(key)`	вернуть значение по ключу	O(1) в среднем
`put(key, value)`	записать пару ключ-значение	O(1) в среднем
`delete(key)`	удалить пару по ключу	O(1) в среднем
`contains?(key)`	проверить, есть ли ключ	O(1) в среднем

«В среднем» — потому что O(1) держится, пока ключи раскладываются по местам ровно. Если же все они скапливаются в одной точке, операции снова перебирают элементы один за другим и деградируют до O(n). Всё держится на том, как ключ превращается в место в массиве, — с этого превращения и начнём.

От ключа к индексу

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

Каким должен быть хороший «измельчитель»

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

Хеш-функция для строки

Плохая (не учитывает порядок):

def bad_hash(str)
  str.chars.sum(&:ord)  # "ab" и "ba" дадут одинаковый хеш
end

Хорошая (классическая, как в Java):

def good_hash(str)
  hash = 0
  str.each_char { |c| hash = hash * 31 + c.ord }
  hash
end

Умножение на 31 на каждом шаге делает хеш зависимым от порядка символов: символ, попавший раньше, успевает умножиться больше раз, поэтому «ab» и «ba» расходятся. Множитель берут простым — простое число при перемешивании реже даёт совпадения, чем составное.

"ab": (0*31 + 97)*31 + 98 = 3105
"ba": (0*31 + 98)*31 + 97 = 3135

От хеша к индексу

Хеш — большое число, а массив маленький: всего capacity ячеек (это его размер). Чтобы хеш превратился в номер ячейки, берут остаток от деления хеша на размер массива — остаток меньше делителя, поэтому попадает в диапазон от 0 до capacity - 1. Хеш бывает и отрицательным; в Ruby остаток от деления на положительное число всё равно неотрицателен, а в языках со знаковым остатком (Java, C) индекс дополнительно нормализуют — берут остаток по модулю или добавляют capacity:

index = hash(key) % capacity   # % — остаток от деления

Если capacity = 16 и hash("alice") = 3105, то index = 3105 % 16 = 1.

Коллизия

Данных бесконечно много, ячеек — ограниченное количество. Разные ключи могут получить одинаковый индекс. Это коллизия (столкновение). Два разных идентификатора сессии — "abc123" и "xyz789" — после hash(key) % capacity могут дать один и тот же индекс, и обе пары будут претендовать на одну ячейку. Нужна стратегия разрешения.

Цепочки в каждой ячейке

Первый способ разрешить коллизию: пусть ячейка хранит не одну пару, а связный список пар с одинаковым индексом — цепочку. Стрелка в схеме ниже — это связь списка от одного узла к следующему:

┌───┬─────────────────────────────────────┐
│ 0 │ [("bob", data)]                     │
│ 1 │ [("alice", data) → ("charlie", data)]│  <-- коллизия
│ 2 │ []                                  │
└───┴─────────────────────────────────────┘

Каждый узел цепочки хранит и ключ, и значение. Ключ нужен, чтобы при коллизии отличить нужную пару от соседней: alice и charlie попали в ячейку 1, и без сравнения ключей get("alice") не понял бы, какую из двух пар вернуть.

Поиск по ключу теперь двухшаговый. get(key): считаем индекс, идём по цепочке этой ячейки и сравниваем ключ каждой пары с искомым; нашли совпадение — возвращаем значение. put(key, value): считаем индекс, идём по цепочке; если пара с таким ключом уже есть — заменяем её значение, если нет — добавляем новую пару в конец.

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

Размещение прямо в массиве

Цепочки тратят память на отдельные узлы списка и уводят поиск за пределы массива. Второй способ обходится одним массивом: каждая пара живёт прямо в ячейке, без вложенных списков. Если ячейка, на которую указал хеш, уже занята — пробуют следующую. Отсюда и название: ячейка для пары не закреплена жёстко за её хешем, любая пара «открыта» для размещения в соседних ячейках. Поиск свободной ячейки шаг за шагом называют пробой (probing).

Простейший вариант — линейная проба: если ячейка i занята, проверяем i+1, потом i+2, и так до первой свободной.

put("alice"),   hash % 8 = 1 -> кладём в 1
put("charlie"), hash % 8 = 1 -> занято, пробуем 2, кладём
put("dave"),    hash % 8 = 2 -> занято, пробуем 3, кладём

Здесь видно, как занятые ячейки слипаются в непрерывные группы — кластеры. Проба всегда сдвигается на соседнюю ячейку, поэтому пара, не поместившаяся на своё место, садится вплотную к занятым, удлиняя их сплошную полосу. Чем длиннее полоса, тем больше у неё «входов»: любая новая пара, чей хеш попал в любую точку кластера, добегает пробой до его конца и пристраивается там — кластер растёт сам себя ускоряя. Соседние кластеры дотягиваются друг до друга и сливаются. Поэтому средняя длина поиска для линейной пробы растёт по мере заполнения не плавно, а лавинообразно. Существуют пробы, разбивающие кластеры, — квадратичная (i+1, i+4, i+9, …) и двойное хеширование (шаг пробы задаёт вторая хеш-функция), — но они усложняют код.

Надгробия для удалённых пар

У линейной пробы есть скрытая ловушка при удалении. Допустим, hash("alice") % 8 = 1 — alice легла в ячейку 1. У charlie тот же индекс 1, ячейка занята, проба положила charlie в ячейку 2. Теперь удалим alice и просто очистим ячейку 1, оставив её пустой. Запрос get("charlie"): считаем индекс — 1, смотрим ячейку 1 — пусто, значит дальше искать незачем, ведь при вставке charlie остановился бы на первой же свободной ячейке. Поиск возвращает «не найдено», хотя charlie лежит в ячейке 2: пустая ячейка разорвала цепочку проб.

Поэтому удалённую ячейку не очищают, а помечают tombstone — маркером «надгробие» на месте удалённой пары. Для поиска tombstone значит «здесь когда-то прыгали дальше, продолжай искать», для вставки — «ячейка свободна, можно занять».

Деградация и load factor

И цепочки, и открытая адресация замедляются по мере заполнения: цепочки удлиняются, кластеры сливаются, и время операции сползает от O(1) к O(n). Чтобы измерить заполнение одним числом, берут load factor (коэффициент заполнения) — отношение числа пар к числу ячеек:

load_factor = n / capacity   # n — число пар, capacity — число ячеек

Для цепочек load factor — это и есть средняя длина цепочки: при значении 3 каждый get в среднем проходит по 3 узлам. Здесь load factor может быть и больше 1 — цепочка вмещает сколько угодно пар. Для открытой адресации он обязан быть меньше 1: больше пар, чем ячеек, в массив физически не уложить. И деградация у неё резче — те самые лавинообразно растущие кластеры. Конкретно для линейной пробы среднее число проверенных ячеек выражается через load factor (обозначим его α):

удачный поиск (ключ есть): ≈ (1/2) × (1 + 1/(1-α))
неудачный поиск (ключа нет): ≈ (1/2) × (1 + 1/(1-α)^2)

Формулы важны не сами по себе, а тем, как они взрываются у границы. При α = 0.5 это пара-тройка проверок, но при α = 0.9 — уже около 5–6 ячеек для удачного поиска и порядка 50 для неудачного: знаменатель 1-α стремится к нулю, и число проб уходит вверх. Поэтому на практике порог заполнения держат на уровне 0.7–0.75 и не дают таблице подойти к опасной зоне.

Перестройка таблицы при переполнении

Порог заполнения держит O(1), но число пар растёт, а размер массива фиксирован — рано или поздно load factor упрётся в порог. Когда это происходит, таблицу перестраивают: заводят массив побольше и заново вычисляют индекс каждой пары под новый размер. Эту перестройку называют перехешированием (rehashing).

Заводим новый массив вдвое большего размера.
Для каждой пары считаем индекс заново: hash % новый_capacity. Новый размер даёт другой остаток, поэтому пары ложатся по другим ячейкам.
Старый массив больше не нужен и отбрасывается.

Размер удваивается, число пар прежнее — значит load factor падает вдвое, цепочки и кластеры укорачиваются, O(1) восстановлено:

До (capacity=4, hash взяты для примера):   После (capacity=8):
A: hash=8   8%4=0                          A: 8%8=0
B: hash=4   4%4=0  -- коллизия с A         B: 4%8=4
C: hash=5   5%4=1                          C: 5%8=5
D: hash=7   7%4=3                          D: 7%8=7

│ 0 │ [A -> B] │   ->   │ 0 │ [A] │
│ 1 │ [C]      │        │ 4 │ [B] │
│ 2 │ []       │        │ 5 │ [C] │
│ 3 │ [D]      │        │ 7 │ [D] │

A и B сталкивались при capacity=4, потому что 8%4 и 4%4 оба дают 0; при capacity=8 остатки расходятся (0 и 4) — коллизия исчезает.

Сама перестройка стоит O(n): нужно пройти все пары. Но удвоение размера делает её настолько редкой, что между двумя перестройками успевают пройти сотни обычных вставок по O(1). Если размазать стоимость одной перестройки по всем этим вставкам, на каждую приходится лишь небольшая постоянная добавка. Такую среднюю стоимость, посчитанную по длинной серии операций, называют амортизированной — и для вставки она остаётся O(1).

Цепочки в коде

Соберём механизм цепочек в коде. Основа — массив ячеек; ячейку в коде хеш-таблиц по традиции называют bucket («корзина»). Каждая ячейка хранит цепочку — массив пар [key, value]. Индекс ячейки считается уже знакомым способом — остаток от деления хеша ключа на размер массива:

def initialize(capacity = 8)
  @buckets = Array.new(capacity)   # массив ячеек, поначалу пустых
  @size = 0                        # сколько пар сейчас лежит
  @max_load = 0.75                 # порог заполнения, на котором перестраиваем
end
 
def bucket_index(key)
  key.hash % @buckets.length       # хеш ключа -> номер ячейки
end

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

def put(key, value)
  resize if (@size + 1).to_f / @buckets.length > @max_load
 
  index = bucket_index(key)
  @buckets[index] ||= []                 # пустую ячейку заводим как пустую цепочку
  pair = @buckets[index].find { |k, _| k == key }
 
  if pair
    pair[1] = value                      # ключ уже есть -> меняем значение
  else
    @buckets[index] << [key, value]      # ключа нет -> добавляем пару
    @size += 1
  end
end

Перестройка из предыдущего раздела на коде — это завести массив вдвое больше и заново разложить по нему все пары прежним put (теперь он считает индекс под новый размер):

def resize
  old_buckets = @buckets
  @buckets = Array.new(old_buckets.length * 2)
  @size = 0
 
  old_buckets.each do |chain|
    next unless chain                    # пропускаем пустые ячейки
    chain.each { |key, value| put(key, value) }
  end
end

get и delete строятся так же: посчитать индекс через bucket_index, пройти цепочку, сравнивая ключи.

Сложность операций

Операция	В среднем	В худшем
get	O(1)	O(n)
put	O(1)*	O(n)
delete	O(1)	O(n)

* — для вставки указана амортизированная стоимость с учётом перестроек.

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

Цепочки против открытой адресации

Аспект	Цепочки	Открытая адресация
Память	пара + отдельный узел списка на каждый элемент	только массив, без узлов
Load factor	может быть > 1	обязан быть < 1
Удаление	просто убрать из цепочки	нужны надгробия
Код	проще	сложнее

Цепочки проще и спокойно переносят высокое заполнение, но платят памятью за узлы списка и разбросанностью пар по памяти. Открытая адресация держит всё в одном массиве, где соседние пробы попадают в соседние ячейки, — но требует надгробий и низкого порога заполнения. На практике реализации часто комбинируют обе стратегии. Ruby Hash, например, маленькие хеши (до 8 пар) хранит компактным массивом с линейным перебором, а при росте переходит к полноценной хеш-таблице с открытой адресацией — подробности в заметке о внутреннем устройстве Ruby Hash.

Чего хеш-таблица не умеет сама

O(1) доступ по ключу — есть. Но хеш-таблица раскладывает пары по индексу хеша, а не по тому, когда и как часто к ним обращались. Никакого «кто был нужен давно, а кто только что» она не помнит.

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

Sources

Donald E. Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching — оценки для линейного пробинга (linear probing).