Поиск путем сравнения ключей

В данном разделе обсуждаются методы поиска, основанные на линейном упорядочении ключей. После сравнения данного аргумента К с ключом K_i из таблицы поиск продолжается одним из трех путей, в зависимости от того, какое из условий К < K_i, К = K_i или К > К_i будет выполняться. Последовательные методы поиска, рассмотренные ранее, по сути, имели только два варианта ветвления поиска - в зависимости от выполнения или не выполнения условия К = К_i.

Поиск в упорядоченной таблице

Бинарный поиск

 

Пожалуй, самым простым способом поиска ключа в упорядоченном массиве является следующий: сравнить К со средним ключом в таблице, в результате этого сравнения определить, в какой половине таблицы находится искомый ключ, и снова применить ту же процедуру к половине таблицы. Таким образом, максимум за величину порядка log₂N сравнений искомый ключ будет либо найден, либо будет установлено, что его нет в таблице. Эта процедура известна как "логарифмический поиск" или "метод деления пополам" но чаще всего употребляется термин бинарный поиск.

Поиск Фибоначчи

 

Данный алгоритм поиска представляет собой альтернативу бинарному поиску. Для некоторых компьютеров предлагаемый метод предпочтителен в связи с тем, что в нем используются только сложение и вычитание, в отличие от бинарного поиска, где применяется деление. На рис. 29 показано дерево поиска Фибоначчи порядка 6.

 

 

 

 

Рис. 29. Дерево Фибоначчи порядка 6

 

Последовательность чисел Фибоначчи F_k описывается следующей зависимостью:

 

F₀=0, F₁=1, F_k+2= F_k+1+ F_k, k=0,1,…

 

В целом, дерево Фибоначчи порядка k имеет F_k+1-1 внутренних и F_k+1 внешних узлов. Оно строится по следующим правилам:

 

· Если k = 0 или k = 1, то дерево вырождается в [0].

· Если k ³ 2, корнем является F_k; левое поддерево представляет собой дерево Фибоначчи порядка k - 1; а правое поддерево представляет собой дерево Фибоначчи порядка k - 2 с числами, увеличенными на F_k.

 

Комбинируя эти наблюдения с механизмом распознавания внешних узлов, получается алгоритм поиска Фибоначчи.

3.3 Хеширование [21]

 

Рассмотренные ранее методы поиска основывались на сравнении данного аргумента К с ключами в таблице. При хешировании данную операцию заменяют арифметическими действиями над ключом К, позволяющими вычислить некоторую функцию f(K). Последняя укажет адрес в таблице, где хранится К и связанная с ним информация.

Идея хеширования состоит в использовании некоторой частичной информации, полученной из ключа, в качестве основы поиска. С помощью ключа происходит вычисление хеш-адреса h(K) и он используется в дальнейшем для проведения поиска. Вполне возможна ситуация, когда найдутся различные ключи K_i и K_j, имеющие одинаковое значение хеш-функции h(K_i) = h(K_j). Такое событие именуется коллизией (collision); для разрешения коллизий разработаны различные способы. При использовании хеширования необходимо решить две практически независимые задачи - выбрать хеш-функцию h(K) и способ разрешения коллизий.

 

Хеш-функции

 

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

 

О £ h(K) < М.

 

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

 

Метод деления весьма прост. В качестве хеш-функции берется остаток от деления ключа К на М:

 

h(K) = К mod M

 

Как показала практика, лучше всего в качестве М использовать простые числа.

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

 

Одна из положительных сторон мультипликативной схемы заключается в отсутствии потери информации, т.е. в возможности восстановить значение ключа К по значению функции h(K). Дело в том, что А и w взаимно просты и при помощи алгоритма Евклида можно найти константу А’, такую, что

A A' mod w = 1; отсюда следует, что К = (А'(АK mod w)) mod w.

 

Хорошие результаты для хеш-функций получаются в случае, когда A/w приближенно равно золотому сечению . В этом случае последовательность значений h(k), h(k+1), h(k+2) ведет себя точно также как последовательность h(0), h(1), h(2).