Привет, Хабр!

Признавайтесь: вы пользуетесь std::collections::HashMap примерно каждый день и ни разу не задумывались, что под ним. А под ним, если коротко, сидит алгоритм от Google. С Rust 1.36 (это лето 2019-го) стандартный HashMap это порт SwissTable, той самой структуры из абсейловского flat_hash_map. До этого там был Robin Hood hashing, и если вы где-то ещё видите описание std-мапы как «linear probing and Robin Hood bucket stealing», знайте: оно протухло, актуальная документация уже пишет «quadratic probing and SIMD lookup».

И вот «SIMD lookup» это самое интересное. Весь фокус скорости SwissTable держится на одном байте служебных данных на элемент, который сканируется по 16 штук за одну инструкцию процессора.

В статье глянем, как это устроено внутри, почему ваша мапа по умолчанию устойчива к hash DoS и платит за это скоростью, когда в проде стоит переходить на FxHash, и почему низкоуровневый RawTable существует, но в публичном HashMap его спрятали.

Будет много кода и немного ассемблерной романтики.

Раскладка SwissTable: метадата отдельно, данные отдельно

Первое, что надо уложить в голове: SwissTable хранит метаданные и сами пары ключ-значение в двух разных массивах.

Есть массив control-байт: ровно один байт на каждый слот. И есть массив слотов с настоящими данными. Когда вы ищете ключ, вы сначала шерстите дешёвый массив байт, и только когда он говорит «вот тут, возможно, твой ключ», лезете в дорогую память за реальным сравнением. Большинство промахов вообще не доходит до ключей.

Что лежит в control-байте? Одно из трёх состояний, и закодированы они так, что по старшему биту мгновенно понятно, занят слот или нет:

0b1111_1111   // EMPTY     (0xFF) — слот пуст
0b1000_0000   // DELETED   (0x80) — надгробие, тут что-то удалили
0b0xxx_xxxx   // FULL      — слот занят; младшие 7 бит это h2, отпечаток хеша

У пустого и удалённого старший бит равен единице, у занятого нулю. Эта мелочь позволяет одной битовой операцией находить, например, все свободные слоты в группе. А у занятого слота в байте лежит h2, семь бит хеша.

Хеш ключа (64 бита) разрезается на две части. Одна выбирает, с какой группы слотов начинать поиск, вторая становится коротким отпечатком в control-байте. В hashbrown это выглядит примерно так:

// hashbrown, упрощённо
fn h1(hash: u64) -> usize {
    hash as usize                 // младшие биты → индекс стартовой группы (& bucket_mask)
}

fn h2(hash: u64) -> u8 {
    (hash >> (64 - 7)) as u8 & 0x7f   // старшие 7 бит → отпечаток в control-байте
}

Старшие 7 бит идут в отпечаток, младшие выбирают группу. Биты берутся из разных концов хеша специально, чтобы выбор группы и отпечаток не коррелировали. Семь бит дают 128 возможных отпечатков, то есть вероятность ложного совпадения по h2 это примерно 1 к 128. Маленькая, но не нулевая, поэтому после совпадения по отпечатку всё равно надо сравнить настоящий ключ.

И зачем такая возня с отдельным байтом-отпечатком? Чтобы не трогать ключи зря. Сравнение байт это копейки, сравнение ключей (особенно строк) это поход в холодную память и кеш-промахи. SwissTable сначала фильтрует кандидатов по дешёвым отпечаткам и лезет в ключи только для уцелевших. Обычно уцелевает один-два слота из группы.

SIMD: 16 слотов за одну инструкцию

А теперь то, ради чего всё затевалось. Раз отпечатки лежат подряд байтами, их можно сравнивать пачкой через SIMD (Single Instruction Multiple Data, «одна инструкция, много данных»).

Группа в hashbrown на x86 с SSE2 это 16 control-байт, ровно один 128-битный регистр. Поиск отпечатка в группе выглядит так:

// найти в группе все слоты, чей control-байт равен h2, одной инструкцией
let group  = _mm_loadu_si128(ctrl_ptr);   // 16 control-байт в 128-битный регистр
let needle = _mm_set1_epi8(h2 as i8);      // размножаем h2 по всем 16 байтам
let eq     = _mm_cmpeq_epi8(group, needle);// побайтовое сравнение всех 16 разом
let mask   = _mm_movemask_epi8(eq) as u16; // собираем результат в 16-битную маску
// в mask единичка там, где отпечаток совпал. обычно 0, 1 или 2 бита.

Три инструкции, и вы за раз проверили 16 слотов. mmset1_epi8 размазывает искомый отпечаток по всем шестнадцати байтам регистра, mmcmpeq_epi8 сравнивает их с группой параллельно (там, где совпало, ставит 0xFF, иначе 0x00), а mmmovemask_epi8 выжимает из этого 16-битную маску, где каждый бит это «совпало или нет» для своего слота. Дальше вы просто итерируетесь по выставленным битам маски, и для каждого лезете в ключ за подтверждением. Эффективно вы прошли 16 шагов пробинга за один такт.

На ARM то же самое делается через NEON, другими инструкциями, идея та же. А если SIMD недоступен вообще, есть портативная ветка на трюке SWAR (SIMD within a register, «SIMD внутри обычного регистра»): восемь control-байт упаковываются в один u64, отпечаток размножается умножением на 0x0101010101010101, дальше пара xor и битовых масок, и вы сравниваете 8 байт за раз обычной арифметикой, без всякого SIMD. Медленнее, чем настоящие векторные инструкции, но всё равно пачкой, а не по одному.

Кстати про память. Тот самый «один байт оверхеда на элемент» это и есть control-байт. Старая, дореформенная мапа тратила около 8 байт служебных данных на запись, hashbrown тратит 1. Отсюда и заявленные «в 2 раза быстрее и заметно компактнее». А еще конце массива control-байт продублирован кусочек начала, чтобы групповой скан у самого края таблицы спокойно читал 16 байт и не вылезал за границу аллокации.

Пробинг: треугольными числами по группам

Коллизии SwissTable разрешает открытой адресацией, но пробит не по одному слоту, а по группам. И последовательность не линейная, а триангулярная.

В hashbrown за это отвечает ProbeSeq: позиция и шаг, где шаг каждый раз растёт на ширину группы:

// старт: pos = младшие биты хеша, маскированные под размер таблицы
let mut pos = h1(hash) & bucket_mask;
let mut stride = 0;

loop {
    // ... просканировать группу в pos через SIMD выше ...
    // нашли пустой слот в группе? ключа в таблице нет, выходим.

    stride += GROUP_WIDTH;                 // 16
    pos = (pos + stride) & bucket_mask;    // смещения 16, 48, 96, ... треугольные числа
}

Шаг идёт по треугольным числам (умноженным на ширину группы), и это не случайность. При размере таблицы, равном степени двойки (hashbrown всегда держит именно такой размер), триангулярная последовательность гарантированно обходит каждую группу ровно один раз, без зацикливания и без дыр. То есть поиск либо найдёт ключ, либо упрётся в пустой слот, либо честно обойдёт всю таблицу.

Загрузку SwissTable держит высокой, до 7/8, то есть до 87.5 процента заполнения, и при этом не разваливается по скорости. Обычная открытая адресация на такой загрузке уже захлёбывается в длинных цепочках пробинга, а тут групповой SIMD-скан остаётся дешёвым почти до конца.

hash DoS: почему дефолтная мапа намеренно медленнее, чем могла бы

Теперь про безопасность.

У любой хеш-таблицы есть страшный сон: все ключи попадают в одну корзину. Тогда O(1) превращается в O(n), и каждая вставка или поиск деградируют до линейного перебора. Если хешер детерминированный и публично известный, атакующий может специально подобрать набор ключей, которые все коллизируют, скормить их вашему серверу через какой-нибудь HTTP-параметр или заголовок, и положить сервис под нагрузкой.

Защита Rust простая: рандомизация. Дефолтный хешер у HashMap это RandomState, и он засеивается случайным ключом, причём seed добывается из качественного источника случайности операционной системы, по возможности не блокируя программу. Сам хешер это SipHash 1-3 (раньше был SipHash 2-4, переключили ради скорости, и std специально не фиксирует алгоритм в документации, чтобы иметь право менять его дальше).

Логика такая: раз ключ хешера случаен и атакующему неизвестен, он не может предсказать, куда лягут ключи, а значит не может подобрать гарантированно коллизирующий набор. SipHash тут не просто быстрый хеш, а криптографический псевдослучайный, его как раз и проектировали стойким к подбору коллизий.

use std::collections::HashMap;

let mut m = HashMap::new();   // на самом деле HashMap<_, _, RandomState>
m.insert("user-supplied-key", 1);
// SipHash 1-3 со случайным ключом: куда ляжет ключ, заранее не угадать

Если вы создаёте мапу с детерминированным хешером, защита испаряется. Самый проблемный случай это HashMap в const- или static-инициализаторе: рандомного seed там взять негде, и такая мапа к hash DoS не устойчива. То же самое с любым фиксированным хешером. В документации std про это есть предупреждение, и про with_hasher тоже: ставя хешер руками, вы можете своими руками открыть вектор для DoS-атаки.

Мораль: дефолт намеренно жертвует частью скорости ради безопасности по умолчанию, и для всего, что хоть как-то касается внешнего ввода, это правильный размен. А вот когда ввод доверенный, можно разменять обратно.

FxHash: машете там, где DoS не грозит

Раз уж зашла речь про «доверенный ввод», вот вам канонический пример: сам компилятор Rust. rustc обрабатывает исходники, которые он полностью контролирует, никакой злоумышленник не подсунет ему идентификаторы, специально подобранные под коллизии. Значит, можно выкинуть криптостойкость и взять что-нибудь брутально быстрое. Так появился FxHash.

Классический FxHash (его таскали из Firefox, отсюда буква Fx) это буквально три операции на слово:

// классический FxHash: старый rustc-hash и крейт fxhash
const K: u64 = 0x51_7c_c1_b7_27_22_0a_95;   // забавный факт: 2^64 / K ≈ π

fn add_word(hash: &mut u64, word: u64) {
    *hash = (hash.rotate_left(5) ^ word).wrapping_mul(K);
}
// инициализация: hash = 0
// финализация: ничего, возвращаем как есть

Поворот на 5, xor со словом, умножение на константу. И всё. Никакого перемешивания 64-битными блоками, как у SipHash: FxHash просто кастует каждое целое в слово и прогоняет add_word. Качество, мягко говоря, среднее. Прогоните его через тесты качества хеша, и он завалит половину: например, для любой последовательности нулей он выдаёт ноль, а старшие биты входа умножение во многом выкидывает. Но для нужд компилятора это неважно, и обогнать его трудно. Большинство ключей в rustc это маленькие целые (старшие биты нули) и указатели (мало энтропии в старших битах), строки редки.

В rustc-hash 2.0 алгоритм заменили. Имя FxHasher оставили для совместимости, но по сути это теперь полиномиальный хеш с финализацией одним битовым поворотом плюс wyhash-подобная компрессия для строк. Поворот-финализатор как раз чинит старую болячку: перетаскивает высокоэнтропийные старшие биты вниз, туда, где их ждут хеш-таблицы. Так что «FxHash» сегодня это уже не тот FxHash, что в большинстве туториалов.

Пользоваться им просто:

use rustc_hash::FxHashMap;

let mut map: FxHashMap<u32, u32> = FxHashMap::default();
map.insert(22, 44);

Когда переключаться на FxHash? Когда профайлер показал, что хеширование это горячая точка, и вы уверены, что ключи доверенные. Внутренние мапы по целочисленным идентификаторам, интернинг, кеши, индексы по своим же данным, любые структуры, куда внешний пользователь не дотягивается напрямую.

И когда не переключаться: всё, что хешит внешний ввод. Ключи из HTTP-заголовков, имён файлов, пользовательских строк, тел запросов. Там FxHash уже как открытая дверь для hash DoS, и экономия пары наносекунд не стоит положенного сервиса. Если хочется и побыстрее, и с защитой, посмотрите в сторону aHash (умеет в аппаратный AES и засеивается случайно) или foldhash. Кстати, отдельный крейт hashbrown давно ушёл с SipHash: сначала на aHash, теперь на foldhash, который заметно быстрее, но и слабее по стойкости к hash DoS. А вот std продолжает держать SipHash 1-3 со своим RandomState.

RawTable: он есть, но вам его не дают

Внутри hashbrown живёт RawTable, низкоуровневый движок, который и реализует всю описанную выше механику: память, раскладку, вставку, поиск, удаление. HashMap, HashSet и весь Entry API это тонкие обёртки поверх него. И вот RawTable в публичном std-HashMap вам не отдают. Почему?

Во-первых, это unsafe-API в чистом виде. В документации hashbrown он так и подписан: «A raw hash table with an unsafe API». Он ничего не знает про ваши ключи и хеши, вы передаёте хеши руками и сами отвечаете за инварианты.

Во-вторых, и это главная причина, экспонировать RawTable в std значит заморозить внутреннее устройство HashMap. Стандартная библиотека хочет иметь право поменять реализацию: вчера Robin Hood, сегодня SwissTable, завтра что-то ещё. Если бы публичный API раскрывал кишки таблицы, любой такой переход стал бы ломающим изменением для всей экосистемы. Поэтому std держит HashMap тонкой безопасной обёрткой: пары ключ-значение, Entry, и больше ничего наружу.

Санкционированный компромисс в std существует и называется raw_entry. Он позволяет искать и вставлять по уже посчитанному хешу, не требуя K: Hash и не хешируя дважды. Но он так и остался нестабильным, за фиче-гейтом hash_raw_entry, потому что API вышел корявый.

А что в самом hashbrown?

В hashbrown 0.15.1 публичные RawTable и raw_entry убрали из публичного API. Вместо них теперь HashTable: тоже низкоуровневая таблица с явным хешированием, но уже не такая зубастая. Вы по-прежнему передаёте хеш сами, но без сырого unsafe на каждом шагу:

use hashbrown::{HashTable, DefaultHashBuilder};
use std::hash::BuildHasher;

let mut table: HashTable<i32> = HashTable::new();
let bh = DefaultHashBuilder::default();
let hash = |v: &i32| bh.hash_one(v);

table.insert_unique(hash(&1), 1, hash);   // хеш считаешь и передаёшь сам
table.insert_unique(hash(&2), 2, hash);
table.insert_unique(hash(&3), 3, hash);

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

Но у низкоуровневости есть цена. API разрешает положить в таблицу два элемента с одинаковым ключом, таблица не сломается, но лукап начнёт возвращать произвольный из дубликатов, а сложность операций уедет с O(1) на O(k), где k это число дублей. То есть гарантии уникальности теперь на вас.

Вот почему RawTable есть, но почти никто его не использует. Прямого доступа из std нет по дизайну, в hashbrown сырой RawTable спрятали в пользу более безопасного HashTable, а сам HashTable нужен лишь в узких случаях, где вы готовы вручную следить за инвариантами ради последней капли производительности. Подавляющему большинству кода хватает обычного HashMap.

В завершение

Самое забавное тут в том, что в обычном коде вам ничего из этого не понадобится. Как писали HashMap::new(), так и будете писать, и правильно сделаете. Вся эта махина внутри крутится молча и ровно затем, чтобы вы про неё не думали.

Хорошая абстракция это та, которую не замечаешь, пока сам не полезешь внутрь от любопытства. .

Так что менять у себя ничего не надо. Но в следующий раз, когда наберёте map.insert(...), вы хотя бы будете представлять, какая дичь прячется за этой одной строчкой.

Размещайте облачную инфраструктуру и масштабируйте сервисы с надежным облачным провайдером Beget.
Эксклюзивно для читателей Хабра мы даем бонус 10% при первом пополнении.