О новых алгоритмах хеш-таблиц
Хотелось бы прокомментировать публикацию Ильи Кабанова в Медузе по поводу новых разработок в алгоритмах хеширования: " Optimal Bounds for Open Addressing Without Reordering " (Farach-Colton, Krapivin, and Kuszmaul, 2025) и последующую " The Bathroom Model: A Realistic Approach to Hash Table Algorithm Optimization " (Wang, 2025). И особенно кликбейтное: "в перспективе метод Крапивина и его коллег может ускорить многие процессы в интернете." Я около 7 лет очень плотно занимался темой хеш-таблиц и написал много их вариантов: Koloboke , SmoothieMap , memory-mapped вариации . Я потерял к теме интерес с выходом гугловской SwissTable (2018), и ее фейсбучного варианта F14 , которые основаны на SIMD. Они проверяют загруженность ячеек и совпадения "тега" элемента сразу блоками по 8 соседних слотов. Поэтому на любых разумных загрузках таблиц (до 90%) - "цепочка проверки" очень редко превышает 1 (то есть, одну проверку 8-элементного блока). В этих SIMD-based алгоритмах, ухищрения и теоретические по поводу "алгоритма шагания" просто не играют никакой роли -- алгоритм шагания можно сказать отсутствует, потому что если можно вставить элемент внутри 8-элементного блока, то это и стоит сделать. Именно эти разработки, а не Крут и не статья Yao, которую "опровергли" новые работы, стали "практическим концом теории" хеш-таблиц, на мой взгляд. SwissTable стали стандартным алгоритмом хеш-таблиц в Расте, и, буквально в этом месяце, в Golang 1.24 . В заключение, отвечая Илье Кабанову: к "ускорению интернета" эти теоретические алгоритмы не приведут :)
https://habr.com/ru/articles/887024/