Следующей структурой данных, которую мы рассмотрим, будет словарь (map, dictionary) или, так называемый ассоциативный массив, позволяющий хранить пары вида «ключ — значение». Ключ — уникальный идентификатор, а значение может быть любой объектной переменной, включая другие структуры данных. Например, списки или другие словари. Ключи и значения могут выводиться в различном порядке, потому что словари не упорядочены.
Аналогично множеству, у словаря существует мультисловарь (multimap), который позволяет хранить несколько элементов с одинаковым ключом. Посмотрите на примеры ниже.
Довольно часто словари реализуют с использованием хэш-таблиц. Говоря об асимптотической сложности операций со словарем, будем иметь ввиду реализацию на хэш-таблицах.
Основные операции со словарем и их асимптотическая сложность:
- Добавление нового элемента с уникальным ключом — O(1).
- Удаление элемента по ключу — O(1).
- Изменение значения по ключу — O(1).
- Получение значения по ключу — O(1).