Процедура квадратичного рехэширования предполагает, что процесс поиска резервных ячеек производится с использованием некоторой квадратичной функции, например такой:
Pi = а,2+Ь,+с. (2.6)
Хотя значения а, Ь, с можно задавать любыми, велика вероятность быстрого зацикливания значений р(. Поэтому в качестве рекомендации опишем один из вариантов реализации процедуры квадратичного рехэширования, позволяющий осуществить перебор всех элементов хэш-таблицы [32]. Для этого значения в формуле (2.6) положим равными: а=1,Ь = с = 0. Размер таблицы желательно задавать равным простому числу, которое определяется формулой М = 4п+3, где п — целое число. Для вычисления значений р> используют одно из соотношений:
pi = (K+i2)modM. (2.7)
Pi = [M+2K-(K+i2)modM]modM. (2.8)
где i = 1, 2, ..., (M-l)/2; К — первоначально вычисленный хэш-адрес.
Адреса, формируемые с использованием формулы (2.7), покрывают половину хэш-таблицы, а адреса, формируемые с использованием формулы (2.8), — вторую половину. Практически реализовать данный метод можно следующей процедурой.
- 1. Задание I = -М.
- 2. Вычисление хэш-адреса К одним из методов хэширования.
- 3. Если ячейка свободна или ключ элемента в ней совпадает с искомым ключом, то завершение процесса поиска. Иначе, 1:=1+1.
- 4. Вычисление h := (h+|i|)modM.
- 5. Если I < М, то переход к шагу 3. Иначе (если I > М), таблица полностью заполнена.
Программа та же, что приведена в методе линейного
рехэширования, за исключением добавления одной команды для инициализации
процесса рехэширования, самого фрагмента рехэширования и небольших
изменений сегмента данных. могут являться методы, основанные на деревьях
поиска, и т. п. Наибольший эффект от хеширования — при поиске по
заданным идентификаторам или дескрипторам, что характерно для задач баз
данных, обработки документов и т. д. Для задач, в которых поиск ведется
сравнением или вычислением сложных логических функций, лучше
использовать традиционные методы сортировки и поиска.
Для того чтобы совершить плавный переход к рассмотрению следующей
структуры данных — спискам, вернемся еще раз к одной проблеме, связанной
с массивами. Упоминалось, что среди массивов можно выделить массивы
специального вида, которые называют разреженными. В этих массивах
большинство элементов равны нулю. Отводить место для хранения всех
элементов расточительно. Естественно, возникает желание сэкономить. Что
для этого можно предпринять?
Техника обработки массивов предполагает, что все элементы расположены в
соседних ячейках памяти. Для ряда приложений это недопустимое
ограничение.
Обобщенно можно сказать, что все перечисленные выше структуры имеют общие свойства:
- постоянство структуры данных на всем протяжении ее существования;
- память для хранения отводится сразу всем элементам структуры и все элементы находятся в смежных ячейках памяти;
- отношения между элементами просты настолько, что можно исключить потребность в средствах хранения информации об их отношениях в какой бы то ни было форме.
Исходя из этих свойств данные структуры данных и называют статическими. Снять подобные ограничения можно, используя другой тип данных — списки. Для них подобных ограничений не существует.