Поиск с использованием хеш-функций

Основные понятия

Пусть имеется набор из n элементов, а ₁, а ₂, а ₃,…, а_n с некоторыми ключами (как и раньше, для простоты будем считать, что сам элемент совпадает с его ключом). Требуется этот набор организовать в виде некоторой структуры данных с возможностью многократного поиска в нем элементов с заданным ключом. Эта задача может решаться различными способами:

• · если набор элементов никак не упорядочен, то поиск выполняется прямым сравнением всех элементов в массиве или списке с трудоемкостью O (n)
• · если элементы упорядочены в массиве или в дереве поиска, поиск более эффективно выполняется как двоичный, с трудоемкостью О (log ₂ n)

Возникает вопрос: существуют ли еще более эффективные методы поиска? Оказывается, при выполнении некоторых дополнительных условий можно организовать исходный набор ключей в виде специальной структуры данных, называемой хеш-таблицей, поиск в которой ЛЮБОГО элемента в идеале выполняется за ОДНО сравнение и НЕ зависит от размерности входного набора. Другими словами, трудоемкость такого метода поиска, называемого хеш-поиском, пропорциональна О (1), что является абсолютным рекордом!

Метод хеш-поиска заключается в следующем. Исходные элементы, а ₁, а ₂, а ₃,…, а_n распределяются некоторым специальным образом по ячейкам массива. Пока будем считать, что число ячеек массива m > n. Идеальным поиском можно считать такой, когда по любому входному ключу сразу вычисляется индекс ячейки с этим ключом, без проверки содержимого остальных ячеек. Для вычисления индекса ячейки по входному ключу используется специальная функция, называемая хеш-функцией. Эта функция ставит в соответствие каждому ключу индекс ячейки массива, где должен располагаться элемент с этим ключом:

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

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

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

Ясно, что каждое значение этой функции лежит в пределах от 1 до m и может приниматься в качестве индекса ячейки массива.

Принято считать, что хорошей является хеш-функция, которая удовлетворяет следующим условиям:

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

Использование данного метода включает два этапа:

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

Рассмотрим два примера с целыми и строковыми ключами.

Пример 1. Пусть задан набор из 8 целочисленных ключей:

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

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

Для этого каждый ключ делим нацело на 10 и используем остаток в качестве индекса размещения ключа в массиве:

• 35 mod 10 = 5, индекс размещения ключа 35 равен 6
• 19 mod 10 = 9, индекс размещения ключа 19 равен 10
• 07 mod 10 = 7, индекс размещения ключа 07 равен 8
• 14 mod 10 = 4, индекс размещения ключа 14 равен 5
• 26 mod 10 = 6, индекс размещения ключа 26 равен 7
• 40 mod 10 = 0, индекс размещения ключа 40 равен 1
• 51 mod 10 = 1, индекс размещения ключа 51 равен 2
• 72 mod 10 = 2, индекс размещения ключа 72 равен 3

Получаем следующую хеш-таблицу:

Если требуется найти в этой хеш-таблице ключ со значением 26, то этот поиск выполняется ровно за одно сравнение: делим 26 на 10, берем остаток 6, входим в ячейку с индексом 7 и сравниваем находящееся там значение с заданным ключом.

Пример 2. Пусть ключи являются строковыми. В этом случае предварительно текстовый ключ надо преобразовать в числовой. Например, можно сложить 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.

В результате для этих четырех строковых ключей получаем следующую хеш-таблицу:

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

Приведенные выше примеры носят несколько искусственный характер, поскольку они описывают идеальный случай, когда хеш-функция для всех различных ключей дает РАЗЛИЧНЫЕ значения индексов в массиве. В этом случае каждый ключ имеет свое уникальное расположение в массиве, не конфликтуя с другими ключами. Подобная ситуация возможна, если исходный набор ключей известен заранее и после построения хеш-таблицы не изменяется, т. е. ключи НЕ добавляются и НЕ удаляются из хеш-таблицы. В этом случае за счет подбора хеш-функции и, возможно, небольшого изменения самих ключей можно построить бесконфликтную хеш-таблицу. Важным практическим примером такой ситуации является построение таблицы ключевых слов в программах-трансляторах с языков программирования. Здесь набор ключевых слов является постоянным, изменяясь только при изменении версии транслятора, а с другой стороны, обработка транслятором входного текста на языке программирования требует многократного и очень быстрого распознавания в этом тексте ключевых слов языка.

К сожалению, идеальный случай возможен весьма редко, и ограничивать применение хеш-поиска только данным случаем было бы неразумно, учитывая выдающиеся потенциальные скоростные возможности метода. Поэтому были предложены различные усовершенствования хеш-поиска, существенно расширившие область его использования. Эти усовершенствования так или иначе связаны с обработкой конфликтных ситуаций, когда два РАЗНЫХ ключа претендуют на ОДНО и то же место в хеш-таблице, т. е. хеш-функция дает для этих разных ключей а_i и а_к одно и то же значение: h (а_i) = h (а_к) = j.

Например, в приведенном выше примере со строковыми ключами простая перестановка символов в ключе приводит к конфликту:

h (VAR) = h (RAV) = h (AVR) = (233 mod 10) + 1 = 4.

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