курсовая открытое хэширование и метод цепочек. Хэштаблица (открытая адресация) vs Хэштаблица (метод цепочек)
 Скачать 451.72 Kb.
|
|
МИНОБРНАУКИ РОССИИ САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ ЭЛЕКТРОТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ «ЛЭТИ» ИМ. В.И. УЛЬЯНОВА (ЛЕНИНА) Кафедра МО ЭВМ КУРСОВАЯ РАБОТА по дисциплине «Алгоритмы и структуры данных» Тема: Хэш-таблица (открытая адресация) vs Хэш-таблица (метод цепочек). Исследование Студент гр. 0383 Смирнов И.А. Преподаватель Берленко Т.А. Санкт-Петербург 2021 АННОТАЦИЯ Курсовая работа представляет собой написание программы на языке Python, реализующей два метода хэширования: метод цепочек и открытая адресация, а также исследование работы этих методов 2 СОДЕРЖАНИЕ Введение 4 1. Задание 5 2. Теоретические сведения 6 3. Ход работы 7 3.1. Хэширование методов цепочек 7 3.2. Хэширование с открытой адресацией 8 4. Асимптотика 9 4.1. Теоретическое время 9 4.2. Практическое время Заключение 9 19 Приложение А 20 3 ВВЕДЕНИЕ Целью работы является написание корректной программы, реализующей два метода хэширования: метод цепочек и открытая адресация, а также исследование с её помощью работы этих методов 4 1. ЗАДАНИЕ Студент Смирнов И.А. Группа 0383 Тема работы: Хэш-таблица (открытая адресация) vs Хэш-таблица (метод цепочек). Исследование. Вариант 5 Хэш-таблица (открытая адресация) vs Хэш-таблица (метод цепочек). - "Исследование" - реализация требуемых структур данных/алгоритмов; генерация входных данных (вид входных данных определяется студентом); использование входных данных для измерения количественных характеристик структур данных, алгоритмов, действий; сравнение экспериментальных результатов с теоретическими. Вывод промежуточных данных не является строго обязательным, но должна быть возможность убедиться в корректности алгоритмов. Содержание пояснительной записки: «Содержание», «Введение», «Ход работы», «Асимптотика», «Анализ результатов» «Заключение» Предполагаемый объем пояснительной записки: Не менее 15 страниц. Дата выдачи задания: 1.09.2021 Дата сдачи реферата: 28.12.2021 Дата защиты реферата: 28.12.2021 Студентка гр. 0383 Смирнов И.А. Преподаватель Берленко Т.А. 5 1. ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ Хэш-таблица — это структура данных, реализующая интерфейс ассоциативного массива, она позволяет хранить пары элементов формата ключ - значение и выполнять следующие операции: добавление, поиск и удаление по ключу. Выполнение операций в хэш-таблице напрямую зависит от вычисленной хэш-функции от ключа элемента, это значение играет роль индекса. Дальнейшие реализации операций зависит от реализации самой хэш-таблицы. Хэш-функция отображает значения ключей на ограниченный интервал хэш-значений, в результате чего нескольким ключам может соответствовать одно и то же хэш-значение. Такая ситуация называется коллизией, и методы разрешения таких ситуаций являются основной отличительной чертой разных типов хэш-таблиц Иногда условия задачи позволяют вовсе избежать таких ситуаций, например если все множество ключей известно заранее и не изменяется, то можно подобрать хэш функцию способную распределить все пары элементов по таблице без коллизий. Одними из методов разрешения коллизий являются исследуемые в данной курсовой работе метод цепочек и открытая адресация. Метод цепочек ставит в таблице парой к хэш значению связный список пар ключ-значение, определенных туда хэш функцией Метод открытой адресации при возникновении коллизии определяет пару ключ-значение в ближайшую доступную ячейку 6 2. ХОД РАБОТЫ 2.1. Хэширование методом цепочек Для хранения элементов хеш-таблицы реализован класс ChainHashUnit, объекты которого представляют собой узлы связных списков. В классе хеш-таблицы при создании объекта указывается размер таблицы и автоматически создается список указанного размера, заполненный None элементами. Хэш функция (метод hash_func) сопоставляет ключу хэш значение, равное его остатку при делении на размер хэш таблицы Помимо описанных в классе хэш таблицы реализованы следующие методы: ● insert(key, data) – добавление элемента по ключу в таблицу. Вычисляется хеш-значение от ключа key и вставляет пару в ячейку с индексом равным хэш значению данную пару элементов в виде объекта ChainHashUnit, привязывая к его полю next находившийся в этой ячейке ранее список элементов (или None, если других пар соответствующих данному хэш значению в таблицу ещё не занесено) ● search(key) – поиск элемента по ключу key. Вычисляется хэш значение по ключу, полученное значение используется как индекс по которому ищется связный список элементов, соответствующих этому значению, список прогоняется, пока не закончится или пока не найдется пара элементов с искомым ключом. В случае нахождения нужной пары возвращается её значащая часть, иначе None ● delete(key) – удаление элемента по ключу key. Выполняются действия аналогичные поиску элемента по ключу. В случае нахождения нужной пары элементов происходит привязка предыдущего узла к следующему за удаляемым 7 2.2. Хэширование с открытой адресацией Для хранения элементов хеш-таблицы реализован класс OpenHashUnit, объекты которого представляют собой пары ключ - значение с флагом занятости ячейки. В классе хеш-таблицы при создании объекта указывается размер таблицы и автоматически создается список указанного размера, заполненный None элементами. Хэш функция (метод hash_func) сопоставляет ключу хэш значение, равное его остатку при делении на размер хэш таблицы Помимо описанных в классе хэш таблицы реализованы следующие методы: ● insert(key, data) – добавление элемента по ключу key. Вычисляется хэш значение от ключа key и в случае незанятости данного хэш значения в таблице (элемент таблицы не занят, если он None или если его флаг занятости установлен на false) пара элементов ставится напротив своего хэш значения в виде объекта OpenHashUnit, в противном случае ищется ближайший незанятый элемент таблицы за диапазоном прямых хэш-значений и пара ставится туда ● search(key) – поиск элемента по ключу key. Вычисляется хэш значение от ключа key и проверяется пара элементов, соответствующая данному хэш значению, если данный элемент таблицы занят и ключ соответствует искомому, возвращается его значащая часть, в противном случае линейно (k = 1) проходится диапазон значений добавленных по коллизии, и в случае нахождения занятого элемента с данным ключом возвращается его значащая часть, иначе None ● delete(key) – удаление элемента по ключу key. Производятся действия аналогичные поиску элемента по ключу. В случае нахождения занятого элемента с данным ключом флаг занятости элемента устанавливается в false 8 3. АСИМПТОТИКА 3.1. Теоретическое время Все три операции в среднем выполняются за О(1), за исключением случая расширения таблицы или при вставке с одним и тем же ключом, при достижении или превышении заполненности таблицы разрешимых показателей Таблица 1 – Теоретическое время Операции В лучшем В среднем В худшем Поиск О(1) О(a) О(n) Вставка О(1) О(а) О(n) Удаление О(1) О(a) О(n) а - количество коллизий 3.2. Практическое время В файле main.py реализован прогон методов двух хэш таблиц разных типов по времени для одинаковых случайно генерирующихся наборов ключ-значение. Для каждого метода составлена диаграмма затраченного времени для каждой пары ключ - значение а также в конце работы программа выводит средние показатели. Входные данные для исследования: ● 50000 элементов в таблице ● 0 до 10000000 9 3.2.1. Лучший случай Убираем возможность возникновения коллизий путем перебора значений ключей от 0 до размера таблицы Рисунок 1 — вставка метод открытой адресации лучший случай Рисунок 2 — вставка метод цепочек лучший случай За редкими исключениями, вызванными, вероятно, погрешностями таймеров, оба метода линейно обрабатывают вставку. 10 Так как метод цепочек имеет максимально простой метод вставки в голову списка без каких либо проверок, в нём эти исключения проявляются реже Рисунок 3 — поиск метод открытой адресации лучший случай Рисунок 4 — поиск метод цепочек лучший случай Здесь же исключений не наблюдается вовсе, видно, что оба метода отрабатывают поиск практически мгновенно, что от них и ожидается 11 Рисунок 5 — удаление метод открытой адресации лучший случай Рисунок 6 — удаление метод цепочек лучший случай Здесь же исключений также не наблюдается, видно, что оба метода отрабатывают удаление практически мгновенно, что от них и ожидается В лучшем случае оба метода подтверждают ожидаемые результаты 12 3.2.2. Средний случай Значения ключей генерируются с шагом во взаимно простое количеству объектов число, что даёт примерно равное распределение количества случаев коллизий между ключами Рисунок 7 — вставка метод открытой адресации средний случай Рисунок 8 — вставка метод цепочек средний случай Несмотря на добавление некоторого количества случаев коллизии, методы показывают примерно те же результаты, что и в лучшем случае 13 Рисунок 9 — поиск метод открытой адресации средний случай Рисунок 10 — поиск метод цепочек средний случай Методы показывают результаты аналогичные лучшему случаю 14 Рисунок 11 — удаление метод открытой адресации средний случай Рисунок 12 — удаление метод цепочек средний случай Методы показывают результаты аналогичные лучшему случаю В среднем случае явной модуляции от n не наблюдается 15 3.2.3. Худший случай Значения ключей генерируются с шагом по количеству объектов число, все хэш-значения ключей совпадают Рисунок 13 — вставка метод открытой адресации худший случай Рисунок 14 — вставка метод цепочек худший случай Ввиду реализации добавления в начало а не конец списка метод цепочек продолжает справляться практически мгновенно 16 В методе открытой адресации четко видна линейная модуляция по мере возрастания n, это именно то, что мы должны видеть при сложности O(n) Рисунок 15 — поиск метод открытой адресации худший случай Рисунок 16 — поиск метод цепочек худший случай Продолжаем видеть модуляцию в методе открытой адресации, в методе же цепочек модуляция обратная, что вызвано обратным хранением ключей в списке, чем больше ключ в данном тестировании, тем ближе его искать 17 Рисунок 17 — удаление метод открытой адресации худший случай Рисунок 18 — удаление метод цепочек худший случай По аналогичным причинам видим модуляцию у метода открытой адресации и обратную модуляцию у метода цепочек 18 ЗАКЛЮЧЕНИЕ В ходе работы были реализованы и исследованы 2 типа решений проблем с коллизией в хэш таблицах - метод цепочек и метод открытой адресации. Метод цепочек позволяет схитрить со временем вставки, сократив его до О(1) в худшем случае, более того в методе открытой адресации часто могут возникать случаи необходимости расширения таблицы просто от увеличения числа подаваемых элементов. Также метод цепочек менее подвержен модуляции при “ухудшении” случая, однако этот факт является лишь делом оптимизации и свойственен исключительно написанным мною реализациям 19 ПРИЛОЖЕНИЕ A ИСХОДНЫЙ КОД ПРОГРАММЫ Название файла: OpenHash.py class OpenHashUnit: def __init__(self, key, data): self.key = key self.data = data self.flag = True def is_free(self): return not self.flag class OpenHash: def __init__(self, size): self.initial_size = size self.size = size*2 self.table = [None] * self.size*2 self.dilimeter = self.size def hash_func(self, key): return key % self.dilimeter def insert(self, key, data): index = self.hash_func(key) if self.table[index] is None or self.table[index].is_free(): self.table[index] = OpenHashUnit(key, data) else: i = self.initial_size while i < self.size: if self.table[i] is None: self.table[i] = OpenHashUnit(key, data) return if self.table[i].is_free(): self.table[i].key = key self.table[i].data = data self.table[i].flag = True return i += 1 new_size = self.size*2 tmp = OpenHash(new_size) for i in range(self.size): tmp.table[i] = self.table[i] self.table = tmp.table self.size = new_size self.table[i] = OpenHashUnit(key, data) def search(self, key): if self.table[self.hash_func(key)] is not None and self.table[self.hash_func(key)].key == key: 20 return self.table[self.hash_func(key)].data i = self.initial_size while i < self.size: if self.table[i] is None: i += 1 continue if not self.table[i].is_free() and self.table[i].key == key: return self.table[i].data i += 1 return None def delete(self, key): if self.table[self.hash_func(key)] is not None and not self.table[self.hash_func(key)].is_free() and self.table[self.hash_func(key)].key == key: self.table[self.hash_func(key)].flag = False else: i = self.initial_size while i < self.size: if self.table[i] is not None and not self.table[i].is_free() and self.table[i].key == key: self.table[i].flag = False return i += 1 Название файла: СhainHash.py class ChainHashUnit: def __init__(self, key, data, next=None): self.key = key self.data = data self.next = next class ChainHash: def __init__(self, size): self.size = size self.table = [None] * self.size def hash_func(self, key): return key % self.size def insert(self, key, data): self.table[self.hash_func(key)] = ChainHashUnit(key, data, self.table[self.hash_func(key)]) def search(self, key): cur = self.table[self.hash_func(key)] while cur is not None: if key == cur.key: return cur.data cur = cur.next 21 return None def delete(self, key): index = self.hash_func(key) prev = self.table[index] if prev is None: return if key == prev.key: self.table[index] = self.table[index].next return cur = prev.next while cur is not None: if key == cur.key: prev.next = cur.next return prev = cur cur = cur.next Название файла: main.py from ChainHash import * from OpenHash import * import matplotlib.pyplot as plt from time import time_ns from random import randint '''лучший случай''' objects_amount = 50000 random_limit = 10000000 table_size = 50000 keys = [x for x in range(objects_amount)] values = [randint(0, random_limit) for x in range(objects_amount)] '''средний случай''' # objects_amount = 50000 # random_limit = 10000000 # table_size = 50000 # # keys = [13*x for x in range(objects_amount)] # values = [randint(0, random_limit) for x in range(objects_amount)] '''худший случай''' # objects_amount = 10000 # random_limit = 10000000 # table_size = 10000 # # keys = [x*table_size for x in range(objects_amount)] # values = [randint(0, random_limit) for x in range(objects_amount)] open_hash_table = OpenHash(table_size) open_insert_time = [] open_search_time = [] 22 open_delete_time = [] chain_hash_table = ChainHash(table_size) chain_insert_time = [] chain_search_time = [] chain_delete_time = [] for key, value in zip(keys, values): start_time = time_ns() open_hash_table.insert(key, value) end_time = time_ns() open_insert_time.append(end_time - start_time) start_time = time_ns() chain_hash_table.insert(key, value) end_time = time_ns() chain_insert_time.append(end_time - start_time) for key in keys: start_time = time_ns() open_hash_table.search(key) end_time = time_ns() open_search_time.append(end_time - start_time) start_time = time_ns() chain_hash_table.search(key) end_time = time_ns() chain_search_time.append(end_time - start_time) for key in keys: start_time = time_ns() open_hash_table.delete(key) end_time = time_ns() open_delete_time.append(end_time - start_time) start_time = time_ns() chain_hash_table.delete(key) end_time = time_ns() chain_delete_time.append(end_time - start_time) plt.figure(figsize=(16, 8)) plt.plot(keys, open_insert_time, color='red') plt.figure(figsize=(16, 8)) plt.plot(keys, open_search_time, color='blue') plt.figure(figsize=(16, 8)) plt.plot(keys, open_delete_time, color='green') plt.figure(figsize=(16, 8)) plt.plot(keys, chain_insert_time, color='red') plt.figure(figsize=(16, 8)) plt.plot(keys, chain_search_time, color='blue') 23 plt.figure(figsize=(16, 8)) plt.plot(keys, chain_delete_time, color='green') plt.show() print(f"average insert time: {sum(open_insert_time)/objects_amount} for open and {sum(chain_insert_time)/objects_amount} for chain") print(f"average search time: {sum(open_search_time)/objects_amount} for open and {sum(chain_search_time)/objects_amount} for chain") print(f"average delete time: {sum(open_delete_time)/objects_amount} for open and {sum(chain_delete_time)/objects_amount} for chain") 24 |