Приложение. Хеш-таблицы

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

Если метки элементов представляют собой числа в диапазоне от 0 до (М–1), то простейшее решение состоит в использовании таблицы размером М- Элемент с меткойiвставляется в таблицу в позицииi. При условии, что размер всех элементов одинаков, поиск в таблице тривиален и сводится к индексированию таблицы на основе числового значения метки элемента. Кроме того, хранить метку элемента в таблице не обязательно, поскольку она однозначно определяет­ся положением элемента. Такая таблица называется таблицей прямого доступа (directaccesstable).

Если метки не являются числами, использование подхода, основанного на прямом доступе, все равно остается возможным. Обозначим элементы А[1], ...,A[N].Каждый элемент A[t] состоит из метки, или ключа; и значения. Опре­делим функцию отображенияI(k), дающую для всех ключей значения от 1 доМ,такую, чтодля любых.В этом случае можно использовать таблицу прямого доступа длиной М.

Единственная трудность в применении данной схемы возникает, когда М гораздо больше, чем N. В этом случае в таблице оказывается слишком много не­использованных элементов, что приводит к неэффективному использованию па­мяти. Альтернативой является использование таблицы длиной N и хранение в ней Nэлементов (как значений, так и меток). В таком случае количество используемой памяти минимально, однако теперь трудной задачей становится поиск нужного элемента в таблице. Применимы различные алгоритмы поиска.

• Последовательный поиск.Подход "в лоб", требующий много времени при работе с большими таблицами.

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

• Бинарный поиск.Если метки (или их числовые отображения) расположены в таблице в возрастающем (убывающем) порядке, бинарный поиск значи­тельно быстрее последовательного (табл. 8.7) и не требует специального ап­паратного обеспечения.

Таблица 8.7. Средняя продолжительность поиска одного из Nэлементов в таблице размером М

Алгоритм	Продолжительность поиска
Прямой доступ	1
Последовательный поиск
Бинарный поиск	log2M
Линейное хеширование	2-
	2-
Хеширование (переполнение с цепочками)

Многообещающе для поиска в таблице выглядит бинарный поиск. Основным его недостатком является то, что добавление нового элемента в таблицу — процесс обычно непростой и требует переупорядочения записей таблицы. Таким образом, бинарный поиск обычно используется для более или менее статичных таблиц, которые достаточно редко изменяются.

Конечно, хотелось бы избежать как перерасхода памяти при прямом доступе, так и излишней работы процессора при остальных перечисленных подходах. Наиболее часто используемым компромиссным методом является хеширование. Этот метод, разработанный еще в 50-х годах, прост в реализации и имеет два достоинства. Во-первых, он позволяет найти большинство элементов за одно обращение к таблице, как при прямом доступе, а во-вторых, добавления элементов в таблицу и удаления элементов из нее выполняются без излишней сложности. Хеширование можно определить следующим образом. Предположим, что доNэлементов хранятся в таблице размеромМ > N ,причем М не намного большеN.Вставка элемента в таблицу осуществляется следующим образом.

I1. Преобразуем метку элемента в почти случайное числопмежду 0 иМ-1. Например, если метки представляют собой числовые значения, довольно распространенным методом является деление метки по модулю М.

I2. Используем полученное значение п в качестве индекса в хеш-таблице.

а. Если соответствующая запись в таблице пуста, значит, элемент ранее не был сохранен в таблице.

б. Если запись уже занята и ее метка соответствует искомой, значит, найден требуемый элемент.

в. Если запись занята и ее метка не соответствует заданной, продолжаем поиск в области переполнения.

Различные схемы хеширования отличаются способом обработки переполнения. Одна из широко распространенных технологий, обычно использующаяся в компиляторах, — технология линейного хеширования.В этом случае правило 12.бвыглядит следующим образом.

12.б.Если запись занята, установитьn=(n+1)modMи вернуться к шагу12.а.

Соответствующим образом изменяется и правило 12.в.

На рис. 8.24,априведен пример использования линейного хеширования. В данном случае метки элементов хранятся в виде чисел, а размер хеш-таблицы равен 8(М =8). Функция отображения представляет собой остаток при делении на 8. Предполагается, что элементы вставляются в таблицу в возрастающем порядке (хотя это условие и не является необходимым). Таким образом, элементы 50 и 51 отображаются на позиции 2 и 3, соответственно, и поскольку соответствующие записи пусты, элементы оказываются вставленными в положения 50 и 51. Элемент 74 также отображается в позицию 2, но так как она занята, мы пробуем вставить элемент в позицию 3. Поскольку она тоже занята, элемент 74 вставляется в таблицу в позиции 4.

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

Средняя продолжительность поиска , где.

Обратите внимание, что полученный результат не зависит от размера таблицы, а зависит только от степени ее заполненности. Приятной неожиданностью оказывается то, что даже при заполненности таблицы на 80% средняя продол­жительность поиска оказывается равной 3.

Однако даже такое значение продолжительности поиска можно рассматри­вать в ряде задач как слишком большое, да и процесс удаления элемента из таб­лицы при линейном хешировании достаточно сложен. Более привлекателен под­ход, обеспечивающий меньшую продолжительность поиска (см. табл. 8.7) и бо­лее простое удаление элементов — переполнение с цепочками, показанное на рис. 8.24,б.В этом случае имеется отдельная таблица, в которой размещаются элементы, вызывающие переполнение. Записи этой таблицы включают указате­ли, связывающие элементы с одинаковым хеш-значением в цепочки при случайно распределенных данных.

Средняя продолжительность поиска == 1 +.

Для больших значений N = М средняя продолжительность поиска стремит­ся к 1.5. Таким образом, этот метод обеспечивает быстрый поиск при компакт­ном хранении.