Выбор способа перевода ключевых слов в числовую форму
Квадратичное рехэширование
Процедура квадратичного рехэширования предполагает, что процесс поиска резервных ячеек производится с использованием некоторой квадратичной функции, например такой:
Pi = а,2+b,+с. (2.6)
Хотя значения а, b, с можно задавать любыми, велика вероятность быстрого зацикливания значений рi. Поэтому в качестве рекомендации опишем один из вариантов реализации процедуры квадратичного рехэширования, позволяющий осуществить перебор всех элементов хэш-таблицы [32]. Для этого значения в формуле (2.6) положим равными: а=1, b = с = 0. Размер таблицы желательно задавать равным простому числу, которое определяется формулой М = 4n+3, где n – целое число. Для вычисления значений рi используют одно из соотношений:
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), – вторую половину. Практически реализовать данный метод можно следующей процедурой.
- Задание I = -М.
- Вычисление хэш-адреса К одним из методов хэширования.
- Если ячейка свободна или ключ элемента в ней совпадает с искомым ключом, то завершение процесса поиска. Иначе, 1: = 1+1.
- Вычисление h: = (h+|i|)modM.
- Если I < М, то переход к шагу 3. Иначе (если I > М), таблица полностью заполнена.
Программа та же, что приведена в методе линейного рехэширования, за исключением добавления одной команды для инициализации процесса рехэширования, самого фрагмента рехэширования и небольших изменений сегмента данных. могут являться методы, основанные на деревьях поиска, и т. п. Наибольший эффект от хеширования – при поиске по заданным идентификаторам или дескрипторам, что характерно для задач баз данных, обработки документов и т. д. Для задач, в которых поиск ведется сравнением или вычислением сложных логических функций, лучше использовать традиционные методы сортировки и поиска.
Для того чтобы совершить плавный переход к рассмотрению следующей структуры данных – спискам, вернемся еще раз к одной проблеме, связанной с массивами. Упоминалось, что среди массивов можно выделить массивы специального вида, которые называют разреженными. В этих массивах большинство элементов равны нулю. Отводить место для хранения всех элементов расточительно. Естественно, возникает желание сэкономить. Что для этого можно предпринять?
Техника обработки массивов предполагает, что все элементы расположены в соседних ячейках памяти. Для ряда приложений это недопустимое ограничение.
Обобщенно можно сказать, что все перечисленные выше структуры имеют общие свойства:
- постоянство структуры данных на всем протяжении ее существования;
- память для хранения отводится сразу всем элементам структуры и все элементы находятся в смежных ячейках памяти;
- отношения между элементами просты настолько, что можно исключить потребность в средствах хранения информации об их отношениях в какой бы то ни было форме.
Исходя из этих свойств данные структуры данных и называют статическими. Снять подобные ограничения можно, используя другой тип данных – списки. Для них подобных ограничений не существует.