В компьютерной науке , в ассоциативном массиве , карты , таблицы символов или словаря является абстрактным типом данных состоит из коллекции из (ключ, значение) пар , таким образом, что каждый из возможных ключевых появляется в самый раз в коллекции.
Операции, связанные с этим типом данных, позволяют: [1] [2]
- добавление пары в коллекцию;
- снятие пары из коллекции;
- модификация существующей пары;
- поиск значения, связанного с конкретным ключом.
Реализация ассоциативных массивов ставит проблему словаря , классическую проблему информатики: задачу проектирования структуры данных, которая поддерживает набор данных во время операций «поиска», «удаления» и «вставки». [3] Двумя основными решениями проблемы словаря являются хеш-таблица и дерево поиска . [1] [2] [4] [5] В некоторых случаях также возможно решить проблему, используя массивы с прямой адресацией , бинарные деревья поиска или другие более специализированные структуры.
Многие языки программирования включают ассоциативные массивы в качестве примитивных типов данных , и они доступны в программных библиотеках для многих других. Память с адресацией по содержимому - это форма прямой аппаратной поддержки ассоциативных массивов.
У ассоциативных массивов есть множество приложений, включая такие фундаментальные шаблоны программирования, как мемоизация и шаблон декоратора . [6]
Название происходит не от ассоциативного свойства, известного в математике. Скорее, это происходит из-за того, что мы связываем значения с ключами.
Операции [ править ]
В ассоциативном массиве связь между ключом и значением часто называется «отображением», и такое же сопоставление слов может также использоваться для обозначения процесса создания новой связи.
Для ассоциативного массива обычно определяются следующие операции: [1] [2]
- Добавить или вставить : добавить новую пару в коллекцию, сопоставив новый ключ с его новым значением. Аргументами этой операции являются ключ и значение.
- Переназначить : заменить значение в одной из пар, которые уже есть в коллекции, сопоставив существующий ключ новому значению. Как и при вставке, аргументами этой операции являются ключ и значение.
- Удалить или удалить : удалить пару из коллекции, отключив данный ключ от его значения. Аргумент этой операции - ключ.
- Поиск : найдите значение (если есть), связанное с данным ключом. Аргументом этой операции является ключ, а значение возвращается из операции. Если значение не найдено, некоторые реализации ассоциативного массива вызывают исключение , в то время как другие создают пару с заданным ключом и значением по умолчанию для типа значения (ноль, пустой контейнер ...).
Часто вместо добавления или переназначения используется одна операция набора, которая добавляет новую пару, если она еще не существует, и в противном случае переназначает ее.
Кроме того, ассоциативные массивы могут также включать в себя другие операции, такие как определение количества отображений или построение итератора для перебора всех отображений. Обычно для такой операции порядок, в котором возвращаются сопоставления, может определяться реализацией.
MultiMap обобщает ассоциативный массив, позволяя несколько значений , которые будут связаны с одним ключом. [7] двунаправленная карта является связанным типом абстрактного данных , в котором отображения работают в обоих направлениях: каждое значение должно быть связанно с уникальным ключом, а вторая операция поиска принимает значение в качестве аргумента и смотрит на ключе , связанный с этим ценить.
Пример [ править ]
Предположим, что набор кредитов, выданных библиотекой, представлен в структуре данных. Каждую книгу в библиотеке может извлекать только один посетитель библиотеки одновременно. Однако один посетитель может просмотреть несколько книг. Таким образом, информация о том, какие книги проверены для каких посетителей, может быть представлена ассоциативным массивом, в котором книги являются ключами, а посетители - значениями. Используя нотацию Python или JSON , структура данных будет следующей:
{ «Гордость и предубеждение» : «Алиса» , «Грозовой перевал» : «Алиса» , «Большие надежды» : «Джон» }Операция поиска по ключу «Большие надежды» вернет «Джон». Если Джон вернет свою книгу, это вызовет операцию удаления, а если Пэт извлечет книгу, это вызовет операцию вставки, ведущую к другому состоянию:
{ «Гордость и предубеждение» : «Алиса» , «Братья Карамазовы» : «Пэт» , «Грозовой перевал» : «Алиса» }Реализация [ править ]
Для словарей с очень небольшим количеством сопоставлений может иметь смысл реализовать словарь с использованием списка ассоциаций , связанного списка сопоставлений. В этой реализации время выполнения основных словарных операций линейно зависит от общего количества отображений; однако его легко реализовать, а постоянные факторы времени его работы невелики. [1] [8]
Другой очень простой метод реализации, который можно использовать, когда ключи ограничены узким диапазоном, является прямая адресация в массив: значение для данного ключа k сохраняется в ячейке массива A [ k ], или если нет сопоставления для k тогда в ячейке хранится специальное контрольное значение , указывающее на отсутствие сопоставления. Этот метод не только прост, но и быстр: каждая операция со словарем занимает постоянное время. Однако пространство, необходимое для этой структуры, составляет размер всего пространства ключей, что делает ее непрактичной, если пространство ключей невелико. [4]
Двумя основными подходами к реализации словарей являются хэш-таблица или дерево поиска . [1] [2] [4] [5]
Реализации хеш-таблиц [ править ]
Наиболее часто используемая реализация ассоциативного массива общего назначения - это хеш-таблица : массив, объединенный с хеш-функцией, которая разделяет каждый ключ на отдельную «корзину» массива. Основная идея хеш-таблицы заключается в том, что доступ к элементу массива через его индекс является простой операцией с постоянным временем. Следовательно, средние накладные расходы на операцию для хеш-таблицы - это только вычисление хеш-кода ключа в сочетании с доступом к соответствующему сегменту в массиве. Таким образом, хеш-таблицы обычно работают за время O (1) и в большинстве ситуаций превосходят альтернативные варианты.
Хеш-таблицы должны иметь возможность обрабатывать коллизии : когда хеш-функция сопоставляет два разных ключа одному и тому же сегменту массива. Двумя наиболее распространенными подходами к этой проблеме являются раздельное связывание и открытая адресация . [1] [2] [4] [9] При отдельной цепочке массив не хранит само значение, а хранит указатель на другой контейнер, обычно это список ассоциаций , в котором хранятся все значения, соответствующие хешу. С другой стороны, при открытой адресации, если обнаруживается хеш-коллизия, таблица ищет пустое место в массиве для хранения значения детерминированным образом, обычно просматривая следующую непосредственную позицию в массиве.
Открытая адресация имеет более низкий коэффициент промахов кэша, чем отдельная цепочка, когда таблица в основном пуста. Однако по мере того, как таблица заполняется большим количеством элементов, производительность открытой адресации падает в геометрической прогрессии. Кроме того, при раздельной цепочке в большинстве случаев используется меньше памяти, если только записи не очень маленькие (меньше четырехкратного размера указателя).
Реализации дерева [ править ]
Самобалансирующиеся деревья двоичного поиска [ править ]
Другой распространенный подход - реализовать ассоциативный массив с самобалансирующимся двоичным деревом поиска , таким как дерево AVL или красно-черное дерево . [10]
По сравнению с хеш-таблицами эти структуры имеют как преимущества, так и недостатки. В худшем случае производительность самобалансирующихся двоичных деревьев поиска значительно лучше, чем у хеш-таблицы, с временной сложностью в нотации O, равной O (log n ). Это контрастирует с хэш-таблицами, производительность которых в наихудшем случае включает в себя все элементы, совместно использующие одну корзину, в результате чего O ( n) временная сложность. Кроме того, как и все бинарные деревья поиска, самобалансирующиеся бинарные деревья поиска поддерживают порядок своих элементов. Таким образом, обход его элементов следует шаблону от наименьшего к наибольшему, тогда как обход хеш-таблицы может привести к тому, что элементы будут расположены в случайном порядке. Однако хеш-таблицы имеют гораздо лучшую временную сложность в среднем случае, чем самобалансирующиеся двоичные деревья поиска O (1), и их производительность в худшем случае очень маловероятна при использовании хорошей хеш-функции .
Стоит отметить, что самобалансирующееся двоичное дерево поиска может использоваться для реализации сегментов для хэш-таблицы, которая использует отдельную цепочку. Это позволяет выполнять поиск констант в среднем случае, но обеспечивает производительность O (log n ) в наихудшем случае . Однако это вносит дополнительную сложность в реализацию и может привести к еще худшей производительности для небольших хэш-таблиц, где время, затрачиваемое на вставку и балансировку дерева, больше, чем время, необходимое для выполнения линейного поиска по всем элементам связанного список или аналогичная структура данных. [11] [12]
Другие деревья [ править ]
Ассоциативные массивы также могут храниться в несбалансированных двоичных деревьях поиска или в структурах данных, специализированных для определенного типа ключей, таких как деревья счисления , попытки , массивы Джуди или деревья Ван Эмде Боаса , хотя возможность этих методов реализации в сравнении с хэш-таблицами варьируется; например, деревья Джуди по-прежнему работают с меньшей эффективностью, чем хэш-таблицы, в то время как тщательно отобранные хеш-таблицы обычно работают с большей эффективностью по сравнению с адаптивными основами системы счисления с потенциально большими ограничениями на типы данных, которые они могут обрабатывать. [13] Преимущества этих альтернативных структур проистекают из их способности обрабатывать операции, выходящие за рамки базовых операций ассоциативного массива, такие как поиск сопоставления, ключ которого является ближайшим к запрошенному ключу, когда сам запрос отсутствует в наборе сопоставлений.
Сравнение [ править ]
| Базовая структура данных | Искать | Вставка | Удаление | Упорядоченный | |||
|---|---|---|---|---|---|---|---|
| средний | худший случай | средний | худший случай | средний | худший случай | ||
| Хеш-таблица | О (1) | О ( п ) | О (1) | О ( п ) | О (1) | О ( п ) | Нет |
| Самобалансирующееся двоичное дерево поиска | O (журнал n ) | O (журнал n ) | O (журнал n ) | O (журнал n ) | O (журнал n ) | O (журнал n ) | да |
| несбалансированное двоичное дерево поиска | O (журнал n ) | О ( п ) | O (журнал n ) | О ( п ) | O (журнал n ) | О ( п ) | да |
| Последовательный контейнер пар ключ-значение (например, список ассоциаций ) | О ( п ) | О ( п ) | О (1) | О (1) | О ( п ) | О ( п ) | Нет |
Упорядоченный словарь [ править ]
Базовое определение словаря не требует порядка. Чтобы гарантировать фиксированный порядок перечисления, часто используются упорядоченные версии ассоциативного массива. Упорядоченный словарь имеет два смысла:
- Порядок перечисления всегда детерминирован для данного набора ключей путем сортировки. Так обстоит дело с реализациями на основе дерева, одним из представителей которых является
<map>контейнер C ++. [14] - Порядок перечисления не зависит от ключа и основан на порядке вставки. Так обстоит дело с «упорядоченным словарем» в .NET Framework и Python . [15] [16]
Чаще встречается последний смысл упорядоченных словарей. Они могут быть реализованы с использованием списка ассоциаций или путем наложения двусвязного списка поверх обычного словаря. Последний подход, который использовался CPython до версии 3.6, имеет преимущество в том, что сохраняет потенциально лучшую сложность другой реализации. [17] CPython 3.6+ упорядочивает словари, разделяя хеш-таблицу на упорядоченный вставкой массив пар kv и разреженный массив («хеш-таблица») индексов. [18]
Языковая поддержка [ править ]
Ассоциативные массивы могут быть реализованы на любом языке программирования в виде пакета, и многие языковые системы предоставляют их как часть своей стандартной библиотеки. В некоторых языках они не только встроены в стандартную систему, но и имеют специальный синтаксис, часто использующий индексы типа массивов.
Встроенная синтаксическая поддержка ассоциативных массивов была введена в 1969 году компанией SNOBOL4 под названием «таблица». TMG предлагает таблицы со строковыми ключами и целочисленными значениями. MUMPS создал многомерные ассоциативные массивы, опционально постоянные, для своей ключевой структуры данных. SETL поддерживал их как одну из возможных реализаций наборов и карт. Большинство современных языков сценариев, начиная с AWK и включая Rexx , Perl , PHP , Tcl , JavaScript , Maple , Python , Ruby , Wolfram Language ,Go и Lua поддерживают ассоциативные массивы в качестве основного типа контейнера. На многих других языках они доступны как библиотечные функции без специального синтаксиса.
В Smalltalk , Objective-C , .NET , [19] Python , REALbasic , Swift , VBA и Delphi [20] они называются словарями ; в Perl , Ruby и Seed7 они называются хешами ; в C ++ , Java , Go , Clojure , Scala , OCaml , Haskell они называются картами (см. карту (C ++) ,unordered_map (C ++) и Map); в Common Lisp и Windows PowerShell они называются хэш-таблицами (поскольку обе обычно используют эту реализацию); в Maple и Lua они называются таблицами . В PHP все массивы могут быть ассоциативными, за исключением того, что ключи ограничены целыми числами и строками. В JavaScript (см. Также JSON ) все объекты ведут себя как ассоциативные массивы со строковыми ключами, в то время как типы Map и WeakMap принимают произвольные объекты в качестве ключей. В Lua они используются как примитивный строительный блок для всех структур данных. В Visual FoxPro они называются Коллекциями . ВВ языке D также есть поддержка ассоциативных массивов. [21]
Постоянное хранилище [ править ]
Многим программам, использующим ассоциативные массивы, в какой-то момент потребуется сохранить эти данные в более постоянной форме, например, в компьютерном файле . Распространенным решением этой проблемы является обобщенная концепция, известная как архивирование или сериализация , которая создает текстовое или двоичное представление исходных объектов, которые могут быть записаны непосредственно в файл. Чаще всего это реализуется в базовой объектной модели, такой как .Net или Cocoa, которая включает стандартные функции, преобразующие внутренние данные в текстовую форму. Программа может создать полное текстовое представление любой группы объектов, вызвав эти методы, которые почти всегда уже реализованы в базовом классе ассоциативных массивов. [22]
Для программ, использующих очень большие наборы данных, такое хранилище отдельных файлов не подходит, и требуется система управления базами данных (БД). Некоторые системы БД изначально хранят ассоциативные массивы, сериализуя данные, а затем сохраняя эти сериализованные данные и ключ. Затем отдельные массивы могут быть загружены или сохранены из базы данных с помощью ключа для ссылки на них. Эти хранилища «ключ-значение» использовались в течение многих лет и имеют такую же долгую историю, как и более распространенные реляционные базы данных (RDB), но отсутствие стандартизации, среди других причин, ограничивало их использование определенными нишевыми ролями. В большинстве случаев для этих ролей использовались РБД, хотя сохранение объектов в РБД может быть сложной задачей, известной как несоответствие объектно-реляционного импеданса..
После c. В 2010 году потребность в высокопроизводительных базах данных, подходящих для облачных вычислений и более точно соответствующих внутренней структуре программ, использующих их, привела к возрождению рынка хранилищ ключей и значений. Эти системы могут хранить и извлекать ассоциативные массивы естественным образом, что может значительно повысить производительность в общих рабочих процессах, связанных с Интернетом.
См. Также [ править ]
- База данных "ключ-значение"
- Кортеж
- Функция (математика)
- JSON
Ссылки [ править ]
- ^ a b c d e е Гудрич, Майкл Т .; Тамассия, Роберто (2006), «9.1 Тип абстрактных данных карты», Структуры данных и алгоритмы в Java (4-е изд.), Wiley, стр. 368–371
- ^ a b c d e Мельхорн, Курт ; Сандерс, Питер (2008), «4 хэш-таблицы и ассоциативные массивы», алгоритмы и структуры данных: The Basic Toolbox (PDF) , Springer, стр. 81–98.
- ^ Андерссон, Арне (1989). «Оптимальные границы на словарной задаче». Proc. Симпозиум по оптимальным алгоритмам . Конспект лекций по информатике. Springer Verlag. 401 : 106–114. DOI : 10.1007 / 3-540-51859-2_10 . ISBN 978-3-540-51859-4.
- ^ a b c d Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стейн, Клиффорд (2001), «11 хэш-таблиц», Введение в алгоритмы (2-е изд.), MIT Press и McGraw-Hill , стр. 221–252, ISBN 0-262-03293-7.
- ^ a b Дитцфельбингер, М., Карлин, А., Мельхорн, К., Мейер-ауф-дер-Хайде, Ф., Ронерт, Х. и Тарджан, RE 1994. «Динамическое идеальное хеширование: верхние и нижние границы» Архивировано 2016 г. 03-04 у Wayback Machine . SIAM J. Comput. 23, 4 (август 1994 г.), 738-761. http://portal.acm.org/citation.cfm?id=182370 doi : 10.1137 / S0097539791194094
- ^ Goodrich & Tamassia (2006) , стр. 597-599.
- ^ Goodrich & Tamassia (2006) , стр. 389-397.
- ^ "Когда мне следует использовать хеш-таблицу вместо списка ассоциаций?" . lisp-faq / часть2. 1996-02-20.
- ^ Кламмер, Ф .; Маццолини, Л. (2006), "Следопыты ассоциативных карт", Ext. Аннотации ГИС-1 2006 , ГИС-I, стр. 71–74.
- ^ Джоэл Адамс и Ларри Найхофф. «Деревья в STL» . Цитата: «Стандартная библиотека шаблонов ... некоторые из ее контейнеров - шаблоны set <T>, map <T1, T2>, multiset <T> и multimap <T1, T2> - обычно создаются с использованием специальных своего рода самобалансирующееся двоичное дерево поиска, называемое красно-черным деревом ».
- ^ Кнут, Дональд (1998). Искусство программирования . 3: Сортировка и поиск (2-е изд.). Эддисон-Уэсли. С. 513–558. ISBN 0-201-89685-0.
- ^ Пробст, Марк (30.04.2010). «Линейный поиск против двоичного» . Проверено 20 ноября 2016 .
- ^ Альварес, Виктор; Рихтер, Стефан; Чен, Сяо; Диттрих, Йенс (апрель 2015 г.). «Сравнение адаптивных оснований системы счисления и хеш-таблиц». 2015 IEEE 31-я Международная конференция по инженерии данных . Сеул, Южная Корея: IEEE: 1227–1238. DOI : 10.1109 / ICDE.2015.7113370 . ISBN 978-1-4799-7964-6. S2CID 17170456 .
- ^ "std :: map" . en.cppreference.com .
- ^ "Класс OrderedDictionary (System.Collections.Specialized)" . MS Docs .
- ^ "коллекции - Типы данных контейнеров - Документация Python 3.9.0a3" . docs.python.org .
- ^ Димитрис Фасаракис Хиллиард. "словарь - как Python OrderedDict запоминает вставленные элементы?" . Переполнение стека .
- ^ Димитрис Фасаракис Хиллиард. "Словари заказаны в Python 3.6+?" . Переполнение стека .
- ^ "Dictionary <TKey, TValue> Class" . MSDN.
- ^ "System.Generics.Collections.TDictionary - RAD Studio API Documentation" . docwiki.embarcadero.com . Проверено 18 апреля 2017 .
- ^ "Ассоциативные массивы, язык программирования D" . Цифровой Марс.
- ^ "Руководство по программированию архивов и сериализации" , Apple Inc., 2012
Внешние ссылки [ править ]
 | Поищите ассоциативный массив в Викисловаре, бесплатном словаре. |
- Словарь алгоритмов и структур данных NIST: ассоциативный массив
