Слайды лекций - 2014 (лектор - Белеванцев А. А.) (1107979), страница 16

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 16)

Применяется, когда количествовозможных ключей невелико: например, ключиперенумерованы целыми числами из множестваU = {0, 1, 2, …, m – 1}, где m не очень большое число.В случае прямой адресации ключ с номером kсоответствует элементу Index[k]. Этот ключ обычно незаписывается в элемент массива, т.к. совпадает синдексом.Все три словарные операции выполняются за времяпорядка O(1).Основной недостаток прямой адресации – таблица Indexзанимает слишком много места, если множествовсевозможных ключей U достаточно велико2(m большое целое число).Хеш-таблицыХеширование тоже позволяет обеспечить среднее времяопераций с данными Tср(n) = O(1) и тоже за счет использованиятаблицы Index.Хеш-таблица использует память объемом Θ(|K|), где |K| –мощность множества использованных ключей (правда это оценкав среднем, а не в худшем случае, да и то при определенныхпредположениях).Пример использования хеширования – таблицаидентификаторов программы, составляемая компилятором.В случае хеш-адресации элементу с ключом key отводитсястрока таблицы с номером hash(key), гдеhash: U → {0, 1, 2, …, m – 1} – хеш-функция.Число hash(key) называется хеш-значением ключа key.Если хеш-значения ключей key1 и key2 совпадают(hash(key1) == hash(key2)), говорят, что случилась коллизия.Выбрать хеш-функцию, для которой коллизии исключены,возможно лишь тогда, когда все возможные значения ключейзаранее известны.3В общем же случае коллизии неизбежны, так как |U| > m.Хеш-таблицыПростейший способ обработки коллизий – сцепление элементовс одинаковыми значениями хеш-функции: все такие элементысцепляются в список, а в хеш-таблицу помещается указатель напервый элемент этого списка.

В пределах каждого такого спискаосуществляется последовательный поиск.В случае использования двусвязного списка среднее времявыполнения каждой из трех словарных операций будет иметьпорядок O(1). Основная трудность – в поиске по списку, ноколлизий не очень много и hash(key) можно выбрать так, чтобысписки были достаточно короткими.Примером хеш-таблицы с цепочками является записная книжка салфавитом.4Хеш-таблицыУстройство простой хеш-таблицы (реализация хеширования сцепочками).Задается некоторое фиксированное число m(типичные значения m от 100 до 1,000,000).Создается массив Index[m] указателей началдвусвязных списков (цепочек), который называетсяиндексом хеш-таблицы.

В начале работы все указателиимеют значения NULL.Задается хеш-функция hash(), которая получает на входключи и выдает значение от 0 до m – 1.При добавлении пары (key, value) вычисляетсяh = hash(key) и пара добавляется в список Index[h].При удалении либо поиске пары (key, value) вычисляетсяh = hash(key) и происходит удаление либо поиск пары(key, value) в списке Index[h].5Хеш-таблицыАнализ хеширования с цепочками.Пусть Index[m] – хеш-таблица с m позициями, в которуюзанесено n пар (key, value).

Отношение α = n/mназывается коэффициентом заполнения хеш-таблицы.Коэффициент заполнения α позволяет судить о качествехеш-функции: m −11M =пусть∑ | Index[i ] | – средняя длина списков;mi =0если hash(key) – «хорошая» хеш-функция, то1 m −1дисперсия D = ∑ (M − | Index[i ] |)2 ≤ α.mi =0Это условие исключает наихудший случай, когда хешзначения всех ключей одинаковы, заполнен только одинсписок и поиск в этом списке из n элементов имеетсреднее время Θ(n).6Хеш-таблицыАнализ хеширования с цепочками.Равномерное хеширование: хеш-функция подобранатаким образом, что каждый данный элемент можетпопасть в любую из m позиций хеш-таблицы с равнойвероятностью, независимо от того, куда попали другиеэлементы.Условие из предыдущего слайда выполняется и средняядлина каждого из m списков хеш-таблицы скоэффициентом заполнения α равна α.Среднее время поиска элемента, отсутствующего втаблице, пропорционально средней длине списка α,так как поиск сводится к просмотру одного из списков.Поскольку среднее время вычисления хеш-функцииравно Θ(1), то среднее время выполнения каждой изсловарных операций с учетом вычисления хеш-функцииравно Θ(1 + α).7Хеш-таблицыТеорема.

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

Теорема не сводится к предыдущей, так какв предыдущей теореме оценивалось среднее числодействий, необходимых для поиска случайного элемента,равновероятно попадающего в любую из ячеек таблицы.В этой теореме сначала рассматривается случайновыбранная последовательность элементов, добавляемыхв таблицу (на каждом шаге все значения ключа равновероятныи шаги независимы); потом в полученной таблице выбираемэлемент для поиска, считая, что все ее элементы равновероятны.Из теорем следует, что в случае равномерного хешированиясреднее время выполнения любой словарной операции есть O(1).8Методы построения хеш-функцийПостроение хеш-функции методом деления с остатком.Хеш-функция 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.9Методы построения хеш-функцийПостроение хеш-функции методом умножения.Пусть количество хеш-значений равно m.Выберем и зафиксируем вещественную константуv, 0 < v < 1; положим hash(key) = m(frac(key⋅v )frac(key⋅v) – дробная часть числа key⋅v.Достоинство метода умножения в том, что качество хешфункции слабо зависит от выбора m. Обычно в качествеm выбирают степень двойки, так как в этом случаеумножение на m сводится к сдвигу.Пример.

Пусть в используемом компьютере длина словаравна w битам и ключ key помещается в одно слово.Если m = 2p, то вычисление hash(key) можно выполнитьследующим образом: умножим key на w-битовое целоечисло v⋅2w; получится 2w-битовое число r0.В качестве значения hash(key) возьмем старшие p битов“дробной” части числа r0 / 2w (r0 %2w или обнуление wстарших разрядов, потом умножение на m = 2p).Согласно Д. Кнуту выбор v = 5 − 1 / 2 = 0.6180339887...является удачным.10()Хеш-функции: программы#define MAX 701/* размер хеш-таблицы */struct htype {int key;/* ключ */int val;/* значение элемента данных */struct htype *next;/* указатель на следующий элементцепочки */struct htype *prvs;/* указатель на предыдущий элементцепочки */};struct htype *index[MAX];11Хеш-функции: программы#define MAX 701/* размер хеш-таблицы */static inline int hash (int key) {return key % MAX;}/* инициализация хеш-таблицы */void init (void) {int i;for (i = 0; i < MAX; i++)index[i] = NULL; /* массив начал цепочек */}12Хеш-функции: программы/* Вычисление хеш-адреса и поиск по ключу k:если элемент с ключом k найден, возвращаем указательна него, если нет, возвращаем NULL */struct htype *search (int k) {/* вычисление хеш-адреса */int h = hash (k);/* поиск ключа k */if (index[h]) {struct htype *p = index[h];do {if (p->key == k)return p;elsep = p->next;} while (p);}return NULL;}13Хеш-функции: программы/* Порождение нового элемента цепочки и возврат указателяна него */struct htype *new (void) {struct htype *p;p = (struct htype *) malloc (sizeof (struct htype));if (!p)abort ();p->key = -1;p->val = 0;p->next = NULL;p->prvs = NULL;return p;}14Хеш-функции: программы/* Вычисление хеш-адреса и поиск по ключу k: если элемент с ключом kнайден, возвращаем значение true и указатель на найденный элемент;если элемент не найден, возвращаем значение false и указатель напоследний элемент либо NULL, если цепочка пустая */static bool search_internal (int k, struct htype **r) {struct htype *p, *q;if ((p = index[hash (k)]) != NULL) {do {if (p->key == k) {*r = p;return true;}elseq = p, p = p->next;} while (p);*r = q;} else*r = NULL;return false;}15Хеш-функции: программы/* Добавление новой пары (key, value) */void insert (int k, int v) {struct htype *p, *q;/* Если элемент с ключом k уже имеется в цепочке,изменяем его значение на v */if (search_internal (k, &p))p->val = v;else {/* Если элемента с ключом k в цепочке нет *//* порождение и инициализация нового элемента цепочки */q = new ();q->key = k;q->val = v;/* Включение порожденного элемента в цепочку */if (p) {p->next = q;q->prvs = p;} elseindex[hash (k)] = q;}}16Хеш-функции: программы/* Исключение пары (key, value) */void delete (int k, int v) {struct htype *p;if (search_internal (k, &p)) {if (p->prvs)p->prvs->next = p->next;elseindex[hash (k)] = p->next;if (p->next)p->next->prvs = p->prvs;free (p);}/* иначе ничего не нашли, удалять не нужно */}17Хеширование с открытой адресациейВсе записи хранятся в самой хеш-таблице: каждая ячейкатаблицы (массива длины m) содержит либо хранимый элемент,либо NULL.

Характеристики

Список файлов лекций