Что если коллизия все еще существует после применения алгоритма двойного хеширования? - PullRequest
Новая
       24

Что если коллизия все еще существует после применения алгоритма двойного хеширования?

0 голосов
/ 20 мая 2018

У меня есть хеш-таблица размера 8, куда я хочу вставить значения (0, 1, 8, 9, 5, 33).
Я пробовал это с хэшированием, которое имеет конфликт, затем я попробовал алгоритм двойного хешированияно столкновение все же происходит следующим образом:

Хеширование = H1 (k) = k% 8
Двойное хеширование = H2 (k) = M - (k% M) 

H1(0) = 0 % 8 = 0   
H1(1) = 1 % 8 = 1  
H1(8) = 8 % 8 = 0 -----> Needs double hashing ----> 7-(8 % 7)=7-1=6 (we forward 6 steps from the current position which is 0 and it will become 6).  
H1(9) = 9 % 8 = 1----> Needs double hashing ---> 7 - (9%7)=7-2=5(we forward 5 steps from the current position which is 1 and it will become 6 again).

Теперь я застрял здесь, и я не знаю, что делать.Примечание: я не хочу использовать какой-либо другой метод, я хочу использовать только двойное хеширование.
Любая помощь приветствуется заранее.

Ответы [ 2 ]

0 голосов
/ 20 мая 2018

Вы должны использовать алгоритм двойного хеширования, как и предполагалось.

Как уже упоминалось в этой очень хорошей статье :

Двойное хеширование может быть выполнено с использованием: 

(hash1(key) + i * hash2(key)) % TABLE_SIZE

Здесь hash1 () и hash2 () являются хеш-функциями, а TABLE_SIZE - размером хеш-таблицы.(Мы повторяем, увеличивая i, когда происходит столкновение)

И приведенный пример (в вашем случае): 

H1(0) = 0 % 8 = 0   
H1(1) = 1 % 8 = 1  
H1(8) = 8 % 8 = 0
   H2(8) = 7 - (8 % 7)= 7-1 = 6
   // double hashing algorithm start : i == 1
   (H1(8) + i*H2(8)) % TABLE_SIZE = (0 + 1*6) % 8 = 6       

H1(9) = 9 % 8 = 1
   H2(9) = 7 - (9 % 7)= 7-2 = 5
   // double hashing algorithm start : i == 1
   (H1(9) + i*H2(9)) % TABLE_SIZE = (1 + 1*5) % 8 = 6 --> collision (increment i to 2)
   (H1(9) + i*H2(9)) % TABLE_SIZE = (1 + 2*5) % 8 = 3 --> no collision

Дополнительные ссылки:

Бонус:

0 голосов
/ 20 мая 2018

При двойном хешировании вы повторяете второй шаг хеширования, пока не найдете свободное место.Процесс состоит в том, чтобы продолжать добавлять H2 (k) к последнему индексу (размер по модулю), чтобы генерировать следующий индекс.

В вашем примере это означает:

H1 (9) = 9% 8 = 1
H2 (9) = 7 - (9% 7) = 5

Попытки пятна: 1, 6, 3, 0, 5, 2, 7, 4

Таким образом, значение 9 будет сохранено в индексе 3.

...