Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
All ATD конспект.docx
Скачиваний:
5
Добавлен:
01.04.2025
Размер:
80 Кб
Скачать
☆

36. Словари. Методы их реализации

Применение множеств при разработке алгоритмов не всегда требует таких мощных операторов, как операторы объединения и пересечения. Часто достаточно только хранить в множестве "текущие" объекты с периодической вставкой или удалением некоторых из них. Время от времени также возникает необходимость узнать, присутствует ли конкретный элемент в данном множестве.

Абстрактный тип множеств с операторами INSERT, DELETE и MEMBER называется DICTIONARY (Словарь).

Мы также включим оператор MAKENULL в набор операторов словаря - он потребуется при реализации АТД для инициализации структур данных.

Реализация

Словари можно представить посредством сортированных или несортированных связанных списков.

Другая возможная реализация словарей использует двоичные векторы, предполагая, что элементы данного множества являются целыми числами 1, ..., N для некоторого N или элементы множества можно сопоставить с таким множеством целых чисел.

Третья возможная реализация словарей использует массив фиксированной длины с указателем на последнюю заполненную ячейку этого массива. Эта реализация выполнима, если мы точно знаем, что размер множества не превысит заданную длину массива.

37. Структуры данных основанные на хеш-таблицах

Существует еще один полезный и широко используемый метод реализации словарей, который называется хешированием.

Мы рассмотрим две различные формы хеширования.

Одна из них называется открытым, или внешним, хешированием (частный случай расширенного хеширования) и позволяет хранить множества в потенциально бесконечном пространстве, снимая тем самым ограничения на размер множеств.

Другая называется закрытым, или внутренним или прямым, хешированием и использует ограниченное пространство для хранения данных, ограничивая таким образом размер множеств.

38. Оценка эффективности хеш-функций

Хеширование — преобразование входного массива данных произвольной длины в выходную битовую строку фиксированной длины. Такие преобразования также называются хеш-функциями или функциями свёртки, а их результаты называют хешем, хеш-кодом. Примеры алгоритмов хеширования: CRC, MD4, Tiger.

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

Основными требованиями к хэш-функции являются:

– уменьшение возможности подбора ключа в случае применения хеш-функции в

криптографии;

– равномерное распределение значения свертки в случае применения хеш-функции в структурах данных;

– генерация последовательностей чисел, которые невозможно отличить от случайных, используемых в имитационном моделировании.

Процедура оценки эффективности алгоритмов хеширования включает ряд задач, в том числе:

– определение временной сложности алгоритма;

– расчет вероятности возникновения коллизий;

– оценка возможности подбора ключа (для алгоритмов, применяемых в криптографии).

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]