Алгоритм поиска, поиск хешированием

Введение

Предположим, что есть набор, состоящий из n компонентов $а_1, а_2, а_3, . . ., а_n$, каждый из которых имеет некоторый ключ. Необходимо данный набор представить в форме определённой информационной структуры с обеспечением возможности многократных поисковых операций компонентов с определённым ключом. Такую задачу можно решить разными способами:

1. Когда набор компонентов не подвергался упорядочению, то поиск может быть выполнен путём прямого сравнения каждого компонента массива или списка. При этом трудоёмкость операции будет O(n).
2. Когда компоненты прошли процесс упорядочения в массиве или дереве поиска, то более эффективным будет поиск в двоичном формате при трудоёмкости О(log 2 n).

Но, если выполнить ещё некоторые дополнительные условия, то можно осуществить организацию исходного набора ключей в формате специальной структурной организации данных, которые называются хеш-таблицей. Поиск любого компонента в этой таблице в идеальном случае производится за единственное сравнение и на него не влияет размерность исходного набора. То есть, трудоёмкость этого способа поиска, именуемого хеш- поиском, будет пропорциональна О(1), что является великолепным результатом.

Поиск хешированием

Способ хеш-поиска состоит в следующем. Начальные компоненты $а_1, а_2, а_3, . . ., а_n$ располагаются особым образом в ячейках массива. Предполагаем, что количество ячеек в массиве $m > n$. Оптимальным случаем поисковой операции считается такая операция, когда при поступлении на вход какого-либо ключа можно сразу определить индекс ячейки, обладающей этим ключом, без анализа других ячеек. Чтобы вычислить индекс ячейки по ключу на входе, применяется специальная функция, именуемая хеш-функцией. По этой функции можно поставить в соответствие всем ключам индексы ячеек массива, где расположен компонент, имеющий этот ключ:

h (аi ) = j, j = (1, m);

Массив, который наполнен компонентами начального набора в очерёдности, определяемой хеш-функцией, является хеш-таблицей. Следовательно, разрешение поисковой задачи этим способом имеет существенную зависимость от применяемой хеш-функции. Известно достаточно много разных хеш-функций. Наиболее простой, но не наилучшей хеш-функцией считается функция, являющаяся остатком от деления ключа на m:

h (аi ) = (аi mod m) + 1;

Естественно, все значения данной функции расположены в диапазоне от единицы до m и могут считаться индексами ячеек массива. Предполагается, что оптимальной считается хеш-функция, удовлетворяющая таким условиям:

1. Выражение функции должно быть не сложным с точки зрения необходимых вычислений.
2. Ключи, распределённые хеш-функцией, должны быть расположены в хеш-таблице по возможности в равномерном порядке.

Применение этой методики состоит из двух этапов:

1. Формирование хеш-таблицы для определённого ключевого набора при помощи заданной хеш-функции, то есть задание каждому ключу своего места в таблице.
2. Применение сформированной таблицы с целью поиска компонентов при помощи выбранной хеш-функции.

Приведём конкретные примеры. Имеется набор из восьми ключей, заданных целыми числами:

35, 19, 07, 14, 26, 40, 51,72.

Необходимо выполнить распределение этих ключей в массиве из десяти ячеек при посредстве самой простой хеш-функции. То есть надо разделить все ключи нацело на десять и применить остатки как индексы расположения ключей в массиве:

35 mod 10 = 5, индекс местоположения ключа 35 равняется шести

19 mod 10 = 9, индекс местоположения ключа 19 равняется десяти

07 mod 10 = 7, индекс местоположения ключа 07 равняется восьми

14 mod 10 = 4, индекс местоположения ключа 14 равняется пяти

26 mod 10 = 6, индекс размещения ключа 26 равняется семи

40 mod 10 = 0, индекс местоположения ключа 40 равняется единице

51 mod 10 = 1, индекс местоположения ключа 51 равняется двум

72 mod 10 = 2, индекс местоположения ключа 72 равняется трём

В итоге будет получена следующая хеш-таблица:

Рисунок 1. Хеш-таблица. Автор24 — интернет-биржа студенческих работ

Если необходимо выполнить поиск в данной хеш-таблице ключ, имеющий значение 26, то надо разделить двадцать шесть на десять, затем взять остаток, который равен шести и войти в ячейку, имеющую индекс равный семи. Далее можно сравнить записанное в ячейку значение с задаваемым ключом.

Рассмотрим ещё один пример. Предположим, что ключи имеют строковый формат. Следовательно, сначала необходимо выполнить преобразование ключа в текстовом формате в цифровой формат. К примеру, можно выполнить сложение ASCII-кодов всех символьных знаков, которые входят в данный ключ. Предположим, что строковым ключом является слово END, тогда его эквивалентное числовое отображение будет равно сумме кодов этих трёх букв:

ord(E) + ord(N) + ord(D) = 69 + 78 + 68 = 215

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

h (END) = (215 mod 10) + 1 = 6

h (VAR) = (233 mod 10) + 1 = 4

h (AND) = (211 mod 10) + 1 = 2

h (NIL) = (227 mod 10) + 1 = 8

В итоге для данных строковых ключей сформирована следующая хеш-таблица:

Рисунок 2. Хеш-таблица. Автор24 — интернет-биржа студенческих работ

Выполнить поисковую операцию в данной таблице совсем не сложно. Нужно найти целочисленный аналог строкового ключа, затем вычислить величину хеш-функции и сравнить содержимое найденной ячейки с исходным ключом. К примеру, h (VAR) = 4, выполняем сравнение содержимого ячейки четыре с ключом VAR, отмечаем наличие совпадения. Поиск завершён.