Лекция 13. Хеш-таблицы (Электронные лекции)

Лекции по курсу “Алгоритмы и алгоритмические языки”, 1 курс, 1 поток, 2010/2011 уч.годЛекция 13 Хеш-таблицы13.1. Словарные операции: добавление, поиск и удаление элементов по их ключам. Организуетсятаблица ключей: массив Index[m] длины m, элементы которого содержат значение ключа иуказатель на данные (информацию), соответствующие этому ключу.13.1.1. Прямая адресация. Применяется, когда количество возможных ключей невелико:например, ключи перенумерованы целыми числами из множества U = {0, 1, 2, …, m– 1}, где m не очень большое целое число.

В случае прямой адресации ключ сномером k соответствует элементу Index[k]. Нередко в качестве ключаиспользуется индекс (номер элемента) массива Index, а значениями элементовмассива Index являются указатели на соответствующие данные, либо нулевойуказатель null.Для реализации прямой адресации необходимо запрограммировать три словарныеоперации: поиск (Search(key)), добавление данных (Insert(key, value)) и исключениеданных (Delete(key, value)).

Ясно, что выполнение каждой из трех словарныхопераций требует время порядка O(1) (т.е. какое-то фиксированное время):Search(key) – это обращение к элементу Index[key], Insert(key, value) сводится коперации присваивания Index[key] = &value, а Delete(key, value) – к операцииприсваивания Index[key] = null.13.1.2. Определение. f(n) = O(g(n)) означает, что с ростом n (при n → ∞) отношение f(n)/g(n)f ( n)= 0 , то f(n) = o(g(n)).остается ограниченным. Если же limn→ ∞ g ( n )f(n) = O(1) означает, что f(n) является ограниченной функцией для всех n, т.е. длявсех n | f(n)| ≤ C, это C можно использовать в качестве значения f(n).13.1.3. Основной недостаток прямой адресации – таблица Index занимает слишком многоместа, если множество всевозможных ключей U достаточно велико (m большоецелое число).

Тем более что обычно число используемых ключей << числавсевозможных ключей, так что большая часть памяти расходуется зря.13.2. Хеширование тоже позволяет обеспечить среднее время операций с данными Tср(n) = O(1) итоже за счет использования таблицы Index. Однако в этом случае таблица содержит места недля всех возможных ключей. Будет показано, что хеш-таблица использует намного меньшуюпамять, чем |U| (мощность множества всех ключей). Она использует память объемом Θ(|K|),где |K| – мощность множества использованных ключей (правда это оценка в среднем, а не вхудшем случае, да и то при определенных предположениях). Пример использованияхеширования – таблица идентификаторов программы, составляемая компилятором (при еесоставлении ключами являются идентификаторы).13.2.1.

При прямой адресации элементу с ключом key отводится строка таблицы с номеромkey, в случае хеш-адресации элементу с ключом key отводится строка таблицы сномером hash(key), где hash: U → {0, 1, 2, …, m – 1} – хеш-функция. Число hash(key)называется хеш-значением ключа key.13.2.2.

Если хеш-значения ключей key1 и key2 совпадают (hash(key1) == hash(key2)), говорят,что случилась коллизия. Конечно, хотелось бы выбрать хеш-функцию, для которойколлизии исключены, но это возможно лишь тогда, когда все возможные значенияключей заранее известны. В общем же случае коллизии неизбежны, так как |U| > m.(с) Кафедра системного программирования ф-та ВМК МГУ, 20101Лекции по курсу “Алгоритмы и алгоритмические языки”, 1 курс, 1 поток, 2010/2011 уч.год13.2.3. Простейший способ обработки коллизий – сцепление элементов с одинаковымизначениями хеш-функции: все такие элементы сцепляются в список, а в хеш-таблицупомещается указатель на первый элемент этого списка.

В пределах каждого такогосписка осуществляется последовательный поиск. Будет показано, что в случаеиспользования двустороннего списка, среднее время выполнения каждой из трехсловарных операций – поиска (Chained-Hash-Search(key)), добавления данных(Chained-Hash-Insert(key, value)) и исключения данных (Chained-Hash-Delete(key,value)) – будет иметь порядок O(1). Основная трудность – в поиске по списку, ноколлизий не очень много и hash(key) можно выбрать так, чтобы списки былидостаточно короткими.13.2.4. Примером хеш-таблицы с цепочками является записная книжка с алфавитом.

Хештаблица с цепочками успешно применяется в компиляторах при формированиитаблицы имен.13.3. Устройство простой хеш-таблицы (реализация хеширования с цепочками).13.3.1. Задается некоторое фиксированное число m (Типичные значения m от 100 до1,000,000).13.3.2. Создается массив Index[m] указателей начал двунаправленных списков (цепочек),который называется индексом хеш-таблицы. В начале работы все указатели имеютзначения null.13.3.3.

Задается хеш-функция hash(), которая получает на вход ключи и выдает значение от0 до m – 1.13.3.4. При добавлении пары (key, value) (Insert(key, value)) вычисляется h = hash(key) и парадобавляется в список *Index[h]: выполняется поиск по этому списку и если в немимеется пара с ключом key, значение заменяется на value; если пары с ключом key всписке нет, то пара (key, value) добавляется в конец списка.13.3.5. При удалении, либо поиске пары (key, value) (Delete(key, value), либо Search(key))вычисляется h = hash(key) и происходит удаление, либо поиск пары (key, value) всписке *Index[h].13.4.

Анализ хеширования с цепочками.13.4.1. Пусть Index[m] – хеш-таблица с m позициями, в которую занесено n пар (key,value). Отношение α = n/m называется коэффициентом заполнения хеш-таблицы.13.4.1.1. Коэффициент заполнения α позволяет судить о качестве хеш-функции:пусть M =1 m∑ | *Index[i] | – средняя длина списков; если hash(key)m i= 01 m− 1( M − | *Index[i] |) 2 ≤ α.∑m i= 013.4.1.2.

В частности, условие (13.4.1.1) исключает наихудший случай, когда хешзначения всех ключей одинаковы, заполнен только один список и поиск вэтом списке из n элементов имеет среднее время Θ(n). Ясно, что такоехеширование бессмысленно.13.4.1.3. Равномерное хеширование: хеш-функция подобрана таким образом, чтокаждый данный элемент может попасть в любую из m позиций хеш-таблицыс равной вероятностью, независимо от того, куда попали другие элементы.13.4.1.4. В случае равномерного хеширования условие (13.4.1.1) выполняется исредняя длина каждого из m списков хеш-таблицы с коэффициентомзаполнения α равна α.– «хорошая» хеш-функция, то дисперсия D =(с) Кафедра системного программирования ф-та ВМК МГУ, 20102Лекции по курсу “Алгоритмы и алгоритмические языки”, 1 курс, 1 поток, 2010/2011 уч.год13.4.1.5.

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

Пусть T – хеш-таблица с цепочками, имеющая коэффициент заполненияα, причем хеширование равномерно. Тогда при поиске элемента, отсутствующего втаблице, будет просмотрено в среднем α элементов таблицы, а, включая время навычисление хеш-функции, будет равно Θ(1 + α).13.4.2. Теорема. При равномерном хешировании среднее время успешного поиска в хештаблице с коэффициентом заполнения α есть Θ(1 + α).13.4.2.1. Замечание.

Теорема не сводится к предыдущей, так как в предыдущейтеореме оценивалось среднее число действий, необходимых для поискаслучайного элемента, равновероятно попадающего в любую из ячеектаблицы. В этой теореме сначала рассматривается случайно выбраннаяпоследовательность элементов, добавляемых в таблицу (на каждом шаге всезначения ключа равновероятны и шаги независимы); потом в полученнойтаблице выбираем элемент для поиска, считая, что все ее элементыравновероятны.13.4.2.2. Доказательство несложное, но требует знания основ теории вероятностей(это видно и из п°. 13.4.2.1).13.4.3. Из теорем 13.4.1 и 13.4.2.

следует, что в случае равномерного хеширования среднеевремя выполнения любой словарной операции есть O(1), т.е. оценивается некоторымпостоянным (своим для каждой операции) значением.13.5. Методы построения хеш-функций.13.5.1. Общие требования13.5.2. Построение хеш-функции методом деления с остатком. Хеш-функция hash(key)определяется соотношениемhash(key) = key % m.При правильном выборе m такая хеш-функция обеспечивает распределение, близкоек равномерному.Правильный выбор m: в качестве m выбирается достаточно большое простое число,далеко отстоящее от степеней двойки.

Например, если устраивает средняя длинасписков 3, а число записей, доступ к которым нужно обеспечить с помощью хештаблицы ≈ 2000, то можно взять m = 2000/3 ≈ 701. Тогда hash(key) = key % 701.Недостаток: в качестве m нельзя брать степень двойки, так как если m = 2p, тоhash(key) – это просто p младших битов числа key.13.5.3. Построение хеш-функции методом умножения.