Зондирование каждое место R'th хэширования

Question

Что-то мне было интересно из моей лекции:

Предположим, что мы хотим, чтобы исследовать каждый Rth место для функции х мод 10 и R = 2. Теперь хэш 4, 14 , 114, 1114 и 11114:

• 4 будет идти в слоте 4.
• 14 сначала попытается попасть в слоте 4, но, видя, что он полон, он будет идти в слоте 6, то (+ Р).
• 114 найдет слот 4 полный, перейдя в слот 6 (+ R), но так как он заполнен, он перейдет в Slot 0 (+ 2R).

Но для 1114 года, похоже, продолжается вечно - независимо от того, куда он идет, он всегда будет работать в полный слот. Что происходит в этом случае?

Answer 1

Есть три варианта неразрешимых хэш столкновений на открытой адресации хэш-таблиц:

1. пересказом всей таблицы с другой хеш-функции, и надеемся, что новые неразрешимые хэш столкновения не происходит.
2. Измените размер стола (со всеми возможными операциями), чтобы гарантировать еще несколько возможных слотов.
3. Сохраните отдельный список для неразрешимых хеш-коллизий.

Ни один из этих вариантов не является хорошим.

Что вы должны сделать, это тщательно выбрать метод зондирования в сочетании с размером хэш-таблицы. Если ваш размер таблицы был нечетным, с тем же постоянным шагом, вы бы не запускали эту проблему, хотя в таблице все еще было место.

Популярные комбинации включают в себя квадратичное зондирование с хэш-таблицей размера, которая гарантирует успех вставки, если таблица меньше половины, и quadratic probing with triangular numbers and power of 2 hash table, что гарантирует вставку, если таблица не заполнена. Мощность 2-х хэш-таблиц имеет много преимуществ, единственный недостаток заключается в том, что они неумолимы по качеству алгоритма хеширования.