нужен примерHash table quadrtc. зондирования
мне нужно указать размер таблицы и элементы, которые я попытался вставить, что я не мог вставить из-за столкновения после того, как таблица больше, чем наполовину.
Я попытался несколько различных входов на таблицу размеров, с функцией: ч I (х) = (хеш (х) + е (я)) мод размер таблицы
F (я) = i^2
Буду признателен за любую благодарность за помощь.
Для таблицы размера 7 предположим, что пятна 0, 1, 2, 4 взяты, 3, 5, 6 являются свободными. Теперь попробуйте вставить х, где хэш (х) = 0.
Пример: позволяет принимать хэш (х) = х% 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
...
Я с помощью 53,25,72,10,6 , 17,26; если он сталкивается, так как я увеличиваю его, он в конечном итоге находит пустое место для размещения следующего числа, мне нужна последовательность чисел, где он НЕ находит пятно, чтобы поместить следующий номер до заполнения таблицы. Вот где у меня возникают проблемы, кажется, что каждый вход я пытаюсь, если он сталкивается с другим значением уже на месте, так как i увеличивает значение f (i) = i^2; он всегда находит место в какой-то момент. Мне нужна некоторая последовательность чисел, где никогда не найдется места для добавления следующего элемента до заполнения таблицы. – ek1437
Для простоты возьмите hash (x) = x% 7. Теперь вставьте 0, 1, 2, 4, затем попробуйте 7. – Henry
, который будет линейным зондированием справа? Даже если бы я попытался использовать линейное зондирование, это было бы [x + f (i)] mod 7, где f (i) = i я все равно мог бы разместить 7 в 5-м индексе – ek1437