Почему HashMaps работают так быстро (C++ с нуля)

Как работает хеш-карта, и можно ли создать такую, которая превзойдёт std::unordered_map? Мы создаём её с нуля на C++, добавляем повседневный интерфейс реальной карты (удаление, любой тип ключа, элементы, которые никогда не перемещаются, квадратные скобки, вставка, поиск, вставка, размещение, удаление, очистка, итераторы, копирование и перемещение, собственный хеш и сравнение на равенство), сравниваем её с реальной картой, а затем продолжаем работу с открытой адресацией, тегами и SIMD. Три идеи: превратить ключ в позицию и сразу перейти к ней; как можно реже запрашивать память у компьютера; хранить искомые элементы близко друг к другу в памяти. Цепочка запросов обрабатывает коллизии, изменение размера списков делает их короткими, а подсчёт запросов к памяти (и, соответственно, уменьшение их количества) — вот что делает её быстрой. После этого каждая функция измеряется: если это влияет на скорость, мы выясним почему. Разделы 0:00 Вопрос: как найти одно число среди миллионов (и три идеи) 1:43 Почему список работает медленно 3:53 Ключ к номеру ячейки (хеш-функция, корзина) 9:40 Два ключа, одна корзина (коллизии, цепочки) 13:06 Расширение таблицы (коэффициент загрузки, рехеширование) 17:58 Догоняем реальный список (меньше запросов к памяти) 23:08 Что есть в реальном списке, чего нет в нашем (остановитесь здесь, если вас интересует только принцип работы) 24:16 Удаление и любой тип ключа (дыры в большом списке, шаблоны, std::hash) 28:05 Элементы, которые никогда не перемещаются (deque, наши собственные страницы) 30:03 Остальная часть повседневного интерфейса, проверка по сравнению с реальным списком, таблица результатов 33:50 Продолжение: открытая адресация, теги, SIMD (швейцарский синтаксис) таблицы) 38:50 Краткий обзор: три идеи Как это измерялось g++ 13.3 на WSL2 Ubuntu 24.04, -O2, -std=c++17, Intel Core i3-8100, работающий на одном ядре, лучший из 9 запусков после прогрева, объединенный в два процесса. «Настоящая» — это std::unordered_map, поставляемая с GCC 13 (libstdc++); другие стандартные библиотеки собираются по-разному. Каждая версия программы, показанная на панели кода, находится в code/ (ver-*.cpp) и была скомпилирована и протестирована (code/check_revs.py), включая случайное сравнение put/get/erase с std::unordered_map для готовых версий. Один миллион целочисленных ключей (в цепочке = завершенная карта цепочек v9, в открытой = завершенная карта SIMD с открытой адресацией): Вставка: стандартное время 196 мс, в цепочке 65 мс, в открытой цепочке 45 мс. Поиск, ключ присутствует: стандартное время 65 нс, в цепочке 37 нс, в открытой цепочке 27 нс. Поиск, ключ отсутствует: стандартное время 76 нс, в цепочке 26 нс, в открытой цепочке 9 нс. Удаление всех: стандартное время 266 мс, в цепочке 128 мс, в открытой цепочке 57 мс. Посещение каждого элемента: стандартное время 24,1 мс, в цепочке 1,3 мс, в открытой цепочке 8,0 мс. Стабильное соотношение операций получения/помещения/стирания (1 млн операций): стандартное время 90 мс, в цепочке 90 мс, в открытой цепочке 69 мс (совпадение с картой цепочек). Память на элемент: стандартная 36 Б, цепочка 24 Б, открытая 36 Б. Запросы памяти при вставке: стандартная 1000017, цепочка 1007, открытая 36. Имена ("номер ключа 123456", 100 000 из них): поиск при наличии 248 нс (стандартный) против 173 нс (цепочка), при отсутствии 209 нс против 104 нс, вставка 34 нс против 25 мс. Примечания В каждой гонке против реальной используется один и тот же набор инструментов (лучший из 9 запусков после разминки). Сравнение растущей и фиксированной таблиц — это более старый и простой метод измерения только нашей собственной карты. При миллионе записей SIMD-карта не лучше, чем версия только с тегами, для присутствующих ключей и удаления (см. видео); предварительная выборка помогла присутствующим ключам и навредила отсутствующим. Здесь доминирует задержка памяти, а не инструкции. Открытая адресация отказывается от гарантии того, что указатели на элементы останутся действительными при росте таблицы (стандарт этого требует, поэтому std::unordered_map нельзя построить таким образом). Наша цепочка отображений сохраняет эту гарантию, используя страницы по 1024 элемента. Не реализованы: пользовательские распределители памяти, дескрипторы узлов (извлечение, слияние), интерфейс корзины, гетерогенный поиск, equal_range, count (используйте contains), гарантии точных исключений; итератор возвращает пару K и V (а не пару константных K и V), поэтому не изменяйте ключ через него. Готовая цепочка отображений была проверена на std::unordered_map с помощью 400 000 случайных операций (operator[], insert, emplace, find, erase, at, clear, copy, move, reserve и другие), а также тестов на пользовательский хеш и равенство, константные отображения и стабильность указателей. Это учебная реализация повседневного интерфейса, а не замена для каждой функции. — Хэш суммы букв из первых глав — это учебный пример, а не что-то, что нужно использовать. Если это помогло: поставьте лайк...