Сборник по задачам и примерам Assembler


Поиск в таблице - часть 16


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

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

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

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

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

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

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

 




Начало  Назад  Вперед



Книжный магазин