Лекция 13. Хеш-таблицы (1107988)
Текст из файла
Лекции по курсу “Алгоритмы и алгоритмические языки”, 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. Построение хеш-функции методом умножения.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
