Является ли этот подход к работе с хеш-коллизиями новым / уникальным?
Работая с хэш-картами, я видел несколько стратегий борьбы с хеш-коллизиями, но мы придумали что-то другое. Мне было интересно, если это что-то новое или нет.
Эта версия хеш-карты работает только в том случае, если хеш и структуры данных, которые будут хешироваться, можно реализовать.
(Это случай в hashable в Haskell, где мы предложили реализовать этот подход.)
Идея состоит в том, что вместо хранения списка или массива в каждой ячейке хэш-карты вы сохраняете рекурсивную хеш-карту. Единственная разница в этой рекурсивной хэш-карте заключается в том, что вы используете другую соль. Таким образом, хеш-коллизии на одном уровне хеш-карты, скорее всего, не являются хеш-коллизиями на следующем уровне. В результате вставка в такую карту хеша больше не O(количество столкновений в этом хеше), а O(число уровней, на которых столкновения происходят на рекурсивном уровне), что, скорее всего, лучше.
Более подробное объяснение и реализацию можно найти здесь:
1 ответ
Ваша идея, по-видимому, практически совпадает с той, которая была предложена в статье Фредмана, Комлоса и Семереди от 1984 года. Как подытоживает Википедия:
Хэширование FKS использует хеш-таблицу с двумя уровнями, в которой верхний уровень содержит n сегментов, каждый из которых содержит свою собственную хеш-таблицу.
В отличие от вашей идеи, локальные хеш-карты не являются рекурсивными, вместо этого каждая из них выбирает соль, которая делает ее идеальным хешем. На практике это (как вы говорите) обычно дается уже первой солью, которую вы пробовали, таким образом, это асимптотически постоянное время.