CS Notes

hash-table

7 min read

Хеш-таблица

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

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

Хеш-таблица реализует словарь — коллекцию пар ключ-значение:

ОперацияСигнатураСложность
Получить значениеget(key) → valueO(1) в среднем
Записать значениеput(key, value)O(1) в среднем
Удалитьdelete(key)O(1) в среднем
Проверить наличиеcontains?(key) → boolO(1) в среднем

“В среднем” — потому что в худшем случае, при патологическом распределении ключей, все операции деградируют до O(n). Откуда берётся этот худший случай и как его избежать — об этом дальше.

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

Слово “hash” пришло из кулинарии — буквально “рубить, крошить, мелко резать”. Хеш-функция “рубит” входные данные, перемешивает и выдаёт число, в котором исходная структура неузнаваема. Это число используется как индекс в массиве — и вот уже произвольный ключ превращается в 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 делает хеш зависимым от порядка символов. Почему именно 31: это нечётное простое число, а умножение на него компилятор может заменить на (x << 5) - x — быстрый сдвиг вместо дорогого умножения.

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

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

index = hash(key) % capacity

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

Индекс должен попадать в диапазон 0...capacity. В Ruby оператор % уже возвращает неотрицательный остаток, но в некоторых языках отрицательный hash может дать отрицательный результат — тогда индекс нормализуют.

Коллизия

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

Стратегия 1: Chaining (цепочки)

Каждая ячейка хранит список (цепочку) элементов с одинаковым индексом:

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

Ячейка хранит и ключ, и значение — ключ нужен, чтобы при коллизии отличить «свой» элемент от чужого. Без ключа get("alice") и get("charlie"), попавшие в одну ячейку, вернули бы одно и то же значение.

get(key): вычисляем индекс, идём по списку, сравниваем ключи.

put(key, value): вычисляем индекс, ищем в списке, обновляем или добавляем.

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

Стратегия 2: Open Addressing (открытая адресация)

В open addressing весь массив “открыт” для размещения любого элемента, не только того, чей хеш указывает на эту ячейку. Все элементы живут прямо в массиве. Если ячейка занята — ищем следующую свободную.

Linear Probing: если ячейка i занята, пробуем i+1, i+2, …

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

Занятые ячейки имеют свойство слипаться в группы — кластеры. Новый элемент, попавший хешем в любую точку кластера, добавляется в его конец — и кластер растёт. Два соседних кластера сливаются в один большой. Средняя длина поиска резко растёт по мере заполнения таблицы: для линейного пробинга при α = n / capacity (где n — количество элементов, capacity — размер массива) оценки такие:

  • успешный поиск: ≈ (1/2) × (1 + 1/(1-α))
  • неуспешный поиск: ≈ (1/2) × (1 + 1/(1-α)^2)

При α = 0.9 это уже порядка ~5–6 проб для успешного поиска и ~50 проб для неуспешного. Quadratic probing (i+1, i+4, i+9, ...) и double hashing уменьшают кластеризацию, но усложняют код.

Tombstones (надгробия)

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

Поэтому вместо nil ставят tombstone — специальный маркер («надгробие» на месте удалённого элемента). При поиске tombstone означает «продолжай искать», при вставке — «можно занять».

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

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

load_factor = n / capacity

Где n — количество элементов, capacity — размер массива.

Для chaining средняя длина цепочки равна load factor: при lf = 3 каждый get в среднем проходит по 3 узлам. Load factor может превышать 1 — цепочки допускают любую длину. Для open addressing load factor обязан быть меньше 1 — физически нельзя разместить больше элементов, чем ячеек. На практике порог держат на уровне 0.7–0.75: выше этого кластеры растут лавинообразно.

Rehashing (перехеширование)

Когда load factor пересекает порог, таблицу перестраивают — выделяют новый массив большего размера и перехешируют все элементы:

  1. Выделяем новый массив большего размера (×2)
  2. Перехешируем все элементы (hash % новый_capacity ≠ hash % старый_capacity)
  3. Освобождаем старый массив
До (capacity=4):            После (capacity=8):
│ 0 │ [A → B]  │           │ 0 │ [B]  │
│ 1 │ [C]      │     →     │ 2 │ [A]  │
│ 2 │ []       │           │ 3 │ [C]  │
│ 3 │ [D]      │           │ 5 │ [D]  │

hash % 4 и hash % 8 дают разные индексы — элементы перераспределяются, цепочки укорачиваются.

Стоит O(n), но происходит редко → амортизированно O(1) на операцию.

Реализация хеш-таблицы с chaining (Ruby)

class HashTable
  LOAD_FACTOR_THRESHOLD = 0.75
 
  def initialize(capacity = 8)
    @buckets = Array.new(capacity)
    @size = 0
  end
 
  def put(key, value)
    resize if (@size + 1).to_f / @buckets.length > LOAD_FACTOR_THRESHOLD
 
    index = bucket_index(key)
    entry = find_entry(index, key)
 
    if entry
      entry[1] = value
    else
      @buckets[index] ||= []
      @buckets[index] << [key, value]
      @size += 1
    end
  end
 
  def get(key)
    entry = find_entry(bucket_index(key), key)
    entry&.[](1)
  end
 
  def delete(key)
    index = bucket_index(key)
    chain = @buckets[index]
    return nil unless chain
 
    i = chain.index { |k, _| k == key }
    return nil unless i
 
    @size -= 1
    chain.delete_at(i)[1]
  end
 
  private
 
  def bucket_index(key)
    key.hash % @buckets.length
  end
 
  def find_entry(index, key)
    chain = @buckets[index]
    return nil unless chain
 
    chain.find { |k, _| k == key }
  end
 
  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
end

Каждая ячейка (bucket) — массив пар [key, value]. При resize все элементы перехешируются: hash % новый_capacity даёт другие индексы, поэтому цепочки перераспределяются.

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

ОперацияВ среднемВ худшем
getO(1)O(n)
putO(1)*O(n)
deleteO(1)O(n)

* — амортизированно с учётом rehashing

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

Сравнение стратегий

АспектChainingOpen Addressing
ПамятьУказатели на спискиТолько массив
ЛокальностьХужеЛучше
Load factorМожет быть > 1Должен быть < 1
УдалениеПростоеНужны tombstones
КодПрощеСложнее

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

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

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

Для кэша с ограниченным размером нужно вытеснять элементы. Какие? Нужна политика вытеснения — и структура, которая её поддерживает. LRU-кэш комбинирует хеш-таблицу с двусвязным списком для решения этой задачи.

Sources

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

Graph View

Backlinks