Алгоритмы и структуры данных

АТД: Ассоциативный массив

Ассоциативный массив (associative array) — это абстрактный тип данных (АТД), который предпологает хранение пар вида «(ключ, значение)». Данный тип данных также известен как «мапа» или словарь (map, dictionary).

Название «ассоциативный массив» происходит от того факта, что мы «ассоциируем» ключ с значением.

Доступные операции

При работе с словарем ассоциация ключа с значением называется «маппингом» (mapping). На словаре определены следующие операции:

  • Вставка (insert): Добавление новой пары «(ключ, значение)» в коллекцию, то есть маппинг ключа к значению
  • Удаление (remove): удаление пары из коллекции по заданному ключу
  • Обновление (reassign): изменение значения существующей пары для указанного ключа
  • Поиск (lookup): значения по указанному ключу

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

Ассоциативный массив не предпологает хранение нескольких значений для ключа. Однако, мультимапа (мультисловарь) обобщает принцип ассоциативного массива и позволяет хранить несколько значений для ключа. Пример реализации в Java Spring — MultiValueMap.

Порядок обхода

В общем случае при работе с ассоциативным массивом не гарантируется никакого порядка обхода — то есть итерация зависит от реализации.

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

  • Сортировке
  • Порядке вставки пар

Пример применения

Ассоциативный массив может применяться в следующих областях:

Реализация

Существует 2 наиболее известные и применяющиеся на практике реализации ассоциативного массива (структуры данных):

  • Хэш-таблица (Hash table)
  • Дерево поиска (Search Tree)

В следующей статье мы рассмотрим структуру данных Хэш-таблица.

Добавить комментарий

Ваш адрес email не будет опубликован.