Как квадратичному зондированию не удается найти место на следующей вставке, в то время как линейное зондирование всегда находит его?

Я делаю практический вопрос из практики структур данных

Вопрос
1. Линейный зонд будет (обведите один):
постепенно снижается производительность при добавлении большего количества значений
II.Может не найти место на следующей вставке
iii. Ни один из перечисленных

2. Квадратичное зондирование (обведите один кружок):
постепенно снижается производительность при добавлении большего количества значений
II.Может не найти место на следующей вставке
iii. Ни один из перечисленных

В соответствии с ключом ответа (по ссылке) ответ на 1 - это i, а ответ на 2 - на ii.

Я согласен с ответом на вопрос 1. Линейное зондирование изучит все возможности и при необходимости перенесет в начало хеш-таблицы. Поэтому он найдет место на следующей вставке. Если вы вставите набор значений, которые отображаются в один и тот же сегмент или рядом с ним, кластеризация приведет к снижению производительности.
Я понимаю, почему ответ на вопрос 2 не я. Квадратичные приращения зондов за разные приращения, чтобы избежать проблемы кластеризации. Однако некоторые могут объяснить интуицию, лежащую в основе того, как квадратичное зондирование "может не найти место при следующей вставке"
Квадратичная функция зондирования определяется с помощью (из Quadratic Probing)
n-й зонд ((h (k) + n2) mod TableSize), пока зонд не достигнет нуля (незанятый)

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

Источник

3 ответа

Решение

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

Допустим, размер таблицы равен 7, а h(k) равно 0. Для i-й итерации probe = i^2 mod 7. Я проверил все i менее чем 10000, и это всегда оценивается как 0, 1, 2 или 4 для любой я Ведра 3, 5 и 6 никогда не будут проверены.

Вот скрипт, который я использовал:

var hash_of_k = 0;
var table_size = 7;
var iteration_limit = 10000;
var buckets =  new Object();

//Probe buckets
for(var i=0; i<iteration_limit; i++){
  b = (hash_of_k+(i*i)) % table_size;
  buckets[b] = 1;
}

//Report which buckets were probed.
var buckets_probed = '';
for(b in buckets){
  buckets_probed += b + '  ';
}

alert(buckets_probed);

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

Источник

Я думаю, что вопрос в том, в каком случае квадратичное зондирование вообще не сможет найти следующее местоположение в случае столкновения.

В приведенном ниже примере я вижу, что квадратичное зондирование не может найти местоположение в случае столкновений с тем же результирующим ключом.

Допустим, размер хеш-таблицы равен 7.

Вот числа, которые будут вставлены 23, 39, 9, 16, 30.

h (k, i) = [h (k) + sqr (i)] mod 7, где h(k) = k mod 7.

for i = 0, h(k,0) = h(k)
for i = 1, h(k,1) = [h(k) + 1] mod 7
for i = 2, h(k,2) = [h(k) + 4] mod 7
for i = 3, h(k,3) = [h(k) + 9] mod 7

23 --> 23 % 7 = 2

39 --> 39 % 7 = 4

9  --> 9 % 7 = 2 <--- Collision
   2 + 1 = 3

16 --> 16 % 7 = 2 <--- Collision
   2 + 1 = 3 <--- Collision
   2 + 4 = 6

30 --> 30 % 7 = 2 <--- Collision

   2 + 1 = 3 <--- Collision

   2 + 4 = 6 <--- Collision
   2 + 9 = 4 <--- Collision
   2 + 16 = 4 <--- Collision
   2 + 25 = 6 <--- Collision
   2 + 36 = 3 <--- Collision
   2 + 49 = 2 <--- Collision
   2 + 64 = 3 <--- Collision
   2 + 81 = 6 <--- Collision
   2 + 100 = 4 <--- Collision
   2 + 121 = 4 <--- Collision
   2 + 144 = 6 <--- Collision
   2 + 169 = 3 <--- Collision
   2 + 196 = 2 <--- Collision
   2 + 225 = 3 <--- Collision
   2 + 256 = 6 <--- Collision
   2 + 289 = 4 <--- Collision
   2 + 324 = 4 <--- Collision
   2 + 361 = 6 <--- Collision
   2 + 400 = 3 <--- Collision

Это было бы в случае любой клавиши k с (размер k mod), равным 2 (например, 37, 44, 51, 58 и т. Д.

Источник

Чтобы выяснить, ищет ли h(k) + n^2 все возможности, нужно выяснить, принимает ли n ^ 2 все возможные значения в зависимости от размера хеш-таблицы - скажем, N. Таким образом, вам нужно знать, выбрав все N возможностей. для п вы можете иметь п ^ 2 принять все N возможных различных значений.

(-n) ^ 2 = n ^ 2, поэтому здесь представлены различные входные значения для функции квадрата, которые выдают одинаковые выходные значения. Таким образом, невозможно получить все N разных выходных значений, потому что есть конфликты между результатами разных входных значений.

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

Источник
Другие вопросы по тегам