В информатике ассоциативный массив , карта , таблица символов или словарь — это абстрактный тип данных , который хранит коллекцию пар (ключ, значение) , так что каждый возможный ключ появляется в коллекции не более одного раза. С математической точки зрения ассоциативный массив — это функция с конечной областью определения . [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 , структура данных будет такой:
{ «Гордость и предубеждение» : «Алиса» , «Грозовой перевал» : «Алиса» , «Большие надежды» : «Джон» } Операция поиска по ключу «Большие надежды» вернет «Джон». Если Джон вернет свою книгу, это вызовет операцию удаления, а если Пэт выберет книгу, это вызовет операцию вставки, что приведет к другому состоянию:
{ «Гордость и предубеждение» : «Алиса» , «Братья Карамазовы» : «Пэт» , «Грозовой перевал» : «Алиса» } Для словарей с очень небольшим количеством сопоставлений может иметь смысл реализовать словарь с использованием списка ассоциаций — связанного списка сопоставлений. При такой реализации время выполнения основных словарных операций линейно зависит от общего количества отображений; однако его легко реализовать, и постоянные факторы, влияющие на время его работы, невелики. [3] [10]
Другой очень простой метод реализации, который можно использовать, когда ключи ограничены узким диапазоном, — это прямая адресация в массив: значение для данного ключа k сохраняется в ячейке массива A [ k ], или если для k нет сопоставления. затем в ячейке сохраняется специальное контрольное значение , указывающее на отсутствие сопоставления. Этот метод прост и быстр: каждая операция со словарем занимает постоянное время. Однако требование к пространству для этой структуры равно размеру всего пространства ключей, что делает его непрактичным, если только пространство ключей не маленькое. [5]
Двумя основными подходами к реализации словарей являются хеш-таблица и дерево поиска . [3] [4] [5] [6]
Наиболее часто используемая реализация ассоциативного массива общего назначения — это хеш-таблица : массив , объединенный с хеш-функцией , которая отделяет каждый ключ в отдельный «корзину» массива. Основная идея хеш-таблицы заключается в том, что доступ к элементу массива через его индекс представляет собой простую операцию, выполняемую с постоянным временем. Таким образом, средние затраты на операцию для хеш-таблицы — это только вычисление хеша ключа в сочетании с доступом к соответствующему сегменту внутри массива. Таким образом, хеш-таблицы обычно работают за время O(1) и обычно превосходят альтернативные реализации.
Хэш-таблицы должны иметь возможность обрабатывать коллизии : сопоставление хэш-функцией двух разных ключей с одним и тем же сегментом массива. Двумя наиболее распространенными подходами к этой проблеме являются раздельная цепочка и открытая адресация . [3] [4] [5] [11] При раздельной цепочке массив не хранит само значение, а хранит указатель на другой контейнер, обычно список ассоциаций , в котором хранятся все значения, соответствующие хешу. Напротив, при открытой адресации, если обнаруживается коллизия хешей, таблица ищет пустое место в массиве для хранения значения детерминированным способом, обычно путем просмотра следующей непосредственной позиции в массиве.
Открытая адресация имеет более низкий коэффициент промахов в кэше , чем раздельная цепочка, когда таблица в основном пуста. Однако по мере того, как таблица заполняется большим количеством элементов, производительность открытой адресации снижается экспоненциально. Кроме того, в большинстве случаев раздельное связывание использует меньше памяти, если только записи не очень малы (менее чем в четыре раза больше размера указателя).
Другой распространенный подход — реализация ассоциативного массива с самобалансирующимся двоичным деревом поиска , например деревом AVL или красно-черным деревом . [12]
По сравнению с хеш-таблицами эти структуры имеют как сильные, так и слабые стороны. В худшем случае производительность самобалансирующихся двоичных деревьев поиска значительно выше, чем у хеш-таблицы, с временной сложностью в большой записи O, равной O(log n ). В этом отличие от хеш-таблиц, в которых наихудшая производительность связана с тем, что все элементы используют один и тот же сегмент, что приводит к временной сложности O( n ). Кроме того, как и все двоичные деревья поиска, самобалансирующиеся двоичные деревья поиска сохраняют свои элементы в порядке. Таким образом, обход ее элементов следует шаблону от наименьшего к наибольшему, тогда как обход хеш-таблицы может привести к тому, что элементы будут находиться в случайном порядке. Поскольку древовидные карты упорядочены, они также могут удовлетворять запросам диапазона (находить все значения между двумя границами), тогда как хеш-карта может находить только точные значения. Однако хеш-таблицы имеют гораздо лучшую временную сложность в среднем случае, чем самобалансирующиеся двоичные деревья поиска O(1), и их производительность в наихудшем случае маловероятна при использовании хорошей хеш-функции .
Стоит отметить, что самобалансирующееся двоичное дерево поиска можно использовать для реализации сегментов для хеш-таблицы, в которой используется отдельное связывание. Это позволяет выполнять поиск констант в среднем случае, но гарантирует производительность O(log n ) в худшем случае . Однако это усложняет реализацию и может привести к еще большему ухудшению производительности для небольших хеш-таблиц, где время, затрачиваемое на вставку и балансировку дерева, превышает время, необходимое для выполнения линейного поиска по всем элементам связанного списка. или аналогичная структура данных. [13] [14]
Ассоциативные массивы также могут храниться в несбалансированных двоичных деревьях поиска или в структурах данных, специализированных для определенного типа ключей, таких как счисления , массивы попыток , массивы Джуди или деревья Ван Эмде Боаса , хотя относительная производительность этих реализаций варьируется. Например, считается, что деревья Джуди работают менее эффективно, чем хеш-таблицы, в то время как тщательно выбранные хеш-таблицы обычно работают более эффективно, чем адаптивные поразрядные деревья, с потенциально более серьезными ограничениями на типы данных, которые они могут обрабатывать. [15] Преимущества этих альтернативных структур заключаются в их способности обрабатывать дополнительные операции с ассоциативными массивами, такие как поиск отображения, ключ которого наиболее близок к запрашиваемому ключу, когда запрос отсутствует в наборе отображений.
Базовое определение словаря не требует порядка. Чтобы гарантировать фиксированный порядок перечисления, часто используются упорядоченные версии ассоциативного массива. У упорядоченного словаря есть два значения:
<map>контейнер C++. [16]Последнее встречается чаще. Такие упорядоченные словари могут быть реализованы с использованием списка ассоциаций , путем наложения двусвязного списка поверх обычного словаря или путем перемещения фактических данных из разреженного (неупорядоченного) массива в плотный массив с упорядочением вставки.
Ассоциативные массивы могут быть реализованы на любом языке программирования в виде пакета, и многие языковые системы предоставляют их как часть стандартной библиотеки. В некоторых языках они не только встроены в стандартную систему, но и имеют специальный синтаксис, часто с использованием индексов, подобных массивам.
Встроенная синтаксическая поддержка ассоциативных массивов была представлена в 1969 году компанией SNOBOL4 под названием «таблица». 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 они называются Коллекциями . Язык D также поддерживает ассоциативные массивы. [22]
Многим программам, использующим ассоциативные массивы, потребуется хранить эти данные в более постоянной форме, например в компьютерном файле . Распространенным решением этой проблемы является обобщенная концепция, известная как архивирование или сериализация , которая создает текстовое или двоичное представление исходных объектов, которые можно записать непосредственно в файл. Чаще всего это реализуется в базовой объектной модели, такой как .Net или Cocoa, которая включает стандартные функции, преобразующие внутренние данные в текст. Программа может создать полное текстовое представление любой группы объектов, вызывая эти методы, которые почти всегда уже реализованы в базовом классе ассоциативного массива. [23]
Для программ, использующих очень большие наборы данных, такой тип хранения отдельных файлов не подходит и требуется система управления базой данных (БД). Некоторые системы БД изначально хранят ассоциативные массивы путем сериализации данных, а затем сохранения этих сериализованных данных и ключа. Затем отдельные массивы можно загрузить или сохранить из базы данных, используя ключ для ссылки на них. Эти хранилища «ключ-значение» используются уже много лет и имеют такую же историю, как и история более распространенных реляционных баз данных (RDB), но отсутствие стандартизации, среди других причин, ограничивало их использование определенными нишевыми ролями. В большинстве случаев для этих ролей использовались RDB, хотя сохранение объектов в RDB может быть сложной задачей — проблема, известная как несоответствие объектно-реляционного импеданса .
После ц. В 2010 году потребность в высокопроизводительных базах данных, подходящих для облачных вычислений и более точно соответствующих внутренней структуре использующих их программ, привела к возрождению рынка хранилищ «ключ-значение». Эти системы могут хранить и извлекать ассоциативные массивы собственным способом, что может значительно повысить производительность в обычных рабочих процессах, связанных с Интернетом.
