Что делать, если функция двойного хэширования также не удалась

Рассмотрим вставку ключей 10, 22, 31, 9, 15, 28, 62, 88 в хеш-таблицу длины m = 11, используя открытую адресацию с хеш-функцией h(k) = k mod m. Проиллюстрируйте результат вставки этих ключей с помощью двойного хеширования с h2(k) = 1 + (k mod(m-1)).

Ниже приведен мой подход.

0 -> 22 , Since 22 mod 11 = 0
1 ->
2 ->
3 ->
4 ->
5 ->
6 ->
7 ->
8 ->
9 -> 31 , Since 31 mod 11 = 9
10 -> 10 , Since 10 mod 11 = 10

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

h(9) = 9 mod 11, то есть 9. Я не могу поставить 9, так как 9 уже нет. Затем я пытаюсь получить двойную хеш-функцию, заданную h2(9) = 1 + (9 mod (11-1)) , что равно 10, и она снова исчезла. Так что я все еще не могу поставить 9 в хеш-таблицу. Что мне делать в таких случаях.


hash data-structures hashtable double-hashing
person Prasad Rajapaksha    schedule 11.05.2012    source источник

Ответы (2)


arrow_upward
3
arrow_downward

Используйте две хеш-функции следующим образом:

hi=(h(key)+i*h1(key))％m 0≤i≤m-1

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

Таким образом, список адресов, по которым вы будете искать ключ, выглядит следующим образом:

h(key), h(key)+h1(key), h(key)+2*h1(key), ... , h(key)+n*h1(key)
person yjshen    schedule 11.05.2012
comment
Спасибо за ответ. Я проверю это. - person Prasad Rajapaksha; 11.05.2012
comment
Спасибо, я нашел способ опубликовать его в качестве ответа. - person Prasad Rajapaksha; 11.05.2012
comment
Что, если увеличение i снова и снова не может решить коллизию, настолько, что это приводит к целочисленному переполнению и, в конечном итоге, к отрицательному индексу? Что можно сделать тогда? - person M. Samil Atesoglu; 28.04.2020

arrow_upward
0
arrow_downward

Наконец я смог найти ответ, используя объяснение вики. http://en.wikipedia.org/wiki/Double_hashing

h(9) = 9 по модулю 11, что равно 9.

h2(9) = 1 + (9 mod (11-1)), что равно 10.

Таким образом, ключ должен быть (9 + 10) по модулю 11, что равно 8.

тогда

8 -> 9

person Prasad Rajapaksha    schedule 11.05.2012