Хеш-таблица quadrtc. зондирование

Question

Нужен пример

Мне нужно указать размер таблицы и элементов, которые я пытался вставить, которые я не смог вставить из-за столкновения после того, как таблица заполнена более чем наполовину.

Я пробовал несколько разных входных данных для размера таблицы с помощью функции: h of i (x) = (hash (x) + f (i)) mod table size

f (i) = i ^ 2

Буду признателен за любую помощь, спасибо.

Answer 1

Для таблицы размера 7 предположим, что места 0, 1, 2, 4 взяты, 3, 5, 6 свободны. Теперь попробуйте вставить х, где хэш (х) = 0.

Пример: возьмем hash(x) = x % 7.

Insert 0: hash(0) = 0, this slot is free so insert 0 into slot 0
Insert 1: hash(1) = 1, this slot is free so insert 1 into slot 1
Insert 2: hash(2) = 2, this slot is free so insert 2 into slot 2
Insert 4: hash(4) = 4, this slot is free so insert 4 into slot 4
Insert 7: hash(7) = 0, slot 0 is already taken; start quadratic probing:
(0+1*1)%7 = 1 also taken
(0+2*2)%7 = 4 also taken
(0+3*3)%7 = 2 also taken
(0+4*4)%7 = 2 also taken
(0+5*5)%7 = 4 also taken
(0+6*6)%7 = 1 also taken
...