Переход от линейного зондирования к квадратичному зондированию (хэш-коллизии)

Question

Моя текущая реализация хэш-таблицы использует линейное зондирование, и теперь я хочу перейти к квадратичному зондированию (а затем и к цепочкам, а также, возможно, к двойному хешированию). Я прочитал несколько статей, учебных пособий, википедии и т. Д ... Но я до сих пор не знаю точно, что мне делать.

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

index = hash_function(key) % table_size;

Затем при поиске, вставке или удалении я перебираю таблицу, пока не найду свободное ведро, например:

do {
    if(/* CHECK IF IT'S THE ELEMENT WE WANT */) {
        // FOUND ELEMENT

        return;
    } else {
        index = (index + 1) % table_size;
    }
while(/* LOOP UNTIL IT'S NECESSARY */);

Что касается Quadratic Probing, я думаю, что мне нужно изменить метод расчета размера шага "index", но я не понимаю, как мне это делать. Я видел разные фрагменты кода, и все они несколько отличаются.

Кроме того, я видел несколько реализаций Quadratic Probing, в которых хеш-функция изменена, чтобы приспособиться к этому (но не ко всем). Это изменение действительно необходимо, или я могу избежать изменения хеш-функции и все еще использовать Quadratic Probing?

EDIT: Прочитав все, что указал Эли Бендерский ниже, я думаю, что получил общее представление. Вот часть кода на http://eternallyconfuzzled.com/tuts/datastructures/jsw_tut_hashtable.aspx:

15   for ( step = 1; table->table[h] != EMPTY; step++ ) {
16     if ( compare ( key, table->table[h] ) == 0 )
17       return 1;
18 
19     /* Move forward by quadratically, wrap if necessary */
20     h = ( h + ( step * step - step ) / 2 ) % table->size;
21   }

Есть две вещи, которые я не получаю ... Они говорят, что квадратичное зондирование обычно выполняется с использованием c(i)=i^2. Тем не менее, в приведенном выше коде, он делает что-то вроде c(i)=(i^2-i)/2

Я был готов реализовать это в моем коде, но я бы просто сделал:

index = (index + (index^index)) % table_size;

... а не:

index = (index + (index^index - index)/2) % table_size;

Во всяком случае, я бы сделал:

index = (index + (index^index)/2) % table_size;

... потому что я видел другие примеры кода, ныряющие вдвое. Хотя я не понимаю, почему ...

1) Почему вычитается шаг?
2) Почему он ныряет на 2?

Answer 1

Существует особенно простой и элегантный способ реализации квадратичного зондирования, если размер таблицы равен степени 2:

step = 1;

do {
    if(/* CHECK IF IT'S THE ELEMENT WE WANT */) {
        // FOUND ELEMENT

        return;
    } else {
        index = (index + step) % table_size;
        step++;
    }
} while(/* LOOP UNTIL IT'S NECESSARY */);

Вместо того, чтобы смотреть на смещения 0, 1, 2, 3, 4 ... от исходного индекса, это будет смотреть на смещения 0, 1, 3, 6, 10 ... (i ^th Зонд со смещением (i * (i + 1)) / 2, то есть он квадратичный).

Это гарантированно попадет на каждую позицию в хеш-таблице (поэтому вы гарантированно найдете пустое ведро, если оно есть) при условии размер таблицы равен степени 2.

---

Вот эскиз доказательства:

1. Учитывая размер таблицы n, мы хотим показать, что мы получим n различных значений (i * (i + 1)) / 2 (mod n) с i = 0 ... n-1.
2. Мы можем доказать это противоречием. Предположим, что существует меньше чем n различных значений: если это так, должно быть не менее двух различных целочисленных значений для i в диапазоне [0, n-1], таких что (i * (i + 1)) / 2 (mod n ) та же. Назовите эти p и q, где p т.е. (p * (p + 1)) / 2 = (q * (q + 1)) / 2 (mod n)
3. => (p ² + p) / 2 = (q ² + q) / 2 (мод n)
4. => p ² + p = q ² + q (мод 2n)
5. => q ² - p ² + q - p = 0 (mod 2n)
6. Factorise => (q - p) (p + q + 1) = 0 (mod 2n)
7. (q - p) = 0 - тривиальный случай p = q.
8. (p + q + 1) = 0 (mod 2n) невозможно: наши значения p и q находятся в диапазоне [0, n-1], а q> p, поэтому (p + q + 1) должно быть в диапазоне [2, 2n-2].
9. Поскольку мы работаем по модулю 2n, мы должны также разобраться с хитрым случаем, когда оба фактора отличны от нуля, но умножим, чтобы получить 0 (мод 2n):
   • Обратите внимание, что разница между двумя факторами (q - p) и (p + q + 1) равна (2p + 1), что является нечетным числом, поэтому один из факторов должен быть четным, а другой - быть странным.
   • (q - p) (p + q + 1) = 0 (mod 2n) => (q - p) (p + q + 1) делится на 2n. Если n (и, следовательно, 2n) является степенью 2 , для этого требуется, чтобы четный множитель был кратным 2n (потому что все простые множители 2n равны 2, тогда как ни один из простых факторов нашего странным фактором являются).
   • Но (q - p) имеет максимальное значение n-1, а (p + q + 1) имеет максимальное значение 2n-2 (как видно на шаге 9), поэтому ни один из них не может быть кратным 2n .
   • Так что этот случай тоже невозможен.
10. Следовательно, предположение о том, что существует менее n различных значений (на шаге 2), должно быть ложным.

(Если размер таблицы равен , а не , то есть степень 2, на шаге 10 это разделится).

Answer 2

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

Здесь есть хороший ресурс . Следующее взято оттуда. Это самая простая форма квадратичного исследования, когда используется простой полином c(i) = i^2:

В более общем случае формула имеет вид:

И вы можете выбрать свои константы.

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

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

---

РЕДАКТИРОВАТЬ: Как и многие вещи в информатике, точные константы и полиномы квадратичного зондирования являются эвристическими. Да, самая простая форма - i^2, но вы можете выбрать любой другой многочлен. Википедия приводит пример с h(k,i) = (h(k) + i + i^2)(mod m).

Поэтому трудно ответить на ваш вопрос «почему». Единственное «почему» здесь - зачем вообще нужно квадратичное зондирование? Возникли проблемы с другими формами исследования и получения кластерной таблицы? Или это просто домашнее задание или самообучение?

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