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

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

Линейный зонд, в основном, имеет шаг 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?

РЕДАКТИРОВАТЬ: После прочтения всего, что указано Эли Бендерски ниже, я думаю, что я понял общую идею. Вот часть кода на 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?

Источник

2 ответа

Решение

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

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

альтернативный текст

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

альтернативный текст

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

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

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

РЕДАКТИРОВАТЬ: Как и многие вещи в информатике, точные константы и полиномы квадратичного зондирования являются эвристическими. Да, самая простая форма 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*(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
  3. т.е. (p * (p + 1)) / 2 = (q * (q + 1)) / 2 (mod n)
  4. => (p2 + p) / 2 = (q2 + q) / 2 (mod n)
  5. => p2 + p = q2 + q (мод 2n)
  6. => q2 - p2 + q - p = 0 (мод 2n)
  7. Factorise => (q - p) (p + q + 1) = 0 (mod 2n)
  8. (q - p) = 0 - тривиальный случай p = q.
  9. (p + q + 1) = 0 (mod 2n) невозможно: наши значения p и q находятся в диапазоне [0, n-1], и q > p, поэтому (p + q + 1) должно быть в диапазон [2, 2n-2].
  10. Поскольку мы работаем по модулю 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.
    • Так что этот случай тоже невозможен.
  11. Следовательно, предположение о том, что существует менее n различных значений (на шаге 2), должно быть ложным.

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

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