В своей работе 1985 года информатик Эндрю Яо, позже ставший лауреатом премии Тьюринга, доказал, что для хеш-таблиц с открытой адресацией лучший способ поиска элемента или пустой ячейки — это случайный перебор возможных мест. Такой подход называется универсальным хешированием. Яо также предположил, что в худшем случае, когда необходимо найти последнюю свободную ячейку, нельзя обойтись без затрат времени, пропорциональных x. Если хеш-таблица заполнена на 99%, то, вероятно, придется проверить около 100 разных позиций, чтобы найти свободное место.
В конце 2021 года на тот момент студент Ратгерского университета Эндрю Крапивин (в своей недавней презентации исследователь представляется именно так; в 2020 году в беседе с жившим в Украине дедом он называл себя Андреем) случайно наткнулся на публикацию про уменьшение размеров указателей в памяти компьютера. Через несколько лет он вернулся к этой статье, перечитал ее и понял, что можно добиться того, что указатели будут занимать еще меньше памяти. Однако для этого нужно улучшить саму организацию данных, к которым указатели будут направлять.
Крапивин обратил внимание на хеш-таблицы и в процессе работы неожиданно для себя создал их новый тип, который оказался значительно быстрее. Его таблица позволяла находить элементы за меньшее время и с меньшими усилиями.
Ссыкли:
- https://www.youtube.com/watch?v=ArQNyOU1hyE
- https://arxiv.org/abs/2111.12800
- https://www.quantamagazine.org/undergraduate-upends-a-40-year-old-data-science-conjecture-20250210/
Что конкретно предлагает-то? Я просмотрел его презентацию, но сложилось впечатление, что парень переизобрел то ли последовательный сдвиг индекса если ячейка занята, то ли хранить в ячейке не один элемент, а список элементов с одним хэшом.
Соль то в чем?
P.S. Также в тред приглашаются свидетели движения «математика программисту не нужна»
