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

Ключевые вопросы параграфа

  • Что такое словарь и зачем он нужен?

  • Какие операции поддерживает словарь и какова их сложность?

  • Как реализуются словари в языках программирования и почему хеш-таблицы — хороший выбор?

Определения словаря

Следующей структурой данных, которую мы рассмотрим, будет словарь (map, dictionary), или так называемый ассоциативный массив, позволяющий хранить пары вида «ключ — значение». Ключ — уникальный идентификатор, а значение может быть любой объектной переменной, включая другие структуры данных. Например, списки или другие словари. Ключи и значения могут выводиться в различном порядке, потому что словари не упорядочены.

Аналогично множеству, у словаря существует мультисловарь (multimap), который позволяет хранить несколько элементов с одинаковым ключом. Посмотрите на примеры ниже.

algosy

Довольно часто словари реализуют с использованием хеш-таблиц. Говоря об асимптотической сложности операций со словарём, будем иметь ввиду реализацию на хеш-таблицах.

Основные операции со словарем и их асимптотическая сложность:

  1. Добавление нового элемента с уникальным ключом — .
  2. Удаление элемента по ключу — .
  3. Изменение значения по ключу — .
  4. Получение значения по ключу — .

Что дальше

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

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

А пока вы не ушли дальше — закрепите материал на практике:

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

Хотите обсудить, задать вопрос или не понимаете, почему код не работает? Мы всё предусмотрели — вступайте в сообщество Хендбука! Там студенты помогают друг другу разобраться.

Ключевые выводы параграфа

  • Словарь хранит пары «ключ — значение» и обеспечивает быстрый доступ по ключу.
  • Большинство операций (добавление, удаление, поиск) выполняются за константное время при реализации через хеш-таблицу.
  • Словари часто используют для подсчёта, группировки и хранения вложенных структур.
  • Мультимапы позволяют хранить несколько значений для одного ключа.
Чтобы добавить в заметки выделенный текст, нажмите Ctrl + E
Предыдущий параграф2.2. Множество
Следующий параграф2.4. Дек