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

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

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

В более общем случае формула:

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

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

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

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

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

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

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

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, т. е. квадратичным).

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

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

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 ‹q.
3. то есть (p * (p + 1)) / 2 = (q * (q + 1)) / 2 (mod n)
4. => (p ² + p) / 2 = (q ² + q) / 2 (mod n)
5. => p ² + p = q ² + q (по модулю 2n)
6. => q ² - p ² + q - p = 0 (mod 2n)
7. Факторизация => (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, 2н-2].
10. As we are working modulo 2n, we must also deal with the tricky case where both factors are non-zero, but multiply to give 0 (mod 2n):
    • Observe that the difference between the two factors (q - p) and (p + q + 1) is (2p + 1), which is an odd number - so one of the factors must be even, and the other must be odd.
    • (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), должно быть ложным.

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