Как устроены ассоциативные массивы: от цепочек до Swiss Tables

2026-10-17

Разобрал все механизмы, которые нашёл за ассоциативными массивами: цепочки, открытая адресация, Robin Hood, hopscotch, cuckoo, Swiss Tables, B-деревья, skip list и ART. Плюс что лежит внутри map в Go до и после 1.24, конкурентных карт Go и Map/Object в V8. Без замеров - замеры в следующей статье.

Зачем

map[K]V в Go, Map в JS, dict в Python, HashMap в Rust. Интерфейс один: положить, найти, удалить. За ним - десяток разных механизмов, и выбор между ними решает не асимптотика, а то, сколько раз процессор сходит в память за один поиск.

В Go 1.24 встроенный map переписали на Swiss Tables. Это хороший повод разложить по полочкам, что вообще бывает, чем одно отличается от другого и что на самом деле лежит в языках, которыми я пользуюсь каждый день.

Это первая из двух статей. Здесь - устройство, без единого замера. Во второй будут цифры на моей машине.

Общая часть

У хеш-таблицы три решения.

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

Разрешение коллизий - что делать, когда двум ключам выпала одна ячейка. Здесь и живёт большая часть разнообразия.

Коэффициент заполнения (load factor) - сколько элементов на ячейку таблица терпит, прежде чем вырасти. Меньше - быстрее поиск, больше - экономнее память.

И одно наблюдение, которое объясняет почти всё дальше. Сравнение двух чисел стоит наносекунду. Промах кэша и поход в оперативную память - около сотни. Поэтому структура, которая делает три сравнения подряд в одной кэш-линии, обгоняет структуру, которая делает одно сравнение, но прыгает по указателю.

Цепочки

Самая старая схема. Каждая ячейка массива - начало связного списка. Коллизия - ещё один узел в списке.

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

Зато у цепочек есть свойство, которого нет у остальных: адрес элемента не меняется при росте таблицы. Поэтому std::unordered_map в C++ до сих пор цепочечный - стандарт требует стабильных указателей. Ankerl в своём большом сравнении делит все таблицы ровно по этой линии: с устойчивыми указателями (узловые) и без (плоские). Плоские почти всегда быстрее.

Открытая адресация

Все элементы лежат в одном массиве. Ячейка занята - смотрим следующую по какому-то правилу, пока не найдём ключ или пустую ячейку.

Правила разные:

Аллокаций на элемент нет, всё в одном массиве, таблица целиком может жить в кэше. Цена - load factor: у линейного пробирования производительность быстро сыпется после 0.5-0.7.

Удаление - главная засада открытой адресации. Просто очистить ячейку нельзя: она могла быть звеном в чьей-то цепочке проб, и следующий поиск остановится на ней раньше времени. Поэтому в ячейку пишут маркер “здесь было удалено” - tombstone. Поиск его проходит насквозь, вставка может переиспользовать. Но tombstone копятся, и таблица с частыми удалениями медленно деградирует, пока её не пересоберут.

Robin Hood

Та же открытая адресация, но со справедливостью. У каждого элемента есть “дистанция” - насколько далеко он лежит от своей идеальной ячейки. При вставке, если новый ключ ушёл дальше от дома, чем тот, что сидит в ячейке, они меняются местами. Богатый уступает бедному.

В итоге дистанции выравниваются: каждый ключ лежит примерно на среднем расстоянии от своего места, длинных хвостов нет. Это позволяет держать load factor 0.7-0.9.

И удаление решается красиво: вместо tombstone - сдвиг назад. Следующие элементы сдвигаются на одну ячейку к дому, пока не встретится элемент на своём месте или пустота. Таблица всегда чистая.

thenumb.at после большого сравнения называет Robin Hood со сдвигом назад выбором по умолчанию. Rust так и делал - его HashMap был на Robin Hood до 2019 года, а потом перешёл на Swiss Table.

Цена - вставка дороже: перестановки.

Hopscotch

Компромисс между линейным пробированием и гарантией. Каждый ключ обязан лежать не дальше H ячеек от своего дома (обычно H = 32). У каждой ячейки есть битовая маска: какие из следующих H ячеек заняты “её” ключами.

Поиск - прочитать маску и проверить только отмеченные ячейки. Все они рядом, все в паре кэш-линий.

Вставка сложнее: если ближайшая пустая ячейка далеко, её “перепрыгиванием” подтаскивают ближе, переставляя элементы, которые могут подвинуться без нарушения своего окна. Отсюда название - классики.

Cuckoo

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

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

Теория красивая. На практике две ячейки - это два случайных похода в память, а чем плотнее таблица, тем длиннее цепочки вытеснений при вставке.

Swiss Tables

Google, 2017 год, Abseil. Открытая адресация, но поиск идёт не по ключам, а по отдельному массиву метаданных.

Слоты собраны в группы. На каждый слот - один байт метаданных (control byte): пусто, удалено, или 7 бит хеша ключа. Хеш делится на две части: старшие биты (H1) выбирают группу, младшие 7 бит (H2) лежат в control byte.

Поиск:

1. По H1 найти группу.
2. Сравнить H2 со всеми control byte группы одной операцией: SIMD-инструкцией или битовыми трюками над 64-битным словом (SWAR).
3. Получить маску совпадений. Сравнить настоящий ключ только в отмеченных слотах.
4. Если в группе есть пустой слот - ключа нет, стоп. Иначе - следующая группа.

Шаг 2 - вся соль. Семь бит хеша отсекают 127 из 128 чужих ключей без чтения самих ключей. На промахе до сравнения ключей дело почти не доходит. А метаданные компактны: в Go control word группы - 8 байт, одна загрузка.

Отсюда высокий load factor 87.5%: даже при плотной таблице поиск остаётся коротким.

Размер группы зависит от реализации. В Abseil на SSE2 - 16 слотов (отсюда “16 слотов параллельно” в некоторых пересказах). В Go - 8 слотов и 8-байтовое control word.

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

Сейчас Swiss Table - это Abseil, Rust (hashbrown) и, с 1.24, встроенный map в Go.

Когда нужен порядок

Хеш-таблица не умеет “дай все ключи от A до B” и “следующий после X”. Для этого - деревья.

B-дерево. Не бинарное: в каждом узле от B-1 до 2B-1 ключей в непрерывном массиве. Поиск - бинарный поиск внутри узла плюс переход вниз. Узлов мало, ключи в узле лежат подряд, кэш доволен. Порядок обхода детерминирован, ресайзов-скачков нет. Минусы: памяти больше, чем у хеш-таблицы, по оценке автора - на 60% и более из-за недозаполненных узлов, и на строках с общими префиксами сравнения дорожают. В stdlib Go деревьев нет вообще - только google/btree, tidwall/btree и подобные.

Skip list. Пью, 1989 год. Отсортированный связный список с “экспресс-полосами”: каждый узел с вероятностью 1/2 поднимается на уровень выше. Поиск идёт сверху, по длинным прыжкам, и спускается. В среднем O(log n), в худшем O(n). Плюс один: нет ротаций, вставка локальна, и в многопоточной версии блокируются только соседние узлы. Поэтому skip list живёт там, где важна конкурентная запись в упорядоченное: Redis ZSET и memtable в RocksDB. Минус - 72-86 байт на узел и прыжки по указателям.

ART (adaptive radix tree). Префиксное дерево, где ключ разбирается по байтам. Обычный trie тратит 256 указателей на каждый узел. ART держит четыре типа узлов - на 4, 16, 48 и 256 детей - и меняет тип по мере заполнения. Плюс сжатие общих префиксов. Поиск стоит O(длина ключа) и не зависит от числа элементов. Умеет диапазоны и поиск по префиксу, которых нет у хеш-таблиц. Минус - аллокации на вставке.

Сводка

Go map: до 1.24 и после

До 1.24: бакеты

Массив бакетов. В каждом 8 пар ключ-значение, причём 8 ключей подряд, потом 8 значений - чтобы не терять место на выравнивании. Плюс 8 байт tophash - верхние биты хеша каждого слота, тот же трюк с отсечением, что и в Swiss. Бакет переполнился - к нему цепляется overflow-бакет, отдельной аллокацией.

То есть это гибрид: внутри бакета - маленький плоский массив, снаружи - цепочки бакетов. Load factor - около 81.25% (6.5 элемента на бакет из 8).

Рост - вдвое, с постепенной эвакуацией: каждая запись переносит пару старых бакетов в новый массив. Пиков задержки нет, но обе таблицы живут одновременно.

После 1.24: Swiss Tables с каталогом

Go 1.24 переписал map целиком. Внутри - Swiss Table: группы по 8 слотов, control word на 8 байт, 57 бит хеша на выбор группы, 7 бит - в control byte. Пробирование между группами - треугольное: +1, +2, +3 группы. Load factor - 7/8.

Но одна большая Swiss Table плохо растёт: удвоение - это пересборка всего массива разом, и запись, на которую оно пришлось, ждёт. В C++ с этим живут. Go так не может: у него гарантия, что рост map не даёт скачков задержки.

Поэтому map в Go - не одна таблица, а каталог таблиц. Расширяемое хеширование: верхние биты хеша выбирают таблицу в каталоге, каждая таблица - отдельная Swiss Table до 128 групп, то есть 1024 слотов. Переполнилась одна - делится только она, остальные не трогаются. Худший случай роста ограничен пересборкой 1024 слотов.

Ещё два Go-специфичных требования, которых нет в Abseil:

• Изменять map во время обхода можно. Итератор держит ссылку на таблицу, которую обходит, даже если она уже разделилась.
• Память после удаления не возвращается. Ни старая, ни новая map не сжимаются. Map, которая один раз выросла до миллиона, так и держит миллион слотов. Если это проблема - копируйте в новую.

Что это дало. Datadog пишет про -70% памяти на больших map в своей нагрузке. На уровне целых программ эффект скромнее: release notes говорят про 2-3% CPU вместе с другими улучшениями рантайма, набор Sweet - про 1.5%. Map редко доминирует в профиле.

Конкурентные карты Go

Встроенный map не потокобезопасен. Одновременная запись из двух горутин обычно заканчивается fatal error: concurrent map writes. Варианты защиты - это отдельный зоопарк механизмов.

Несколько вещей, которые не очевидны.

RWMutex не масштабирует чтение так, как обещает название. Каждый RLock атомарно меняет общий счётчик читателей. Эта кэш-линия гуляет между ядрами, и на многоядерной машине читатели мешают друг другу почти как писатели.

sync.Map до 1.24 и после - разные структуры. Раньше - две карты, read и dirty, и он был хорош только в двух сценариях: кэш, который только растёт, и запись в непересекающиеся ключи. С 1.24 внутри hash trie, и советы из старых статей про sync.Map устарели.

Число шардов - это потолок. У orcaman/concurrent-map их 32, и это зашито. На машине с 64 ядрами 32 мьютекса - узкое место.

CLHT - это про кэш-линии, а не про блокировки. Бакет размером ровно в кэш-линию значит, что обновление гоняет между ядрами не больше одной линии. Чтение ничего не пишет в память и поэтому не инвалидирует чужие кэши.

V8: Map и Object

Map

Детерминированная хеш-таблица Тайлера Клоуза. Два массива: hashTable - индексы бакетов, dataTable - сами записи в порядке вставки, вдвое длиннее. Каждая запись хранит ключ, значение и номер следующей записи в той же цепочке.

То есть это цепочки, но цепочки внутри одного массива, без отдельных аллокаций на узел. Обход идёт по dataTable подряд - отсюда гарантированный спецификацией порядок вставки и быстрая итерация.

Ёмкость - степень двойки, load factor 2: на бакет в среднем две записи. Удалённая запись остаётся дыркой в dataTable до следующей пересборки. Рост - пересборка O(N) в новую таблицу, без инкрементальности, как в Go. Память - около 29 МБ на миллион записей на 64-битной системе без сжатия указателей.

Object

Object - не хеш-таблица. По крайней мере, пока вы им не злоупотребили.

Быстрый режим. V8 описывает форму объекта скрытым классом: какие свойства и в каком порядке. Объекты одной формы делят класс, свойства лежат по фиксированным смещениям, а inline-кэш в месте вызова запоминает смещение. Доступ к полю - одна загрузка без хеширования. Добавление свойства - переход по дереву переходов к следующему скрытому классу.

Это идеально для записей с фиксированной структурой и бесполезно для словаря с тысячами разных ключей.

Режим словаря. Когда ключей много, когда они динамические или когда вы удалили не последнее добавленное свойство, объект переходит в режим словаря - собственная хеш-таблица на каждый объект. Медленнее быстрого режима и в разы прожорливее.

Целые ключи - отдельная история. Ключи-индексы V8 хранит не в свойствах, а в elements, как у массива. Плотные индексы - массив, разреженные - тоже хеш-таблица. А спецификация требует при обходе отдавать целочисленные ключи по возрастанию, независимо от порядка вставки и от того, как они хранятся.

Отсюда стандартный совет: динамические ключи с частыми вставками и удалениями - в Map, не в Object.

Что брать

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

А сколько это стоит в наносекундах на конкретной машине - в следующей статье. Там я перемерил всё перечисленное одной методикой, на Go и на JS, и не всё совпало с тем, что пишут.