Ассоциативный массив - Associative array

"Словарь (структура данных)" перенаправляется сюда. Не следует путать с словарь с данными.
«Ассоциативный контейнер» перенаправляется сюда. О реализации упорядоченных ассоциативных массивов в стандартной библиотеке языка программирования C ++ см. ассоциативные контейнеры.
"Карта (информатика)" перенаправляется сюда. Для функции высшего порядка см. Карта (функция высшего порядка).

В Информатика, ассоциативный массив, карта, таблица символов, или толковый словарь является абстрактный тип данных состоит из коллекция из (ключ, значение) пары, так что каждый возможный ключ появляется в коллекции не более одного раза.

Операции, связанные с этим типом данных, позволяют:[1][2]

  • добавление пары в коллекцию
  • удаление пары из коллекции
  • модификация существующей пары
  • поиск значения, связанного с определенным ключом

Реализация ассоциативных массивов ставит проблема словаря, классическая задача информатики: задача проектирования структура данных который поддерживает набор данных во время операций «поиск», «удаление» и «вставка».[3]Два основных решения проблемы словаря: хеш-таблица или дерево поиска.[1][2][4][5]В некоторых случаях также возможно решить проблему, используя непосредственно адресованные массивы, деревья двоичного поиска, или другие более специализированные структуры.

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

Ассоциативные массивы имеют множество приложений, в том числе такие фундаментальные. шаблоны программирования так как мемоизация и декоратор шаблон.[6]

Название происходит не от ассоциативное свойство известен в математике. Скорее, это происходит из-за того, что мы связываем значения с ключами.

Операции

В ассоциативном массиве связь между ключ и значение часто называют «отображением», и то же словесное отображение может также использоваться для обозначения процесса создания новой ассоциации.

Для ассоциативного массива обычно определяются следующие операции:[1][2]

  • Добавить или вставить: добавить новый пара в коллекцию, сопоставляя новый ключ с его новым значением. Аргументами этой операции являются ключ и значение.
  • Переназначить: заменить значение в одном из пары, которые уже находятся в коллекции, отображая существующий ключ на новое значение. Как и при вставке, аргументами этой операции являются ключ и значение.
  • удалять или Удалить: удалить пара из коллекции, отключив данный ключ от его значения. Аргумент этой операции - это ключ.
  • Искать: найти значение (если есть), связанное с данным ключом. Аргументом этой операции является ключ, а значение возвращается из операции. Если значение не найдено, некоторые реализации ассоциативного массива вызывают исключение, в то время как другие создают пару с данным ключом и значением по умолчанию для типа значения (ноль, пустой контейнер ...).

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

Кроме того, ассоциативные массивы могут также включать в себя другие операции, такие как определение количества сопоставлений или построение итератор чтобы перебрать все сопоставления. Обычно для такой операции порядок, в котором возвращаются сопоставления, может определяться реализацией.

А Multimap обобщает ассоциативный массив, позволяя связывать несколько значений с одним ключом.[7] А двунаправленная карта - это связанный абстрактный тип данных, в котором сопоставления действуют в обоих направлениях: каждое значение должно быть связано с уникальным ключом, а вторая операция поиска принимает значение в качестве аргумента и ищет ключ, связанный с этим значением.

пример

Предположим, что набор кредитов, предоставленных библиотекой, представлен в структуре данных. Каждую книгу в библиотеке может проверять только один посетитель библиотеки одновременно. Однако один посетитель может проверить несколько книг. Таким образом, информация о том, какие книги проверены для каких клиентов, может быть представлена ​​ассоциативным массивом, в котором книги являются ключами, а посетители - значениями. Используя обозначения из Python или JSON, структура данных будет такой:

{    "Гордость и предубеждение": "Алиса",    "Грозовой перевал": "Алиса",    "Большие Надежды": "Джон"}

Операция поиска по ключу «Большие надежды» вернет «Джон». Если Джон вернет свою книгу, это вызовет операцию удаления, а если Пэт извлечет книгу, это вызовет операцию вставки, что приведет к другому состоянию:

{    "Гордость и предубеждение": "Алиса",    "Братья Карамазовы": "Пэт",    "Грозовой перевал": "Алиса"}

Реализация

Для словарей с очень небольшим количеством сопоставлений может иметь смысл реализовать словарь, используя список ассоциаций, а связанный список сопоставлений. В этой реализации время выполнения основных операций со словарем линейно зависит от общего числа отображений; однако его легко реализовать, и постоянные факторы времени его работы невелики.[1][8]

Другой очень простой метод реализации, который можно использовать, когда ключи ограничены узким диапазоном, - это прямая адресация в массив: значение для данного ключа k хранится в ячейке массива А[k], или если для k тогда в ячейке хранится специальный контрольное значение что указывает на отсутствие сопоставления. Этот метод не только прост, но и быстр: каждая операция со словарем занимает постоянное время. Однако пространство, необходимое для этой структуры, составляет размер всего пространства ключей, что делает ее непрактичной, если пространство ключей невелико.[4]

Два основных подхода к реализации словарей: хеш-таблица или дерево поиска.[1][2][4][5]

Реализации хеш-таблиц

Основная статья: Хеш-таблица
На этом графике сравнивается среднее количество Кэш процессора промахи, необходимые для поиска элементов в больших хэш-таблицах (намного превышающих размер кеша) с цепочкой и линейное зондирование. Линейное зондирование работает лучше благодаря лучшему местонахождение ссылки, хотя при заполнении таблицы ее производительность резко ухудшается.

Наиболее часто используемая реализация ассоциативного массива общего назначения с хеш-таблица: an массив в сочетании с хэш-функция который разделяет каждый ключ на отдельную «корзину» массива. Основная идея хеш-таблицы заключается в том, что доступ к элементу массива через его индекс является простой операцией с постоянным временем. Следовательно, средние накладные расходы операции для хеш-таблицы - это только вычисление хеш-кода ключа в сочетании с доступом к соответствующему сегменту в массиве. Таким образом, хеш-таблицы обычно работают за время O (1) и в большинстве ситуаций превосходят альтернативные варианты.

Хеш-таблицы должны уметь обрабатывать столкновения: когда хеш-функция отображает два разных ключа в одну и ту же корзину массива. Два наиболее распространенных подхода к этой проблеме: отдельная цепочка и открытая адресация.[1][2][4][9] В отдельной цепочке массив не хранит само значение, а хранит указатель в другой контейнер, обычно список ассоциаций, в котором хранятся все значения, соответствующие хешу. С другой стороны, при открытой адресации, если обнаруживается хеш-коллизия, таблица ищет пустое место в массиве для хранения значения детерминированным образом, обычно путем просмотра следующей непосредственной позиции в массиве.

Открытая адресация имеет более низкий промах в кеше соотношение, чем отдельные цепочки, когда таблица в основном пуста. Однако по мере того, как таблица заполняется большим количеством элементов, производительность открытой адресации падает экспоненциально. Кроме того, при раздельной цепочке в большинстве случаев используется меньше памяти, если только записи не очень маленькие (меньше четырехкратного размера указателя).

Реализации дерева

Основная статья: Дерево поиска

Самобалансирующиеся бинарные деревья поиска

Другой распространенный подход - реализовать ассоциативный массив с самобалансирующееся двоичное дерево поиска, например AVL дерево или красно-черное дерево.[10]

По сравнению с хеш-таблицами эти структуры имеют как преимущества, так и недостатки. В худшем случае производительность самобалансирующихся двоичных деревьев поиска значительно лучше, чем у хеш-таблицы, с временной сложностью в нотация большой O из O (журнал п). Это контрастирует с хэш-таблицами, производительность которых в худшем случае включает в себя все элементы, совместно использующие одну корзину, что приводит к O (п) временная сложность. Кроме того, как и все бинарные деревья поиска, самобалансирующиеся бинарные деревья поиска поддерживают порядок своих элементов. Таким образом, обход его элементов следует шаблону от наименьшего к наибольшему, тогда как обход хеш-таблицы может привести к тому, что элементы будут расположены в случайном порядке. Однако хеш-таблицы имеют гораздо лучшую временную сложность в среднем случае, чем самобалансирующиеся деревья двоичного поиска O (1), и их производительность в худшем случае очень маловероятна при хорошем хэш-функция используется.

Стоит отметить, что самобалансирующееся двоичное дерево поиска может использоваться для реализации сегментов для хэш-таблицы, которая использует отдельную цепочку. Это позволяет выполнять постоянный поиск в среднем случае, но обеспечивает производительность O (log п). Однако это вносит дополнительную сложность в реализацию и может привести к еще худшей производительности для небольших хэш-таблиц, где время, затрачиваемое на вставку и балансировку дерева, больше, чем время, необходимое для выполнения линейный поиск на всех элементах связанного списка или аналогичной структуры данных.[11][12]

Другие деревья

Ассоциативные массивы также могут храниться в несбалансированных деревья двоичного поиска или в структурах данных, специализированных для определенного типа ключей, таких как радиксные деревья, пытается, Джуди массивы, или деревья ван Эмде Боаса, хотя возможности этих методов реализации в сравнении с хэш-таблицами различаются; например, деревья Джуди по-прежнему работают с меньшей эффективностью, чем хэш-таблицы, в то время как тщательно отобранные хеш-таблицы обычно работают с большей эффективностью по сравнению с адаптивными основами системы счисления с потенциально большими ограничениями на типы данных, которые они могут обрабатывать.[13] Преимущества этих альтернативных структур заключаются в их способности обрабатывать операции, выходящие за рамки базовых операций ассоциативного массива, такие как поиск сопоставления, ключ которого является наиболее близким к запрошенному ключу, когда сам запрос отсутствует в наборе сопоставлений.

Сравнение

Базовая структура данныхИскатьВставкаУдалениеЗаказал
среднийхудший случайсреднийхудший случайсреднийхудший случай
Хеш-таблицаО (1)O (п)О (1)O (п)О (1)O (п)Нет
Самобалансирующееся двоичное дерево поискаO (журнал п)O (журнал п)O (журнал п)O (журнал п)O (журнал п)O (журнал п)да
неуравновешенный двоичное дерево поискаO (журнал п)O (п)O (журнал п)O (п)O (журнал п)O (п)да
Последовательный контейнер пары "ключ-значение"
(например. список ассоциаций )		O (п)O (п)О (1)О (1)O (п)O (п)Нет

Заказанный словарь

Базовое определение словаря не требует порядка. Чтобы гарантировать фиксированный порядок перечисления, часто используются упорядоченные версии ассоциативного массива. Упорядоченный словарь имеет два смысла:

  • Порядок перечисления всегда детерминирован для данного набора ключей путем сортировки. Это относится к реализациям на основе дерева, одним из представителей которых является <map> контейнер C ++.[14]
  • Порядок перечисления не зависит от ключа и вместо этого основан на порядке вставки. Так обстоит дело с «упорядоченным словарем» в .NET Framework и Python.[15][16]

Последний смысл упорядоченных словарей встречается чаще. Их можно реализовать с помощью список ассоциаций, или наложив двусвязный список поверх нормального словаря. Последний подход, который использовался CPython до версии 3.6, имеет то преимущество, что сохраняет потенциально лучшую сложность другой реализации.[17] CPython 3.6+ упорядочивает словари путем разделения хеш-таблицы на упорядоченный вставкой массив из k-v пар и разреженный массив («хеш-таблица») индексов.[18]

Языковая поддержка

Основная статья: Сравнение языков программирования (отображение)

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

Встроенная синтаксическая поддержка ассоциативных массивов была представлена ​​в 1969 г. СНОБОЛ4, под названием «таблица». TMG предлагает таблицы со строковыми ключами и целочисленными значениями. МАМПЫ сделаны многомерные ассоциативные массивы, опционально постоянные, его ключевые структуры данных. SETL поддержал их как одну из возможных реализаций наборов и карт. Большинство современных языков сценариев, начиная с AWK и в том числе Rexx, Perl, Tcl, JavaScript, Клен, Python, Рубин, Язык Wolfram Language, Идти, и Lua, поддерживают ассоциативные массивы в качестве основного типа контейнера. На многих других языках они доступны как библиотечные функции без специального синтаксиса.

В Болтовня, Цель-C, .СЕТЬ,[19] Python, REALbasic, Swift, VBA и Delphi[20] они называются словари; в Perl, Рубин и Семя7 они называются хеши; в C ++, Ява, Идти, Clojure, Scala, OCaml, Haskell они называются карты (увидеть карта (C ++), unordered_map (C ++), и карта); в Common Lisp и Windows PowerShell, они называются хеш-таблицы (поскольку оба обычно используют эту реализацию); в Клен и Lua они называются столы. В PHP, все массивы могут быть ассоциативными, за исключением того, что ключи ограничены целыми числами и строками. В JavaScript (см. Также JSON ) все объекты ведут себя как ассоциативные массивы со строковыми ключами, тогда как типы Map и WeakMap принимают произвольные объекты в качестве ключей. В Lua они используются как примитивный строительный блок для всех структур данных. В Visual FoxPro, они называются Коллекции. В Язык D также поддерживает ассоциативные массивы.[21]

Постоянное хранение

Основная статья: Хранилище "ключ-значение"

Многим программам, использующим ассоциативные массивы, в какой-то момент потребуется хранить эти данные в более постоянной форме, например, в компьютерный файл. Распространенным решением этой проблемы является обобщенная концепция, известная как архивирование или сериализация, который создает текстовое или двоичное представление исходных объектов, которое может быть записано непосредственно в файл. Чаще всего это реализуется в базовой объектной модели, такой как .Net или Cocoa, которая включает стандартные функции, преобразующие внутренние данные в текстовую форму. Программа может создать полное текстовое представление любой группы объектов, вызвав эти методы, которые почти всегда уже реализованы в базовом классе ассоциативных массивов.[22]

Для программ, использующих очень большие наборы данных, такое хранилище отдельных файлов не подходит, и система управления базами данных (DB) не требуется. Некоторые системы БД изначально хранят ассоциативные массивы, сериализуя данные, а затем сохраняя эти сериализованные данные и ключ. Затем отдельные массивы могут быть загружены или сохранены из базы данных с помощью ключа для ссылки на них. Эти хранилища "ключ-значение" использовались в течение многих лет и имеют такую ​​же долгую историю, как более распространенные реляционная база данных (RDB), но отсутствие стандартизации, среди прочего, ограничивало их использование определенными нишевыми ролями. Для этих ролей в большинстве случаев использовались RDB, хотя сохранение объектов в RDB может быть сложной задачей, известной как объектно-относительное рассогласование импеданса.

После c. 2010, потребность в высокопроизводительных базах данных, подходящих для облачные вычисления а более точное соответствие внутренней структуры программ, использующих их, привело к возрождению рынка магазинов «ключ-значение». Эти системы могут хранить и извлекать ассоциативные массивы естественным образом, что может значительно повысить производительность в обычных рабочих процессах, связанных с Интернетом.

Смотрите также

использованная литература

  1. ^ а б c d е ж Гудрич, Майкл Т.; Тамассия, Роберто (2006), «9.1 Тип абстрактных данных карты», Структуры данных и алгоритмы в Java (4-е изд.), Wiley, стр. 368–371.
  2. ^ а б c d е Мельхорн, Курт; Сандерс, Питер (2008), «4 хеш-таблицы и ассоциативные массивы», Алгоритмы и структуры данных: базовый набор инструментов (PDF), Springer, стр. 81–98.
  3. ^ Андерссон, Арне (1989). «Оптимальные границы в словарной задаче». Proc. Симпозиум по оптимальным алгоритмам. Конспект лекций по информатике. Springer Verlag. 401: 106–114. Дои:10.1007/3-540-51859-2_10. ISBN  978-3-540-51859-4.
  4. ^ а б c d Кормен, Томас Х.; Лейзерсон, Чарльз Э.; Ривест, Рональд Л.; Штейн, Клиффорд (2001), «11 хеш-таблиц», Введение в алгоритмы (2-е изд.), MIT Press и Макгроу-Хилл, стр. 221–252, ISBN  0-262-03293-7.
  5. ^ а б Дицфельбингер, М., Карлин, А., Мельхорн, К., Мейер-ауф-дер-Хайде, Ф., Ронерт, Х. и Тарьян, Р. Е. 1994.«Динамическое идеальное хеширование: верхняя и нижняя границы» В архиве 2016-03-04 в Wayback Machine.SIAM J. Comput. 23, 4 (август 1994 г.), 738-761.http://portal.acm.org/citation.cfm?id=182370Дои:10.1137 / S0097539791194094
  6. ^ Гудрич и Тамассия (2006) С. 597–599.
  7. ^ Гудрич и Тамассия (2006) С. 389–397.
  8. ^ «Когда мне следует использовать хеш-таблицу вместо списка ассоциаций?». lisp-faq / часть2. 1996-02-20.
  9. ^ Кламмер, Ф.; Маццолини, Л. (2006), «Следопыты ассоциативных карт», Ext. Рефераты ГИС-l 2006 г., ГИС-I, стр. 71–74..
  10. ^ Джоэл Адамс и Ларри Найхофф.«Деревья в СТЛ».Цитата: «Стандартная библиотека шаблонов ... некоторые из ее контейнеров - шаблоны set , map , multiset и multimap - обычно создаются с использованием особый вид самобалансирующееся двоичное дерево поиска называется красно-черное дерево."
  11. ^ Кнут, Дональд (1998). Искусство программирования. 3: Сортировка и поиск (2-е изд.). Эддисон-Уэсли. С. 513–558. ISBN  0-201-89685-0.
  12. ^ Пробст, Марк (30.04.2010). "Линейный поиск против двоичного". Получено 2016-11-20.
  13. ^ Альварес, Виктор; Рихтер, Стефан; Чен, Сяо; Диттрих, Йенс (апрель 2015 г.). «Сравнение адаптивных оснований системы счисления и хеш-таблиц». 2015 31-я Международная конференция по инженерии данных IEEE. Сеул, Южная Корея: IEEE: 1227–1238. Дои:10.1109 / ICDE.2015.7113370. ISBN  978-1-4799-7964-6. S2CID  17170456.
  14. ^ "std :: map". en.cppreference.com.
  15. ^ "Класс OrderedDictionary (System.Collections.Specialized)". Документы MS.
  16. ^ "коллекции - Типы данных контейнеров - Документация Python 3.9.0a3". docs.python.org.
  17. ^ Димитрис Фасаракис Хиллиард. "словарь - как Python OrderedDict запоминает вставленные элементы?". Переполнение стека.
  18. ^ Димитрис Фасаракис Хиллиард. "Словари заказаны в Python 3.6+?". Переполнение стека.
  19. ^ "Класс Dictionary ". MSDN.
  20. ^ "System.Generics.Collections.TDictionary - RAD Studio API Documentation". docwiki.embarcadero.com. Получено 2017-04-18.
  21. ^ «Ассоциативные массивы, язык программирования D». Цифровой Марс.
  22. ^ "Руководство по программированию архивов и сериализаций", Apple Inc., 2012 г.

внешние ссылки