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