Хотелось бы прокомментировать публикацию Ильи Кабанова в Медузе по поводу новых разработок в алгоритмах хеширования: "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.
В заключение, отвечая Илье Кабанову: к "ускорению интернета" новые теоретические алгоритмы не приведут :)
