В информатике ассоциативный массив , карта , таблица символов или словарь — это абстрактный тип данных , который хранит коллекцию пар (ключ, значение) , так что каждый возможный ключ появляется в коллекции не более одного раза. В математических терминах ассоциативный массив — это функция с конечным доменом . [ 1] Он поддерживает операции «поиск», «удаление» и «вставка».
Задача о словаре — это классическая задача проектирования эффективных структур данных , реализующих ассоциативные массивы. [2] Двумя основными решениями задачи о словаре являются хэш-таблицы и деревья поиска . [3] [4] [5] [6] Иногда также возможно решить задачу, используя напрямую адресуемые массивы , двоичные деревья поиска или другие более специализированные структуры.
Многие языки программирования включают ассоциативные массивы как примитивные типы данных , в то время как многие другие языки предоставляют библиотеки программного обеспечения , которые поддерживают ассоциативные массивы. Содержимое адресуемой памяти является формой прямой аппаратной поддержки ассоциативных массивов.
Ассоциативные массивы имеют множество приложений, включая такие фундаментальные шаблоны программирования , как мемоизация и шаблон декоратора . [7]
Название не происходит от ассоциативного свойства, известного в математике. Скорее, оно возникает из ассоциации значений с ключами. Его не следует путать с ассоциативными процессорами .
В ассоциативном массиве связь между ключом и значением часто называется «сопоставлением»; это же слово может также использоваться для обозначения процесса создания новой ассоциации.
Операции, которые обычно определяются для ассоциативного массива: [3] [4] [8]
Ассоциативные массивы могут также включать другие операции, такие как определение количества отображений или построение итератора для цикла по всем отображениям. Для таких операций порядок, в котором возвращаются отображения, обычно определяется реализацией.
Мультикарта обобщает ассоциативный массив, позволяя связывать несколько значений с одним ключом. [9] Двунаправленная карта — это связанный абстрактный тип данных, в котором сопоставления работают в обоих направлениях: каждое значение должно быть связано с уникальным ключом, а вторая операция поиска принимает значение в качестве аргумента и ищет ключ, связанный с этим значением.
Операции ассоциативного массива должны удовлетворять различным свойствам: [8]
lookup(k, insert(j, v, D)) = if k == j then v else lookup(k, D)lookup(k, new()) = fail, где fail— исключение или значение по умолчаниюremove(k, insert(j, v, D)) = if k == j then remove(k, D) else insert(j, v, remove(k, D))remove(k, new()) = new()где kи jявляются ключами, v— значением, D— ассоциативный массив, а new()создает новый, пустой ассоциативный массив.
Предположим, что набор выданных библиотекой книг представлен в структуре данных. Каждая книга в библиотеке может быть выдана одним читателем за раз. Однако один читатель может выдать несколько книг. Таким образом, информация о том, какие книги выданы каким читателям, может быть представлена ассоциативным массивом, в котором книги являются ключами, а читатели — значениями. Используя нотацию Python или JSON , структура данных будет выглядеть следующим образом:
{ "Гордость и предубеждение" : "Алиса" , "Грозовой перевал" : "Алиса" , "Большие надежды" : "Джон" } Операция поиска по ключу "Great Expectations" вернет "John". Если Джон вернет свою книгу, это вызовет операцию удаления, а если Пэт извлечет книгу, это вызовет операцию вставки, что приведет к другому состоянию:
{ "Гордость и предубеждение" : "Алиса" , "Братья Карамазовы" : "Пэт" , "Грозовой перевал" : "Алиса" } Для словарей с очень небольшим количеством отображений может иметь смысл реализовать словарь с использованием списка ассоциаций , который является связанным списком отображений. При такой реализации время выполнения основных операций словаря линейно зависит от общего числа отображений. Однако его легко реализовать, а постоянные факторы во времени его выполнения малы. [3] [10]
Другой очень простой метод реализации, применимый, когда ключи ограничены узким диапазоном, — это прямая адресация в массив: значение для заданного ключа k сохраняется в ячейке массива A [ k ], или, если для k нет сопоставления , то ячейка сохраняет специальное контрольное значение , которое указывает на отсутствие сопоставления. Этот метод прост и быстр, при этом каждая операция со словарем занимает постоянное время. Однако требование к пространству для этой структуры равно размеру всего пространства ключей, что делает его непрактичным, если только пространство ключей не мало. [5]
Два основных подхода к реализации словарей — это хэш-таблица и дерево поиска . [3] [4] [5] [6]
Наиболее часто используемая универсальная реализация ассоциативного массива — это хэш-таблица : массив , объединенный с хэш-функцией , которая разделяет каждый ключ на отдельный «корзину» массива. Основная идея хэш-таблицы заключается в том, что доступ к элементу массива через его индекс — это простая операция с постоянным временем. Поэтому средние накладные расходы на операцию для хэш-таблицы — это только вычисление хеша ключа в сочетании с доступом к соответствующей корзине в массиве. Таким образом, хэш-таблицы обычно выполняются за время O(1) и обычно превосходят альтернативные реализации.
Хэш-таблицы должны уметь обрабатывать коллизии : отображение хэш-функцией двух разных ключей в один и тот же контейнер массива. Два наиболее распространенных подхода к этой проблеме — раздельное связывание и открытая адресация . [3] [4] [5] [11] При раздельном связывании массив не хранит само значение, а хранит указатель на другой контейнер, обычно список ассоциаций , который хранит все значения, соответствующие хешу. Напротив, при открытой адресации, если обнаруживается коллизия хеша, таблица ищет пустое место в массиве для сохранения значения детерминированным образом, обычно путем просмотра следующей непосредственной позиции в массиве.
Открытая адресация имеет более низкий коэффициент промахов кэша , чем раздельная цепочка, когда таблица в основном пуста. Однако по мере заполнения таблицы большим количеством элементов производительность открытой адресации экспоненциально ухудшается. Кроме того, раздельная цепочка использует меньше памяти в большинстве случаев, если только записи не очень малы (менее четырехкратного размера указателя).
Другим распространенным подходом является реализация ассоциативного массива с самобалансирующимся бинарным деревом поиска , таким как дерево AVL или красно-черное дерево . [12]
По сравнению с хэш-таблицами эти структуры имеют как сильные, так и слабые стороны. Худшая производительность самобалансирующихся бинарных деревьев поиска значительно лучше, чем у хэш-таблицы, с временной сложностью в нотации big O O(log n ). Это контрастирует с хэш-таблицами, чья худшая производительность подразумевает, что все элементы совместно используют один контейнер, что приводит к временной сложности O( n ). Кроме того, как и все бинарные деревья поиска, самобалансирующиеся бинарные деревья поиска сохраняют порядок своих элементов. Таким образом, обход ее элементов следует шаблону от наименьшего к наибольшему, тогда как обход хэш-таблицы может привести к элементам, находящимся в, казалось бы, случайном порядке. Поскольку они упорядочены, карты на основе деревьев также могут удовлетворять запросам диапазона (находить все значения между двумя границами), тогда как хэш-карта может находить только точные значения. Однако хэш-таблицы имеют гораздо лучшую среднюю временную сложность, чем самобалансирующиеся бинарные деревья поиска O(1), и их худшая производительность крайне маловероятна при использовании хорошей хэш-функции .
Самобалансирующееся бинарное дерево поиска может быть использовано для реализации сегментов для хэш-таблицы, которая использует раздельное связывание. Это позволяет выполнять поиск констант в среднем случае, но гарантирует производительность в худшем случае O(log n ). Однако это вносит дополнительную сложность в реализацию и может привести к еще более низкой производительности для меньших хэш-таблиц, где время, затрачиваемое на вставку и балансировку дерева, больше времени, необходимого для выполнения линейного поиска по всем элементам связанного списка или аналогичной структуры данных. [13] [14]
Ассоциативные массивы также могут храниться в несбалансированных бинарных деревьях поиска или в структурах данных, специализированных для определенного типа ключей, таких как radix trees , trys , Judy arrays или van Emde Boas trees , хотя относительная производительность этих реализаций различается. Например, было обнаружено, что деревья Judy работают менее эффективно, чем хэш-таблицы, в то время как тщательно отобранные хэш-таблицы, как правило, работают эффективнее, чем адаптивные radix trees, с потенциально большими ограничениями на типы данных, которые они могут обрабатывать. [15] Преимущества этих альтернативных структур заключаются в их способности обрабатывать дополнительные операции с ассоциативными массивами, такие как поиск сопоставления, ключ которого находится ближе всего к запрашиваемому ключу, когда запрос отсутствует в наборе сопоставлений.
Базовое определение словаря не требует порядка. Чтобы гарантировать фиксированный порядок перечисления, часто используются упорядоченные версии ассоциативного массива. Существует два смысла упорядоченного словаря:
<map>контейнер C++. [16]Последнее более распространено. Такие упорядоченные словари могут быть реализованы с использованием списка ассоциаций , путем наложения двусвязного списка поверх обычного словаря или путем перемещения фактических данных из разреженного (неупорядоченного) массива в плотный, упорядоченный вставкой.
Ассоциативные массивы могут быть реализованы в любом языке программирования как пакет, и многие языковые системы предоставляют их как часть своей стандартной библиотеки. В некоторых языках они не только встроены в стандартную систему, но и имеют специальный синтаксис, часто использующий индексацию, подобную массиву.
Встроенная синтаксическая поддержка ассоциативных массивов была представлена в 1969 году SNOBOL4 под названием «table». TMG предлагал таблицы со строковыми ключами и целочисленными значениями. MUMPS сделал многомерные ассоциативные массивы, опционально постоянные, своей ключевой структурой данных. SETL поддерживал их как одну из возможных реализаций множеств и карт. Большинство современных языков сценариев, начиная с AWK и включая Rexx , Perl , PHP , Tcl , JavaScript , Maple , Python , Ruby , Wolfram Language , Go и Lua , поддерживают ассоциативные массивы как основной тип контейнера. Во многих других языках они доступны как библиотечные функции без специального синтаксиса.
В Smalltalk , Objective-C , .NET , [20] Python , REALbasic , Swift , VBA и Delphi [21] они называются словарями ; в Perl , Ruby и Seed7 они называются хэшами ; в C++ , C# , Java , Go , Clojure , Scala , OCaml , Haskell они называются картами (см. map (C++) , unordered_map (C++) и Map); в Common Lisp и Windows PowerShell они называются хэш-таблицами (так как оба обычно используют эту реализацию); в Maple и Lua они называются таблицами . В PHP все массивы могут быть ассоциативными, за исключением того, что ключи ограничены целыми числами и строками. В JavaScript (см. также JSON ) все объекты ведут себя как ассоциативные массивы со строковыми ключами, в то время как типы Map и WeakMap принимают произвольные объекты в качестве ключей. В Lua они используются как примитивный строительный блок для всех структур данных. В Visual FoxPro они называются Collections . Язык D также поддерживает ассоциативные массивы. [22]
Многим программам, использующим ассоциативные массивы, необходимо будет хранить эти данные в более постоянной форме, например, в компьютерном файле . Распространенным решением этой проблемы является обобщенная концепция, известная как архивирование или сериализация , которая создает текстовое или двоичное представление исходных объектов, которое может быть записано непосредственно в файл. Это чаще всего реализуется в базовой объектной модели, такой как .Net или Cocoa, которая включает стандартные функции, преобразующие внутренние данные в текст. Программа может создать полное текстовое представление любой группы объектов, вызывая эти методы, которые почти всегда уже реализованы в базовом классе ассоциативного массива. [23]
Для программ, использующих очень большие наборы данных, такой тип индивидуального хранения файлов не подходит, и требуется система управления базами данных (СУБД). Некоторые системы СУБД изначально хранят ассоциативные массивы, сериализуя данные и затем сохраняя эти сериализованные данные и ключ. Затем отдельные массивы можно загрузить или сохранить из базы данных, используя ключ для ссылки на них. Эти хранилища ключей и значений используются уже много лет и имеют такую же долгую историю, как и более распространенные реляционные базы данных (РБД), но отсутствие стандартизации, среди прочих причин, ограничило их использование определенными нишевыми ролями. РБД использовались для этих ролей в большинстве случаев, хотя сохранение объектов в РБД может быть сложным, проблема, известная как несоответствие объектно-реляционного импеданса .
Примерно после 2010 года потребность в высокопроизводительных базах данных, подходящих для облачных вычислений и более точно соответствующих внутренней структуре программ, их использующих, привела к ренессансу на рынке хранилищ ключей и значений. Эти системы могут хранить и извлекать ассоциативные массивы в нативной манере, что может значительно повысить производительность в общих рабочих процессах, связанных с вебом.
