Базовые структуры данных. Деки, списки и хеш-таблицы, страница 4

Данный метод очень прост. В каждом элементе хеш-таблицы хранится не элемент, а список, содержащий все элементы (вместе с ключами), ключи которых имеют одинаковое хеш-значение. Тогда для поиска любого значения в среднем достаточно времени Θ(1 + α).

В этом случае при операциях вставки, удаления и поиска элемента необходимо учитывать, что придётся иметь дело со списками размером в среднем α.

3.4  Открытая адресация

При открытой адресации все данные хранятся исключительно в ячейках хеш-таблицы (в каждой ячейке записаны или элемент, или 0). Понятно, что при этом всегда n <= m, иначе места для всех элементов просто не найдётся. Как же находить хеш-значение?

Для этого мы будем использовать простой обманный манёвр. Пусть у нас есть хеш-функция от двух аргументов h(k, i), где i – номер попытки нахождения хеш-значения.

Таким образом, при вставке нового элемента в хеш-таблицу мы сначала просматриваем ячейку T[h(k, 0)]. Если её значение не равно 0, просматриваем ячейку T[h(k, 1)] и так далее до тех пор, пока не найдём пустую ячейку, куда и запишем новый элемент. Точно так же и с поиском.

При этом для поиска несуществующего элемента требуется время Θ(1 / (1 - α)), а для успешного поиска (существующего элемента) – Θ(1/α ln 1/(1-α)). Это, естественно, при использовании равномерного хеширования. Доказательство можно узнать хотя бы в труде Кормена, Лейзерсона и Ривеста.

Самая большая проблема открытой адресации – выбор хеш-функции, которая осуществляла бы равномерное хеширование. На практике подобное практически неосуществимо, но используются методы, позволяющие получить достаточно хорошие хеш-функции. Это линейная последовательность проб, квадратичная последовательность проб и двойная адресация.

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

3.4.1  Двойное хеширование

При таком хешировании хеш-функция имеет вид

h(k, i) = (h₁(k) + i h₂(k)) mod m

Тут h₁(k) и h₂(k) – обычные хеш-функции. Все гениальное, как вы уже знаете, просто.

Можно выбрать их так (пусть m – простое число):

h₁(k) = k mod m

h₂(k) = 1 + (k mod m’)

Тут m’ – число, на 1 или 2 меньшее, чем m.

4  Домашнее задание

1.  Реализуйте на C++ класс (шаблон или для определённого типа), инкапсулирующий двусвязный список. С использованием вашего класса списка реализуйте класс, инкапсулирующий дек. Унаследуйте от него классы стека и очереди (уберите функциональность у соответствующих методов). Пожалуйста, реализуйте, а не делайте оболочек для стандартных контейнеров STL.

2.  Объясните, как за время Θ(n) переставить элементы в односвязном списке в обратном порядке, используя O(1) памяти.

3.  Прочитайте главу о хеш-таблицах ещё раз.

4.  Найдите ненулевое значение коэффициента заполнения α, при котором при открытой адресации оценка среднего числа проб при поиске отсутствующего элемента вдвое превосходит оценку среднего числа проб при успешном поиске.

5  Список литературы

Т. Кормен, Ч. Лейзерсон, Р. Ривест [2001], Алгоритмы. Построение и анализ, МЦНМО, М., 194-235

Дональд Э. Кнут [2000], Искусство программирования, третье издание. Том 1: Основные алгоритмы, Вильямс, 277-475

Дональд Э. Кнут [2000], Искусство программирования, третье издание. Том 3: Сортировка и поиск, Вильямс, 549-598