О новых алгоритмах хеш-таблиц

Хотелось бы прокомментировать публикацию Ильи Кабанова в Медузе ^[1] по поводу новых разработок в алгоритмах хеширования: "Optimal Bounds for Open Addressing Without Reordering ^[2]" (Farach-Colton, Krapivin, and Kuszmaul, 2025) и последующую "The Bathroom Model: A Realistic Approach to Hash Table Algorithm Optimization ^[3]" (Wang, 2025). И особенно кликбейтное: "в перспективе метод Крапивина и его коллег может ускорить многие процессы в интернете."

Я около 7 лет очень плотно занимался темой хеш-таблиц и написал много их вариантов: Koloboke ^[4], SmoothieMap ^[5], memory-mapped вариации ^[6].

Я потерял к теме интерес с выходом гугловской SwissTable ^[7] (2018), и ее фейсбучного варианта F14 ^[8], которые основаны на SIMD. Они проверяют загруженность ячеек и совпадения "тега" элемента сразу блоками по 8 соседних слотов. Поэтому на любых разумных загрузках таблиц (до 90%) - "цепочка проверки" очень редко превышает 1 (то есть, одну проверку 8-элементного блока).

В этих SIMD-based алгоритмах, ухищрения и теоретические по поводу "алгоритма шагания" просто не играют никакой роли -- алгоритм шагания можно сказать отсутствует, потому что если можно вставить элемент внутри 8-элементного блока, то это и стоит сделать.

Именно эти разработки, а не Кнут и не статья Yao, которую "опровергли" новые работы, стали "практическим концом теории" хеш-таблиц, на мой взгляд.

SwissTable стали стандартным алгоритмом хеш-таблиц в Расте, и, буквально в этом месяце, в Golang 1.24 ^[9].

В заключение, отвечая Илье Кабанову: к "ускорению интернета" новые теоретические алгоритмы не приведут :)