Войти
В информатике, ассоциативный массив, карта, таблица символов или словарь - это абстрактный тип данных, состоящий из коллекции из (ключ, значение) пар, так что каждый возможный ключ появляется в коллекции не более одного раза.
Операции, связанные с этим типом данных, позволяют:
. Реализация ассоциативных массивов ставит проблему словаря, классическую проблему информатики: задачу проектирования структуры данных , который поддерживает набор данных во время операций «поиска», «удаления» и «вставки». Двумя основными решениями проблемы словаря являются хэш-таблица или дерево поиска. В некоторых случаях также возможно решить проблему, используя непосредственно адресуемые массивы , двоичные деревья поиска или другие более специализированные структуры.
Многие языки программирования включают ассоциативные массивы как примитивные типы данных, и они доступны в программных библиотеках для многих других. Память с адресацией по содержимому - это форма прямой аппаратной поддержки ассоциативных массивов.
У ассоциативных массивов есть много приложений, включая такие фундаментальные шаблоны программирования, как memoization и шаблон декоратора.
. Имя не происходит от ассоциативное свойство, известное в математике. Скорее, это происходит из-за того, что мы связываем значения с ключами.
В ассоциативном массиве связь между ключом и значением часто называется «отображением», и такое же сопоставление слов также может использоваться для обозначения процесса создания новой связи.
Операции, которые обычно определяются для ассоциативного массива:
к коллекции, сопоставляя новый ключ с его новым значением. Аргументами этой операции являются ключ и значение.пары, которые уже находятся в коллекции, отображая существующий ключ на новое значение. Как и при вставке, аргументами этой операции являются ключ и значение.из коллекции, отменяя сопоставление данного ключа с его значением. Аргументом этой операции является ключ.Часто вместо добавления или переназначения используется одна операция set, которая добавляет новую пару
Кроме того, ассоциативные массивы могут также включать в себя другие операции, такие как определение количества отображений или построение итератора для перебора всех отображений. Обычно для такой операции порядок, в котором возвращаются сопоставления, может быть определен реализацией.
A multimap обобщает ассоциативный массив, позволяя связывать несколько значений с одним ключом. двунаправленная карта - это связанный абстрактный тип данных, в котором сопоставления работают в обоих направлениях: каждое значение должно быть связано с уникальным ключом, а вторая операция поиска принимает значение в качестве аргумента и ищет ключ связанный с этим значением.
Предположим, что набор кредитов, предоставленных библиотекой, представлен в структуре данных. Каждую книгу в библиотеке может проверять только один посетитель библиотеки одновременно. Однако один посетитель может проверить несколько книг. Таким образом, информация о том, какие книги проверены и для каких посетителей, может быть представлена ассоциативным массивом, в котором книги являются ключами, а посетители - значениями. Используя нотацию из Python или JSON, структура данных будет следующей:
{«Гордость и предубеждение»: «Алиса», «Грозовой перевал»: «Алиса», «Великий Expectations ":" John "}Операция поиска по ключу" Great Expectations "вернет" John ". Если Джон вернет свою книгу, это вызовет операцию удаления, а если Пэт извлечет книгу, это вызовет операцию вставки, ведущую к другому состоянию:
{"Гордость и предубеждение": "Алиса", " Братья Карамазовы »:« Пэт »,« Грозовой перевал »:« Алиса »}Для словарей с очень небольшим количеством сопоставлений может иметь смысл реализовать словарь с использованием ассоциации list, связанный список отображений. В этой реализации время выполнения основных словарных операций линейно зависит от общего числа отображений; однако его легко реализовать, а постоянные факторы во время его работы невелики.
Другой очень простой метод реализации, который можно использовать, когда ключи ограничены узким диапазоном, - это прямая адресация в массив: значение для заданного ключа k сохраняется в ячейке массива A [k], или, если нет отображения для k, тогда в ячейке хранится специальное контрольное значение, которое указывает на отсутствие отображения. Этот метод не только прост, но и быстр: каждая операция со словарем занимает постоянное время. Однако требование к пространству для этой структуры - это размер всего пространства ключей, что делает ее непрактичной, если пространство ключей невелико.
Двумя основными подходами к реализации словарей являются хэш-таблица или дерево поиска.
На этом графике сравнивается среднее количество пропусков кеш-памяти ЦП, необходимых для поиска элементов в больших хеш-таблицах (намного превышающих размер кеша) с цепочкой и линейное зондирование. Линейное зондирование работает лучше благодаря лучшей локальности ссылки, хотя по мере заполнения таблицы ее производительность резко ухудшается. Наиболее часто используемая реализация ассоциативного массива общего назначения - с хешем table : массив в сочетании с хэш-функцией , которая разделяет каждый ключ на отдельную «корзину» массива. Основная идея хэш-таблицы заключается в том, что доступ к элементу массива через его индекс является простой операцией с постоянным временем. Следовательно, средние накладные расходы операции для хеш-таблицы - это только вычисление хеш-функции ключа в сочетании с доступом к соответствующему сегменту в массиве. Таким образом, хеш-таблицы обычно работают за время O (1) и в большинстве ситуаций превосходят альтернативы.
Хеш-таблицы должны иметь возможность обрабатывать коллизии : когда хеш-функция отображает два разных ключа в одну и ту же корзину массива. Два наиболее распространенных подхода к этой проблеме - это разделение цепочки и открытая адресация. При отдельной цепочке массив не сохраняет само значение, а сохраняет указатель на другой контейнер, обычно это список ассоциаций , в котором хранятся все значения, соответствующие хешу. С другой стороны, при открытой адресации, если обнаруживается хеш-коллизия, таблица ищет пустое место в массиве для хранения значения детерминированным образом, обычно путем просмотра следующей непосредственной позиции в массиве.
Открытая адресация имеет более низкий коэффициент промахов в кэш, чем отдельная цепочка, когда таблица в основном пуста. Однако по мере того, как таблица заполняется большим количеством элементов, производительность открытой адресации падает экспоненциально. Кроме того, при раздельной цепочке в большинстве случаев используется меньше памяти, если только записи не очень маленькие (меньше четырехкратного размера указателя).
Другой распространенный подход - реализовать ассоциативный массив с самобалансирующимся двоичным деревом поиска , такие как AVL-дерево или красно-черное дерево.
По сравнению с хеш-таблицами, эти структуры имеют как преимущества, так и недостатки. В худшем случае производительность самобалансирующихся двоичных деревьев поиска значительно лучше, чем у хеш-таблицы, с временной сложностью в нотации большого O из O (log n). Это контрастирует с хэш-таблицами, производительность которых в наихудшем случае включает в себя все элементы, совместно использующие одну корзину, что приводит к временной сложности O (n). Кроме того, как и все бинарные деревья поиска, самобалансирующиеся бинарные деревья поиска поддерживают порядок своих элементов. Таким образом, обход его элементов следует шаблону от наименьшего к наибольшему, тогда как обход хеш-таблицы может привести к тому, что элементы будут расположены в случайном порядке. Однако хеш-таблицы имеют гораздо лучшую временную сложность в среднем случае, чем самобалансирующиеся деревья двоичного поиска O (1), и их производительность в худшем случае очень маловероятна при использовании хорошей хэш-функции .
Стоит отметить, что самобалансирующееся двоичное дерево поиска может использоваться для реализации сегментов для хеш-таблицы, которая использует отдельную цепочку. Это позволяет выполнять поиск констант в среднем случае, но обеспечивает производительность O (log n) в худшем случае. Однако это вносит дополнительную сложность в реализацию и может привести к еще худшей производительности для небольших хэш-таблиц, где время, затрачиваемое на вставку и балансировку дерева, больше, чем время, необходимое для выполнения линейного поиска на всех элементов связанного списка или аналогичной структуры данных.
Ассоциативные массивы также могут храниться в несбалансированных двоичных деревьях поиска или в структурах данных, специализированных для особый тип ключей, такой как дерево счисления, пытается, массивы Джуди или деревья Ван Эмде Боаса, хотя возможности этой реализации методы в сравнении с хеш-таблицами различаются; например, деревья Джуди по-прежнему работают с меньшей эффективностью, чем хэш-таблицы, в то время как тщательно отобранные хеш-таблицы обычно работают с большей эффективностью по сравнению с адаптивными основами системы счисления с потенциально большими ограничениями на типы данных, которые они могут обрабатывать. Преимущества этих альтернативных структур проистекают из их способности обрабатывать операции, выходящие за рамки базовых операций ассоциативного массива, такие как поиск сопоставления, ключ которого является ближайшим к запрошенному ключу, когда сам запрос не присутствует в наборе сопоставлений.
| Базовая структура данных | Поиск | Вставка | Удаление | Упорядоченное | |||
|---|---|---|---|---|---|---|---|
| среднее | наихудший случай | средний | наихудший случай | средний | наихудший случай | ||
| Хеш-таблица | O (1) | O (n) | O (1) | O (n) | O (1) | O (n) | Нет |
| Самобалансирующееся дерево двоичного поиска | O (log n) | O (log n) | O (log n) | O (log n) | O (log n) | O (log n) | Да |
| несбалансированное двоичное дерево поиска | O (log n) | O (n) | O (log n) | O (n) | O (log n) | O (n) | Да |
| Последовательный контейнер пар ключ-значение. (например, список ассоциаций ) | O (n) | O (n) | O (1) | O (1) | O (n) | O (n) | Нет |
Основное определение словаря не требует порядка. Чтобы гарантировать фиксированный порядок перечисления, упорядоченные версии ассоциированного иативный массив. Упорядоченный словарь имеет два смысла:
. Последний смысл упорядоченных словарей встречается чаще. Они могут быть реализованы с использованием списка ассоциаций или путем наложения двусвязного списка поверх обычного словаря. Последний подход, который использовался CPython до версии 3.6, имеет преимущество в том, что сохраняет потенциально лучшую сложность другой реализации. CPython 3.6+ упорядочивает словари путем разделения хэш-таблицы на упорядоченный вставкой массив пар kv и разреженный массив («хеш-таблица») индексов.
Ассоциативные массивы могут могут быть реализованы на любом языке программирования в виде пакета, и многие языковые системы предоставляют их как часть своей стандартной библиотеки. В некоторых языках они не только встроены в стандартную систему, но и имеют специальный синтаксис, часто использующий индексы типа массивов.
Встроенная синтаксическая поддержка ассоциативных массивов была представлена в 1969 г. SNOBOL4 под названием «таблица». TMG предлагал таблицы со строковыми ключами и целочисленными значениями. MUMPS сделал многомерные ассоциативные массивы, необязательно постоянные, свою ключевую структуру данных. SETL поддерживал их как одну из возможных реализаций наборов и карт. Большинство современных языков сценариев, начиная с AWK и включая Rexx, Perl, Tcl, JavaScript, Maple, Python, Ruby, Wolfram Language, Go и Lua поддерживают ассоциативные массивы в качестве основного типа контейнера. На многих других языках они доступны как библиотечные функции без специального синтаксиса.
В Smalltalk, Objective-C, .NET, Python, REALbasic, Swift, VBA и Delphi они называются словарями; в 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 также поддерживает ассоциативные массивы.
Многие программы, использующие ассоциативные массивы, в какой-то момент должны будут хранить эти данные в более постоянной форме, как в компьютерном файле . Распространенным решением этой проблемы является обобщенная концепция, известная как архивирование или сериализация, которая создает текстовое или двоичное представление исходных объектов, которые могут быть записаны непосредственно в файл. Чаще всего это реализуется в базовой объектной модели, такой как.Net или Cocoa, которая включает стандартные функции, преобразующие внутренние данные в текстовую форму. Программа может создать полное текстовое представление любой группы объектов, вызвав эти методы, которые почти всегда уже реализованы в классе базовых ассоциативных массивов.
Для программ, использующих очень большие наборы данных, этот вид отдельных файловое хранилище не подходит, и требуется система управления базами данных (DB). Некоторые системы БД изначально хранят ассоциативные массивы, сериализуя данные, а затем сохраняя эти сериализованные данные и ключ. Затем отдельные массивы могут быть загружены или сохранены из базы данных с помощью ключа для ссылки на них. Эти хранилища "ключ-значение" использовались в течение многих лет и имеют такую же долгую историю, как и более распространенная реляционная база данных (RDB), но отсутствие стандартизации среди других причин., ограничили их использование определенными нишевыми ролями. Для этих ролей в большинстве случаев использовались РБД, хотя сохранение объектов в РБД может быть сложной задачей, известной как несоответствие объектно-реляционного импеданса.
После c. 2010 г. потребность в высоком базы данных производительности, подходящие для облачных вычислений и более точно соответствующие внутренней структуре программ, использующих их, привели к возрождению рынка хранилищ ключей и значений. Эти системы могут хранить и извлекать ассоциативные массивы обычным способом, что может значительно повысить производительность в обычных рабочих процессах, связанных с Интернетом.
Портал компьютерного программирования  | Найдите ассоциативный массив в Wiktionary, бесплатном словаре. |
