ИПЗ Алгоритмы. ИПЗ Алгоритмы. Российский государственный социальный университет итоговое практическое задание по дисциплине Алгоритмы и структуры данных
 Скачать 73.11 Kb.
|
ИТОГОВОЕ ПРАКТИЧЕСКОЕ ЗАДАНИЕ по дисциплине «Алгоритмы и структуры данных»
Москва 2022 Задание: Спроектируйте (постановка задачи, обоснование выбранной технологии организации хэширования) и реализуйте хэш-таблицу с учётом необходимости обработки коллизий (например, на основе связных списков). Представить скриншоты программы и результат тестирование работы программы. Хэш-таблица - структура данных, реализующая интерфейс ассоциативного массива. В отличие от деревьев поиска, реализующих тот же интерфейс, обеспечивают меньшее время отклика в среднем. Представляет собой эффективную структуру данных для реализации словарей, а именно, она позволяет хранить пары (ключ, значение) и выполнять три операции: операцию добавления новой пары, операцию поиска и операцию удаления пары по ключу. Коллизии Когда хеш-функция генерирует один индекс для нескольких ключей, возникает конфликт: неизвестно, какое значение нужно сохранить в этом индексе. Это называется коллизией хеш-таблицы. Есть несколько методов борьбы с коллизиями: метод цепочек; метод открытой адресации: линейное и квадратичное зондирование. Метод цепочек Суть этого метода проста: если хеш-функция выделяет один индекс сразу двум элементам, то храниться они будут в одном и том же индексе, но уже с помощью двусвязного списка. Если j — ячейка для нескольких элементов, то она содержит указатель на первый элемент списка. Если же j пуста, то она содержит NIL. Открытая адресация В отличие от метода цепочек, в открытой адресации несколько элементов в одной ячейке храниться не могут. Суть этого метода заключается в том, что каждая ячейка либо содержит единственный ключ, либо NIL. Существует несколько видов открытой адресации: a) Линейное зондирование Линейное зондирование решает проблему коллизий с помощью проверки следующей ячейки. h(k, i) = (h′(k) + i) mod m, где i = {0, 1, ….} h'(k) — новая хеш-функция Если коллизия происходит в h(k, 0), тогда проверяется h(k, 1). То есть значение i увеличивается линейно. Проблема линейного зондирования заключается в том, что заполняется кластер соседних ячеек. Это приводит к тому, что при вставке нового элемента в хеш-таблицу необходимо проводить полный обход кластера. В результате время выполнения операций с хеш-таблицами увеличивается. b) Квадратичное зондирование Работает оно так же, как и линейное — но есть отличие. Оно заключается в том, что расстояние между соседними ячейками больше (больше одного). Это возможно благодаря следующему отношению: h(k, i) = (h′(k) + c1i + c2i2) mod m, где c1 и c2 — положительные вспомогательные константы, i = {0, 1, ….} c) Двойное хэширование Если коллизия возникает после применения хеш-функции h(k), то для поиска следующей ячейки вычисляется другая хеш-функция. h(k, i) = (h1(k) + ih2(k)) mod m Где применяются Когда необходима постоянная скорость поиска и вставки. В криптографических приложениях. Когда необходима индексация данных. Реализация хэш таблицы на языке Python  Результат прогрыммы :  |
