Ассоциативный массив
В информатике , ассоциативный массив карта , таблица символов или словарь — это абстрактный тип данных , который хранит коллекцию пар (ключ, значение) , так что каждый возможный ключ появляется в коллекции не более одного раза. С математической точки зрения ассоциативный массив — это функция с конечной областью определения . [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 , структура данных будет такой:
{
"Pride and Prejudice": "Alice",
"Wuthering Heights": "Alice",
"Great Expectations": "John"
}
Операция поиска по ключу «Большие надежды» вернет «Джон». Если Джон вернет свою книгу, это вызовет операцию удаления, а если Пэт выберет книгу, это вызовет операцию вставки, что приведет к другому состоянию:
{
"Pride and Prejudice": "Alice",
"The Brothers Karamazov": "Pat",
"Wuthering Heights": "Alice"
}
Выполнение
[ редактировать ]Для словарей с очень небольшим количеством сопоставлений может иметь смысл реализовать словарь с использованием списка ассоциаций , который представляет собой связанный список сопоставлений. При такой реализации время выполнения основных операций со словарем линейно зависит от общего количества сопоставлений. Однако его легко реализовать, и постоянные факторы, влияющие на время его работы, невелики. [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] Преимущества этих альтернативных структур заключаются в их способности выполнять дополнительные операции с ассоциативными массивами, такие как поиск сопоставления, ключ которого наиболее близок к запрашиваемому ключу, когда запрос отсутствует в наборе сопоставлений.
Сравнение
[ редактировать ]| Базовая структура данных | Поиск или удаление | Вставка | Заказал | ||
|---|---|---|---|---|---|
| средний | худший случай | средний | худший случай | ||
| Хэш-таблица | О(1) | На ) | О(1) | На ) | Нет |
| Самобалансирующееся двоичное дерево поиска | О( вход ) | О( вход ) | О( вход ) | О( вход ) | Да |
| несбалансированное двоичное дерево поиска | О( вход ) | На ) | О( вход ) | На ) | Да |
| Последовательный контейнер пар ключ-значение (например, список ассоциаций ) |
На ) | На ) | О(1) | О(1) | Нет |
Заказанный словарь
[ редактировать ]Базовое определение словаря не требует порядка. Чтобы гарантировать фиксированный порядок перечисления, часто используются упорядоченные версии ассоциативного массива. У упорядоченного словаря есть два значения:
- Порядок перечисления всегда является детерминированным для данного набора ключей путем сортировки. Это относится к реализациям на основе дерева, одним из представителей которых является
<map>контейнер C++. [16] - Порядок перечисления не зависит от ключа и вместо этого основан на порядке вставки. Это относится к «упорядоченному словарю» в .NET Framework , LinkedHashMap в Java и Python . [17] [18] [19]
Последнее встречается чаще. Такие упорядоченные словари могут быть реализованы с использованием списка ассоциаций , путем наложения двусвязного списка поверх обычного словаря или путем перемещения фактических данных из разреженного (неупорядоченного) массива в плотный массив с упорядочением вставки.
Языковая поддержка
[ редактировать ]Ассоциативные массивы могут быть реализованы на любом языке программирования в виде пакета, и многие языковые системы предоставляют их как часть стандартной библиотеки. В некоторых языках они не только встроены в стандартную систему, но и имеют специальный синтаксис, часто с использованием индексов, подобных массивам.
Встроенная синтаксическая поддержка ассоциативных массивов была представлена в 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 года потребность в высокопроизводительных базах данных, подходящих для облачных вычислений и более точно соответствующих внутренней структуре использующих их программ, привела к возрождению рынка хранилищ «ключ-значение». Эти системы могут хранить и извлекать ассоциативные массивы собственным способом, что может значительно повысить производительность в обычных рабочих процессах, связанных с Интернетом.
См. также
[ редактировать ]
Ссылки
[ редактировать ]- ^ Коллинз, Грэм; Сайм, Дональд (1995). «Теория конечных отображений». Доказательство теорем логики высшего порядка и его приложения . Конспекты лекций по информатике. 971 : 122–137. дои : 10.1007/3-540-60275-5_61 . ISBN 978-3-540-60275-0 .
- ^ Андерссон, Арне (1989). «Оптимальные границы словарной задачи». Учеб. Симпозиум по оптимальным алгоритмам . Конспекты лекций по информатике. 401 . Спрингер Верлаг: 106–114. дои : 10.1007/3-540-51859-2_10 . ISBN 978-3-540-51859-4 .
- ↑ Перейти обратно: Перейти обратно: а б с д и Гудрич, Майкл Т .; Тамассиа, Роберто (2006), «9.1 Тип абстрактных данных карты», Структуры данных и алгоритмы в Java (4-е изд.), Wiley, стр. 368–371
- ↑ Перейти обратно: Перейти обратно: а б с д Мельхорн, Курт ; Сандерс, Питер (2008), «4 хэш-таблицы и ассоциативные массивы», Алгоритмы и структуры данных: базовый набор инструментов (PDF) , Springer, стр. 81–98, заархивировано (PDF) из оригинала 2 августа 2014 г.
- ↑ Перейти обратно: Перейти обратно: а б с д Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Штейн, Клиффорд (2001), «11 хэш-таблиц», Введение в алгоритмы (2-е изд.), MIT Press и McGraw-Hill , стр. 221–252, ISBN 0-262-03293-7 .
- ↑ Перейти обратно: Перейти обратно: а б Дитцфельбингер М., Карлин А., Мельхорн К., Мейер ауф дер Хайде Ф., Ронерт Х. и Тарьян Р.Э. 1994. «Динамическое идеальное хеширование: верхняя и нижняя границы». Архивировано 4 марта 2016 г. на Wayback Machine . СИАМ Дж. Компьютер. 23, 4 (август 1994 г.), 738–761. http://portal.acm.org/citation.cfm?id=182370 дои : 10.1137/S0097539791194094
- ^ Гудрич и Тамассия (2006) , стр. 597–599.
- ↑ Перейти обратно: Перейти обратно: а б Блэк, Пол Э.; Стюарт, Роб (2 ноября 2020 г.). "словарь" . Словарь алгоритмов и структур данных . Проверено 26 января 2022 г.
- ^ Гудрич и Тамассия (2006) , стр. 389–397.
- ^ «Когда мне следует использовать хеш-таблицу вместо списка ассоциаций?» . lisp-часто задаваемые вопросы/часть2. 20 февраля 1996 г.
- ^ Кламмер, Ф .; Маццолини, Л. (2006), «Следопыты для ассоциативных карт», Ext. Рефераты ГИС-л 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 апреля 2010 г.). «Линейный и бинарный поиск» . Проверено 20 ноября 2016 г.
- ^ Альварес, Виктор; Рихтер, Стефан; Чен, Сяо; Диттрих, Йенс (апрель 2015 г.). «Сравнение адаптивных поразрядных деревьев и хеш-таблиц». 2015 31-я Международная конференция IEEE по инженерии данных . Сеул, Южная Корея: IEEE. стр. 1227–1238. дои : 10.1109/ICDE.2015.7113370 . ISBN 978-1-4799-7964-6 . S2CID 17170456 .
- ^ "std::map" . ru.cppreference.com .
- ^ «Класс OrderedDictionary (System.Collections.Specialized)» . Документы MS .
- ^ «ЛинкедХэшМап» .
- ^ «коллекции — Типы данных контейнеров — Документация Python 3.9.0a3» . docs.python.org .
- ^ «Класс Dictionary<TKey, TValue>» . MSDN.
- ^ «System.Generics.Collections.TDictionary — Документация по API RAD Studio» . docwiki.embarcadero.com . Проверено 18 апреля 2017 г.
- ^ «Ассоциативные массивы, язык программирования D» . Цифровой Марс.
- ^ «Руководство по программированию архивов и сериализации» , Apple Inc., 2012 г.
Внешние ссылки
[ редактировать ]