Хеширование (двойное хеширование без перефразировки)

Question

Это вопрос:

Использует открытую адресацию с помощью двойного хеширования, и основная хеш-функция hi(x) = (hash(x) + f(i)) mod M, где hash(x) = x mod M а также f(i) = i ∗ hash2(x) а также hash2(x) = 13 − (x mod 7),

Мне нужно вставить ключи 27, 22, 16, 26, 47, 12, 42, 3 (в этом порядке). Набор размером 10

This is what i have so far:
0 []
1 []
2 [22]
3 []
4 []
5 []
6 [16]
7 [27]
8 []
9 []

Я запутался, вставив 26, потому что это двойной удар.... Кто-нибудь может объяснить, как это сделать и что происходит?

Answer 1

Риск показать мое невежество, как я и М определены? Я бы предположил, что M равен размеру, и предположил бы, что я счетчик количества вставок, но это не добавит к вашему выводу. Однако моя реализация сталкивается не с 26, а с 42, что означает, что до коллизии использовалось более половины пространства ключей.

---

Но потом я понял, что если указать, что мне нравится, позиция будет зависеть от порядка вставки.

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

Может ли кто-нибудь улучшить мои дикие догадки?

---

Хорошо, давайте развернем это тогда.

hash(x) = x % M
hash2(x) = 13 - (x % 7)
f(i) = i * hash2(x)
hi(x) = (hash(x) + f(i)) % M

для: i=0, M=10, x=27

hash(x) = 27 % 10 -> 7
hash2(x) = 13 - (27 mod 7) -> 7
f(i) = 0 * 7 - > 0
hi(x) = (7 + 0) % 10 -> 7

для: i=1, M=10, x=22

hash(x) = 22 % 10 -> 2
hash2(x) = 13 - (22 mod 7) -> 12
f(i) = 1 * 12 - > 12
hi(x) = (12 + 12) % 10 -> 4

для: i=2, M=10, x=16

hash(x) = 16 % 10 -> 6
hash2(x) = 13 - (16 mod 7) -> 11
f(i) = 2 * 11 - > 22
hi(x) = (6 + 22) % 10 -> 8

и так далее, как вы можете видеть, это довольно быстро расходится с тем, что у вас было

Answer 2

У меня есть сомнения в том, что предложил r_ahlskog. Разве мы не должны увеличивать i только тогда, когда происходит столкновение. Поскольку 26 заканчивается столкновением, мы должны увеличить i t0 1, и в это время 26 разрешается в слот m = 4.

    M = 10 (no. of slots)   
    hi(x) = (hash(x) + f(i)) mod M   (6+0) mod 10 = 14 mod 10 = 6
                                    (6+8) mod 10 = 14 mod 10 = 4
    hash(x) = x mod M                      26 mod 10 = 6

    f(i) = i ∗ hash2(x)           (i=0)  0 * 8 = 0
                                          (i=1) 1 * 8 = 8

    hash2(x) = 13 − (x mod 7)             13 - (26 mod 7) = 13-5=8

hi (x) становится 6 для i=0 и для i=1 его 4.

Поправьте, если мое понимание неверно.

Вот окончательный ответ -

[0]=12;
[1]=42;
[2]=22;
[3]=3;
[4]=26;
[5]=47;
[6]=16;
[7]=27;

Слоты 8 и 9 свободны.

Столкновение произошло и за 42. Это было решено при i=3.