Хэш-таблицы и хэш-функции Лекция 3

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

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

Таблицы с прямой адресацией Прямая адресация представляет собой простейшую технологию, которая хорошо работает для небольших множеств ключей. Предположим, что приложению требуется динамическое множество, каждый элемент которого имеет ключ из множества U = {0,1,..., m 1}, где m не слишком велико. Кроме того, предполагается, что никакие два элемента не имеют одинаковых ключей. Для представления динамического множества мы используем массив, или таблицу с прямой адресацией, который обозначим как Т [0..m 1], каждая позиция, или ячейка (position, slot), которого соответствует ключу из пространства ключей U. Ячейка к указывает на элемент множества с ключом к. Если множество не содержит элемента с ключом к, то Т [k] = NIL. 4

На рисунке каждый ключ из пространства U = {0,1,..., 9} соответствует индексу таблицы. Множество реальных ключей К = {2,3,5,8} определяет ячейки таблицы, которые содержат указатели на элементы. Остальные ячейки (закрашенные темным цветом) содержат значение NIL. 5

Реализация словарных операций тривиальна: D IRECT _A DDRESS _S EARCH (T, к) return T[k] Direct_Address_Insert(T, x) T[key[x]] x Direct_Address_Delete(T, x) T[key[x]] NIL Каждая из приведенных операций очень быстрая: время их работы равно 0(1). 6

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

Хеш-таблицы Недостаток прямой адресации очевиден: если пространство ключей U велико, хранение таблицы Т размером |U | непрактично, а то и вовсе невозможно в зависимости от количества доступной памяти и размера пространства ключей. Кроме того, множество К реально сохраненных ключей может быть мало по сравнению с пространством ключей U, а в этом случае память, выделенная для таблицы Т, в основном расходуется напрасно. Когда множество К хранящихся в словаре ключей гораздо меньше пространства возможных ключей U, хеш-таблица требует существенно меньше места, чем таблица с прямой адресацией. Точнее говоря, требования к памяти могут быть снижены до θ(|K | ), при этом время поиска элемента в хеш- таблице остается равным 0(1). Необходимо заметить, что это граница среднего времени поиска, в то время как в случае таблицы с прямой адресацией эта граница справедлива для наихудшего случая. 8

В случае прямой адресации элемент с ключом к хранится в ячейке к. При хешировании этот элемент хранится в ячейке h (к), т.е. мы используем хеш-функцию h для вычисления ячейки для данного ключа к. Функция h отображает пространство ключей U на ячейки хеш-таблицы Т [0..m 1]: h:U > {0,1,...,m 1}. Говорят, что элемент с ключом к хешируется в ячейку h (к); величина h (к) называется хеш-значением ключа к. Цель хеш-функции состоит в том, чтобы уменьшить рабочий диапазон индексов массива, и вместо |U | значений мы можем обойтись всего лишь m значениями. Соответственно снижаются и требования к количеству памяти. 9

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

Идеальным решением было бы полное устранение коллизий. Можно попытаться добиться этого путем выбора подходящей хеш-функции h. Одна из идей заключается в том, чтобы сделать h случайной, что позволило бы избежать коллизий или хотя бы минимизировать их количество (этот характер функции хеширования отображается в самом глаголе to hash, который означает мелко порубить, перемешать). Функция h должна быть детерминистической и для одного и того же значения к всегда давать одно и то же хеш-значение h(k). Однако поскольку |U| > m, должно существовать как минимум два ключа, которые имеют одинаковое хеш-значение. Таким образом, полностью избежать коллизий невозможно в принципе, и хорошая хеш-функция в состоянии только минимизировать количество коллизий. Таким образом, крайне необходим метод разрешения возникающих коллизий. 11

Разрешение коллизий при помощи цепочек При использовании данного метода мы объединяем все элементы, хешированные в одну и ту же ячейку, в связанный список. 12

Ячейка j содержит указатель на заголовок списка всех элементов, хеш-значение ключа которых равно j. Если таких элементов нет, ячейка содержит значение NIL. На рис. показано разрешение коллизий, возникающих из-за того, что h(k 1 ) = h (k 4 ), h (k 5 ) = h (k 2 ) = h (k 7 ) и h(k 8 ) = h(k 6 ). 13

Словарные операции в хеш-таблице с использованием цепочек для разрешения коллизий реализуются очень просто: Chained_Hash_Insert(T, х) Вставить х в заголовок списка T[h(key[x])] C HAINED _H ASH _S EARCH (T, к) Поиск элемента с ключом к в списке T[h(k)] Chained_Hash_Delete(T, х) Удаление х из списка T[h(key[x])] Время, необходимое для вставки в наихудшем случае, равно 0(1). Процедура вставки выполняется очень быстро, поскольку предполагается, что вставляемый элемент отсутствует в таблице. 14

Анализ хеширования с цепочками Насколько высока производительность хеширования с цепочками? В частности, сколько времени требуется для поиска элемента с данным ключом? Пусть у нас есть хеш-таблица Т с m ячейками, в которых хранятся n элементов. Определим коэффициент заполнения таблицы Т как а = n/m, т.е. как среднее количество элементов, хранящихся в одной цепочке. Наш анализ будет опираться на значение величины а, которая может быть меньше, равна или больше единицы. В наихудшем случае хеширование с цепочками ведет себя крайне неприятно: все n ключей хешированны в одну и ту же ячейку, создавая список длиной n. Таким образом, время поиска в наихудшем случае равно θ (n) плюс время вычисления хеш-функции, что ничуть не лучше, чем в случае использования связанного списка для хранения всех n элементов. Понятно, что использование хеш- таблиц в наихудшем случае совершенно бессмысленно. (Идеальное хеширование (применимое в случае статического множества ключей) обеспечивает высокую производительность даже в наихудшем случае.) 15

Средняя производительность хеширования зависит от того, насколько хорошо хеш-функция h распределяет множество сохраняемых ключей по т ячейкам в среднем. В хеш-таблице с разрешением коллизий методом цепочек математическое ожидание времени неудачного поиска в предположении простого равно­мерного хеширования равно θ (1 + a). В хеш-таблице с разрешением коллизий методом цепочек матема­тическое ожидание времени успешного поиска в предположении простого равномерного хеширования в среднем равно θ (1 + a). Что же означает проведенный анализ? Если количество ячеек в хеш-таблице, как минимум, пропорционально количеству элементов, хранящихся в ней, то n = О (т) и, следовательно, а = n/т = О (т)/т = О (1), а значит, поиск элемента в хеш-таблице в среднем требует постоянного времени. Поскольку в худшем случае вставка элемента в хеш-таблицу занимает 0(1) времени (как и удаление элемента при использовании двусвязных списков), можно сделать вывод, что все словарные операции в хеш-таблице в среднем выполняются за время 0(1). 16

Хеш-функции Качественная хеш-функция удовлетворяет (приближенно) предположению простого равномерного хеширования: для каждого ключа равновероятно помещение в любую из т ячеек, независимо от хеширования остальных ключей. К сожалению, это условие обычно невозможно проверить, поскольку, как правило, распределение вероятностей, в соответствии с которым поступают вносимые в таблицу ключи, неизвестно; кроме того, вставляемые ключи могут не быть независимыми. Иногда распределение вероятностей оказывается известным. Например, если известно, что ключи представляют собой случайные действительные числа, рав­номерно распределенные в диапазоне 0 к < 1, то хеш-функция h (к) = [кт] удовлетворяет условию простого равномерного хеширования. 17

Интерпретация ключей как целых неотрицательных чисел Для большинства хеш-функций пространство ключей представляется множеством целых неотрицательных чисел N = {0,1,2,...}. Если же ключи не являются целыми неотрицательными числами, то можно найти способ их интерпретации как таковых. Например, строка символов может рассматриваться как целое число, записанное в соответствующей системе счисления. Так, идентификатор pt можно рассматривать как пару десятичных чисел (112,116), поскольку в ASCII-наборе символов p=112 и t = 116. Рассматривая pt как число в системе счисления с основанием 128, мы находим, что оно соответствует значению = В конкретных приложениях обычно не представляет особого труда разработать метод для представления ключей в виде (возможно, больших) целых чисел. Далее при изложении материала мы будем считать, что все ключи представляют целые неотрицательные числа. 18

Метод деления Построение хеш-функции методом деления состоит в отображении ключа к в одну из ячеек путем получения остатка от деления к на m, т.е. хеш-функция имеет вид h(k) = к mod т. Например, если хеш-таблица имеет размер т = 12, а значение ключа к = 100, то h (к) = 4. Поскольку для вычисления хеш- функции требуется только одна операция деления, хеширование методом деления считается достаточно быстрым. При использовании данного метода мы обычно стараемся избегать некоторых значений т. Например, т не должно быть степенью 2, поскольку если m = 2 Р, то h (к) представляет собой просто р младших битов числа к. Если только заранее не известно, что все наборы младших р битов ключей равновероятны, лучше строить хеш-функцию таким образом, чтобы ее результат зависел от всех битов ключа. 19

Зачастую хорошие результаты можно получить, выбирая в качестве значения т простое число, достаточно далекое от степени двойки. Предположим, например, что мы хотим создать хеш-таблицу с разрешением коллизий методом цепочек для хранения n = 2000 символьных строк, размер символов в которых равен 8 битам. Нас устраивает проверка в среднем трех элементов при неудачном поиске, так что мы выбираем размер таблицы равным т = 701. Число 701 выбрано как простое число, близкое к величине 2000/3 и не являющееся степенью 2. Рассматривая каждый ключ к как целое число, мы получаем искомую хеш-функцию: h(k) = к mod

Метод умножения Построение хеш-функции методом умножения выполняется в два этапа. Сначала мы умножаем ключ к на константу 0 < А < 1 и получаем дробную часть полученного произведения. Затем мы умножаем полученное значение на m и применяем к нему функцию floor т.е. h (к) = [т (кА mod 1)], где выражение кА mod 1 означает получение дробной части произведения кА, т.е. величину к А [к А]. Достоинство метода умножения заключается в том, что значение т перестает быть критичным. Обычно величина т из соображений удобства реализации функции выбирается равной степени 2. Пусть у нас имеется компьютер с размером слова w битов и к помещается в одно слово. 21

Ограничим возможные значения константы А видом s/2 w, где s целое число из диапазона 0 < s < 2 w. Тогда мы сначала умножаем к на w-битовое целое число s = А 2 w Результат представляет собой 2w-битовое число r 1 2 w +r о, где r 1 старшее слово произведения, а r 0 младшее. Старшие р битов числа r о представляют собой искомое p- битовое хеш- значение. 22

Хотя описанный метод работает с любыми значениями константы А, некоторые значения дают лучшие результаты по сравнению с другими. Оптимальный выбор зависит от характеристик хешируемых данных. Кнут предложил использовать дающее неплохие результаты значение А (sqrt(5)- 1)/ Возьмем в качестве примера к = , р = 14, т = 2 14 = и w = 32. Принимая предложение Кнута, выбираем значение А в виде s/2 w, ближайшее к величине (sqrt(5) 1)/2, так что А = /2 32. Тогда к * s = = ( ) , и, соответственно, r 1 = и r 0 = Старшие 14 битов числа r 0 дают нам хеш-значение h (к) =

Универсальное хеширование Если недоброжелатель будет умышленно выбирать ключи для хеширования при помощи конкретной хеш-функции, то он сможет подобрать n значений, которые будут хешироваться в одну и ту же ячейку таблицы, приводя к среднему времени выборки 0(n). Таким образом, любая фиксированная хеш- функция становится уязвимой, и единственный эффективный выход из ситуации случайный выбор хеш-функции, не зависящий от того, с какими именно ключами ей предстоит работать. Такой подход, который называется универсальным хешированием, гарантирует хорошую производительность в среднем, независимо от того, какие данные будут выбраны злоумышленником. Главная идея универсального хеширования состоит в случайном выборе хеш- функции из некоторого тщательно отобранного класса функций в начале работы программы. 24

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