CS Notes

hash

7 min read

Hash

← Array | String →

Array даёт доступ по числовому индексу за O(1). Но HTTP-заголовки, опции метода, конфигурация — это пары ключ-значение, где ключ не число, а строка или символ. Поиск по ключу в массиве — перебор всех элементов, O(n). Хеш-таблица решает это за O(1) через хеш-функцию и массив бакетов. Но в Ruby-программе большинство хешей маленькие — 3–7 ключей: params, options, заголовки отдельного HTTP-ответа. Поддерживать полноценную хеш-таблицу с массивом бакетов ради пяти пар расточительно: вычисление хеша, деление по модулю, косвенное обращение через массив индексов дороже, чем пройти по пяти парам последовательно.

Ruby решает это адаптивно. Маленькие хеши (≤8 элементов) используют компактный массив с линейным поиском — AR table. Когда хеш перерастает 8 пар, Ruby конвертирует его в полноценную хеш-таблицу — ST table. Оба представления гарантируют сохранение порядка вставки.

Маленький хеш: AR table

Рассмотрим типичный хеш параметров:

params = { name: "Alice", age: 30, city: "Tokyo" }

Три пары ключ-значение. Ruby хранит их в AR table (array-based table) — компактной структуре из двух частей:

AR table (≤8 элементов):
┌────────────────────┬──────────────────────────────────────────┐
│ hints[8]: 8 байт   │ pairs[8]: 8 пар {key, value} = 128 байт │
│ 1 байт на элемент  │ 16 байт на элемент                       │
└────────────────────┴──────────────────────────────────────────┘

AR table размещается прямо в слоте объекта RHash, сразу после заголовка — без отдельной аллокации. Вся структура (~136 байт) помещается в два cache lines процессора (по 64 байта). Последовательный обход 8 hints выигрывает за счёт пространственной локальности кеша — все 8 байт hints лежат рядом в памяти.

Поиск: hints вместо полного хеширования

Когда Ruby ищет ключ :age в params, он не вычисляет hash % num_bins и не обращается к массиву бакетов. Вместо этого:

  1. Вычисляет хеш ключа :age и берёт младшие 8 бит — hint.
  2. Сравнивает hint с hints[0], hints[1], hints[2] — три сравнения однобайтовых значений.
  3. Если hint совпал (допустим, hints[1]) — сравнивает pairs[1].key == :age.
  4. Ключи совпали — возвращает pairs[1].value.

Hint из 8 бит даёт 256 вариантов: вероятность ложного совпадения — 1/256. Для 8 элементов почти всегда полное сравнение ключей выполняется не больше одного раза. А сравнение 8 однобайтовых hints — это несколько тактов процессора, всё в кеше.

Для сравнения, полноценная хеш-таблица на тех же 3 элементах потребовала бы: вычисление hash % num_bins (деление — одна из самых дорогих арифметических операций), обращение к bins[] (возможный cache miss), затем обращение к entries[] (ещё один cache miss). На маленьких данных непрямые обращения к памяти стоят дороже, чем линейный проход по компактной структуре.

Удаление из AR table

При удалении элемента из AR table Ruby сдвигает оставшиеся пары и hints, заполняя пробел — как при удалении из обычного массива. Tombstones не нужны: нет цепочек поиска, которые могли бы разорваться. Стоимость — O(n) сдвиг, но при n ≤ 8 это несколько десятков байт.

Рост: когда линейный поиск проигрывает

Допустим, хеш растёт — приложение собирает метрики и добавляет ключи:

params[:requests] = 0
params[:errors] = 0
params[:latency] = 0.0
params[:throughput] = 0
params[:uptime] = true
# ... уже 8 пар, AR table заполнена
params[:version] = "1.0"  # 9-й элемент → переход на ST table

При 8 элементах каждый lookup — 8 сравнений hints. Ещё терпимо. Но при 20 элементах это 20 сравнений на каждый поиск — O(n), где n растёт. Хеш-таблица с O(1) поиском начинает выигрывать. Ruby переключается при вставке 9-го элемента.

Переход AR → ST

Ruby извлекает все ключи и их хеши из AR table, создаёт ST table нужного размера и переносит записи. Важный момент: вычисление хеша ключа — это вызов метода #hash, то есть Ruby-кода. Пользовательский #hash может модифицировать сам хеш (reentrancy). Если бы Ruby вычислял хеш и сразу вставлял в ST table, модификация хеша внутри #hash могла бы повредить недостроенную таблицу. Поэтому код перехода сначала собирает все хеши в локальный массив, а потом строит ST table из уже вычисленных значений.

Обратный переход ST → AR при уменьшении хеша не происходит. Перестройка стоит дорого, а хеш, который уже рос, вероятно вырастет снова. На практике это означает, что хеш, однажды доросший до 9 элементов, останется на ST table даже если уменьшится до 3 — лишние ~200 байт структуры, но без риска повторной конвертации.

Большой хеш: ST table

ST table — хеш-таблица с open addressing, состоящая из двух массивов:

ST table (>8 элементов):
bins[]:    [ _ ][ 2 ][ 0 ][ _ ][ 1 ][ _ ][ _ ][ 3 ]
                                                        индексы в entries[]
entries[]: [ (hash0, key0, val0) ]   <- 0-й по порядку вставки
           [ (hash1, key1, val1) ]   <- 1-й
           [ (hash2, key2, val2) ]   <- 2-й
           [ (hash3, key3, val3) ]   <- 3-й

entries[] — компактный массив записей {hash, key, value}, куда элементы добавляются последовательно. Порядок вставки сохраняется автоматически: итерация по entries[] от начала до конца — это порядок, в котором ключи были добавлены. Гарантия Ruby, что hash.each возвращает элементы в порядке вставки, обеспечивается именно этой структурой.

bins[] — массив индексов в entries[]. Позиция в bins[] определяется хешем: bin_index = hash % num_bins. Значение bins[bin_index] — номер записи в entries[]. При коллизии (бин занят) Ruby ищет следующий свободный бин (linear probing).

Разделение на два массива даёт два преимущества. Итерация не требует пропуска пустых бакетов — entries[] компактен. А bins[] содержит только индексы, что позволяет следующую оптимизацию.

Переменная ширина индексов

Если в хеше 100 элементов, индексы в entries[] укладываются в 7 бит (0–127). Хранить их как 64-битные числа — пустая трата. Ruby выбирает минимальный тип индекса:

ЗаписейТип индексаБайт на bin
до 128uint81
до 32Kuint162
до 2Buint324
большеuint648

Хеш со 100 элементами использует 8-битные индексы. При 256 бинах это 256 байт на bins[] вместо 2048 при 64-битных — экономия почти 2 КБ. Тип пересчитывается при рехешировании.

Удаление и tombstones

При удалении из ST table запись в entries[] помечается как deleted (tombstone), но не удаляется физически. Причина: open addressing строит цепочки поиска — если элемент A занял бин 5, а элемент B при коллизии ушёл в бин 6, удаление A из бина 5 разорвёт цепочку, и B станет ненаходимым. Tombstone сохраняет цепочку: бин 5 помечен как “был занят”, и поиск продолжается дальше.

Со временем tombstones накапливаются, замедляя поиск (каждый tombstone — лишний шаг в цепочке). При рехешировании Ruby перестраивает entries[], удаляя tombstones и уплотняя массив.

Хеш-функция и безопасность

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

Ruby перешёл с быстрой MurmurHash на криптографически устойчивую SipHash (около Ruby 2.4). SipHash медленнее — примерно в 2–3 раза на коротких ключах, десятки наносекунд разницы на операцию. Но при старте процесса Ruby генерирует случайный seed, и подбор коллизий без знания seed вычислительно неосуществим. Для веб-приложения, принимающего пользовательский ввод, это необходимая цена.

Структура RHash

struct RHash {
    struct RBasic basic;   // 16 байт: flags + klass
    const VALUE ifnone;    // значение по умолчанию (Hash.new(0)) или Proc (Hash.new { ... })
    // далее: ar_table или st_table, inline в слоте
};

Данные AR table или ST table размещаются после ifnone прямо в слоте — без отдельной аллокации для маленьких хешей. Флаги RHASH_AR_TABLE_P / RHASH_ST_TABLE_P в заголовке RBasic.flags определяют текущее представление — их проверяет каждая операция чтения и записи, чтобы выбрать правильный путь кода.

Sources

← Array | String →

Graph View

Backlinks