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

https://stackoverflow.com/questions/2348187

23-09-2019
|

Вопрос

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

Линейное зондирование, по сути, имеет шаг 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 */);

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

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

Редактировать: Прочитав все, на что указал Эли Бендерский ниже, я думаю, что у меня сложилась общая идея.Вот часть кода по адресу 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   }

Есть 2 вещи, которых я не понимаю...Они говорят, что квадратичное зондирование обычно выполняется с использованием 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?

Решение

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

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

alt text

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

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

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

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

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

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

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

Другие советы

Существует особенно простой и элегантный способ реализовать квадратичное зондирование, если размер вашей таблицы равен степени 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*(i+1))/2, т.е.это квадратично).

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

Вот набросок доказательства:

Учитывая размер таблицы n, мы хотим показать, что мы получим n различных значений (i * (i + 1))/ 2 (mod n) при i = 0 ...n-1.
Мы можем доказать это с помощью противоречия.Предположим, что существует менее n различных значений:если это так, то для i в диапазоне [0, n-1] должно быть по крайней мере два различных целых значения, таких, что (i *(i+1))/2 (mod n) одинаковы.Назовем их p и q, где p < q.
т. е.(p * (p+1)) / 2 = (q * (q+1)) / 2 (mod n)
=> (p² + p) / 2 = (q² + q) / 2 (mod n)
=> p² + p = q² + q (мод 2n)
=> q² - п² + q - p = 0 (mod 2n)
Разложить на множители => (q - p) (p + q + 1) = 0 (mod 2n)
(q - p) = 0 - это тривиальный случай p = q .
(p + q + 1) = 0 (mod 2n) невозможно:наши значения p и q находятся в диапазоне [0, n-1], а q > p, поэтому (p + q + 1) должно быть в диапазоне [2, 2n-2].
Поскольку мы работаем по модулю 2n, мы также должны иметь дело со сложным случаем, когда оба фактора отличны от нуля, но умножаются на 0 (mod 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.
- Так что этот случай тоже невозможен.
Следовательно, предположение о том, что существует менее n различных значений (на шаге 2), должно быть ложным.

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

Лицензировано под: CC-BY-SA с атрибуция

Не связан с StackOverflow