Является ли этот подход к работе с хеш-коллизиями новым / уникальным?

Question

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

Эта версия хэш-карты работает только в том случае, если хеш и структуры данных, которые будут хешироваться, можно реализовать.(Это имеет место в hashable в Haskell, где мы предложили реализовать этот подход.)

Идея состоит в том, чтобы вместо хранения списка или массива в каждой ячейке хэшакарта, вы храните рекурсивную хэш-карту.Единственная разница в этой рекурсивной хэш-карте заключается в том, что вы используете другую соль.Таким образом, коллизии хешей на одном уровне карты хешей, скорее всего, не являются коллизиями хешей на следующем уровне.В результате вставка в такую ​​карту хэша больше не O (количество столкновений в этом хеше), а O (число уровней, на которых столкновения происходят на рекурсивной основе), что, скорее всего, лучше.

Более подробное объяснение и реализацию можно найти здесь:

https://github.com/tibbe/unordered-containers/pull/217/files/58af4519ace34c5f7d3c1359907ff75e27b9cdb8#diff-ba23e0f18c79cb873ac5375367524cfaR114

Answer 1

Ваша идея, по-видимому, практически совпадает с той, которая была предложена в статье Фредмана, Комлоса и Семереди от 1984 .Как Википедия обобщает это :

Хеширование FKS использует хеш-таблицу с двумя уровнями, в которой верхний уровень содержит n сегментов, каждый из которых содержит свою собственную хеш-таблицу.

В отличие от вашей идеи, локальные хеш-карты не являются рекурсивными, вместо этого каждая из них выбирает соль, которая делает ее идеальным хешем.На практике это (как вы говорите) обычно дается уже первой солью, которую вы пробовали, таким образом, это асимптотически постоянное время.