22 (1106259)

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

Текст из файла

Курс «Алгоритмы и алгоритмические языки»1 семестр 2013/2014Лекция 221Хеш-таблицыСловарные операции: добавление, поиск и удаление элементовпо их ключам.Организуется таблица ключей: массив Index[m] длины m,элементы которого содержат значение ключа и указательна данные (информацию), соответствующие этому ключу.Прямая адресация. Применяется, когда количествовозможных ключей невелико: например, ключиперенумерованы целыми числами из множества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;struct htype *p;/* вычисление хеш-адреса */h = hash (k);/* поиск ключа k */if (index[h]) {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.

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

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

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