Исследование каждого R-го местоположения для хеширования

Question

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

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

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

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

Answer 1

Существует три варианта неразрешимых коллизий хешей в хеш-таблицах с открытой адресацией:

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

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

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

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