Иллюстрированный самоучитель по задачам и примерам Assembler

Выбор способа перевода ключевых слов в числовую форму

Квадратичное рехэширование

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

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), – вторую половину. Практически реализовать данный метод можно следующей процедурой.

  1. Задание I = -М.
  2. Вычисление хэш-адреса К одним из методов хэширования.
  3. Если ячейка свободна или ключ элемента в ней совпадает с искомым ключом, то завершение процесса поиска. Иначе, 1: = 1+1.
  4. Вычисление h: = (h+|i|)modM.
  5. Если I < М, то переход к шагу 3. Иначе (если I > М), таблица полностью заполнена.

Программа та же, что приведена в методе линейного рехэширования, за исключением добавления одной команды для инициализации процесса рехэширования, самого фрагмента рехэширования и небольших изменений сегмента данных. могут являться методы, основанные на деревьях поиска, и т. п. Наибольший эффект от хеширования – при поиске по заданным идентификаторам или дескрипторам, что характерно для задач баз данных, обработки документов и т. д. Для задач, в которых поиск ведется сравнением или вычислением сложных логических функций, лучше использовать традиционные методы сортировки и поиска.

Для того чтобы совершить плавный переход к рассмотрению следующей структуры данных – спискам, вернемся еще раз к одной проблеме, связанной с массивами. Упоминалось, что среди массивов можно выделить массивы специального вида, которые называют разреженными. В этих массивах большинство элементов равны нулю. Отводить место для хранения всех элементов расточительно. Естественно, возникает желание сэкономить. Что для этого можно предпринять?

Техника обработки массивов предполагает, что все элементы расположены в соседних ячейках памяти. Для ряда приложений это недопустимое ограничение.

Обобщенно можно сказать, что все перечисленные выше структуры имеют общие свойства:

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

Исходя из этих свойств данные структуры данных и называют статическими. Снять подобные ограничения можно, используя другой тип данных – списки. Для них подобных ограничений не существует.

Если Вы заметили ошибку, выделите, пожалуйста, необходимый текст и нажмите CTRL + Enter, чтобы сообщить об этом редактору.