Ассоциативный массив
В информатике ассоциативный массив , карта , таблица символов или словарь — это абстрактный тип данных , который хранит набор пар (ключ, значение) , так что каждый возможный ключ появляется в наборе не более одного раза. С математической точки зрения ассоциативный массив — это функция с конечной областью определения . [1] Он поддерживает операции поиска, удаления и вставки.
Проблема словаря — это классическая проблема проектирования эффективных структур данных , реализующих ассоциативные массивы. [2] Двумя основными решениями проблемы словаря являются хеш-таблицы и деревья поиска . [3] [4] [5] [6] В некоторых случаях также возможно решить проблему, используя массивы с прямой адресацией , бинарные деревья поиска или другие более специализированные структуры.
Многие языки программирования включают ассоциативные массивы в качестве примитивных типов данных , и они доступны в программных библиотеках для многих других. Память с адресацией по содержимому — это форма прямой аппаратной поддержки ассоциативных массивов.
Ассоциативные массивы имеют множество применений, включая такие фундаментальные шаблоны программирования, как мемоизация и шаблон декоратора . [7]
Название происходит не от ассоциативного свойства , известного в математике. Скорее, это происходит из-за того, что мы связываем значения с ключами. Не следует путать с ассоциативными процессорами .
В ассоциативном массиве связь между ключом и значением часто называется «отображением», и одно и то же слово «отображение» также может использоваться для обозначения процесса создания новой ассоциации.
