Часто приходится адресовать элементы множества по ключу, который является целым, изменяющимся в большом диапазоне (прочие ключи – строки, вещественные числа – можно отобразить на множество целых чисел), в то время как общее количество элементов сравнительно мало. В таком случае совершенно нецелесообразно выделять массив размера, необходимого для прямой адресации. Лучше выделить массив некоторого относительно малого размера, а множество ключей отображать на множество возможных индексов используемого массива (он же хеш-таблица). При этом, как будет показано, время поиска в хеш-таблице в среднем случае равно O(1), что совсем неплохо.
3.1 Основные понятия
Пусть хеш-таблица T имеет размер m и индексируется с нуля, а общее количество хешируемых элементов – n. Тогда для осуществления хеширования нам необходима некая функция h(k), которая отображает всё множество наших ключей на множество {0, ..., m-1}. Назовём эту функцию хеш-функцией, а её значение для ключа k – хеш-значением для ключа k. Хеш-значения должны быть равномерно распределены на множестве {0, ..., m-1} (для оптимальной работы), поэтому подбор хеш-функции осуществляется согласно этому критерию.
Основные операции, выполняемые над хеш-таблицей:
§ insert(T, x) – вставляет элемент x в хеш-таблицу T. Выполняется всегда за время Θ(1).
§ delete(T, l) – удаляет элемент, на который указывает l, из хеш-таблицы T. Выполняется всегда за время Θ(1).
§ find(T, k) – возвращает указатель на элемент с ключом k или 0, если такого элемента нет в хеш-таблице T. В среднем случае работает за время O(1).
При работе с хеш-таблицами возникает огромная проблема. Поскольку размер таблицы меньше размера множества возможных ключей, может возникать такая ситуация, когда два ключа имеют одно и то же хеш-значение (коллизия). Подобные неприятности устраняются использованием цепочек или открытой адресации. Оба эти метода будут рассмотрены ниже.
При анализе алгоритмов хеширования используется коэффициент заполнения α. Он равен α = n / m.
3.2 Подбор хеш-функции
На роль хеш-функции подойдёт не каждая первая попавшаяся функция. Основное требование к любой хеш-функции – для каждого значения ключа все m хеш-значений равновероятны. Ниже будут рассмотрены две такие функции, которые используются достаточно часто, и метод универсального хеширования.
Будем считать, что ключи – неотрицательные целые числа.
3.2.1 Деление с остатком
Хеш-функция равна остатку от деления ключа на размер хеш-таблицы m.
h(k) = k mod m
При этом для такой хеш-функции подойдёт далеко не каждое значение m. Например, если m = 2p (p – положительное целое), то kmod 2p есть ни что иное, как маска младших p бит ключа k. Обычно m выбирают простым и не во много раз меньшим, чем вероятное значение n.
3.2.2 Умножение
Для этой хеш-функции
h(k) = floor(m (kA mod 1))
Для умножения значение m не имеет никакого значения. А вот от выбора константы A (0 < A < 1) зависит многое. Небезызвестный товарищ Дональд Эрвин Кнут показал, что для неё хорошо подходит значение A = (sqrt(5) - 1) / 2.
3.2.3 Универсальное хеширование
Никто не может гарантировать, что на разных наборах данных одна и та же хеш-функция будет вести себя одинаково хорошо. Поэтому целесообразно непосредственно перед началом построения хеш-таблицы случайным образом выбрать хеш-функцию из множества предопределённых (или создать её динамически), что сведёт риск ошибки к минимуму.
3.3 Цепочки как решение проблемы коллизий
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.