Асоциативен масив

Асоциативен масив

В програмирането абстрактната структура данни „асоциативен масив“ представлява съвкупност от наредени двойки (ключ, стойност), заедно с дефинирани операции за достъп до стойностите по ключ. Алтернативно тази структура може да бъде наречена още „карта“ (map) или „речник“ (dictionary).

Операции, свързани с тази структура от данни позволяват: ^[1][2]

• Добавянето на двойка (ключ-стойност) към колекцията
• Премахването на двойка (ключ-стойност) от колекцията
• Променяне на съществуваща двойка (ключ-стойност)
• Търсене на стойност свързана с даден ключ

Проблемът „речник“ е един класически проблем в компютърните науки: задачата да се създаде една структура от данни, която да поддържа набор от информация по време на операциите „търси“, „изтрий“ и „добави“^[3]. Едно стандартно решение на този проблем е хеш-таблицата. В някои случаи е възможно проблема да се реши с използването на директно адресирани масиви, двоични дървета за търсене или други по-специални структури.^[1][2][4]

Много програмни езици включват асоциативните масиви като примитивни типове данни, а при други те са достъпни чрез софтуерни библиотеки. Асоциативната памет е вид на директна поддръжка на асоциативния масив на хардуерно ниво.

Асоциативните масиви имат много приложения, включително и при основни шаблони за дизайн като мемоизация и декоратор (шаблон).^[5]

Примери

Да предположим, че имаме низ от заети книги в една библиотека и това е представено в структура от данни. Всяка книга в библиотеката може да е заета само от един човек в определен момент. Един човек обаче може да е заел много на брой книги в един и същ отрязък от време. Оттук насетне информацията с това коя книга е заета от кой човек може да бъде представена с асоциативен масив, в който името на книгата е „ключ“, а държателя е „стойност“.

В повечето езици двойката (ключ, стойност) би изглеждала по следният начин:

{
    "Great Expectations": "John",
    "Pride and Prejudice": "Alice",
    "Wuthering Heights": "Alice"
}

Операции

В асоциативния масив асоциацията между ключ и стойност често се нарича „съвкупност“, и същата дума може да се използва за процеса на създаване на нова асоциация.

Операциите които обикновено са дефинирани при този тип масив са:^[1][2]

• Add or Insert – добавя нова съвкупност (ключ, стойност) в колекцията като ключа се обвързва с новата стойност. Аргументите при тази операция са ключа и стойността.
• Reassign – заменя стойността в един от ключовете които вече са в колекцията, обвързвайки старият ключ с новата стойност. Както при добавянето аргументите на тази операция отново са (key, value).
• Remove or delete – премахва (key, value) двойката от колекцията като двата елемента вече не са обвързани. Аргументът в тази операция е ключът.
• Lookup – намира стойността (ако има такава) която е обвързана към даден ключ. Аргументът при тази операция е ключът, а стойността се връча като резултат от операцията. Ако стойност не е намерена някои имплементации може да върнат изключение (exception).

В допълнение, асоциативните масиви може също да съдържат други операции като примерно намиране броя на съвкупности или конструирането на итератор който да обходи в цикъл всичките съвкупности. Обикновено при такава операция редът при който двойките се връщат като резултат варира. 

Мултикарта генерализира асоциативен масив позволявайки много на брой стойности да бъдат асоциирани с един-единствен ключ^[6]. Двупосочна карта е близък абстрактен тип карта в който обвързването работи в двете посоки: всяка стойност трябва да е асоциирана с уникален ключ, като втора операция за обхождане взима стойност като аргумент и търси ключа асоцииран с тази стойност

Имплементация

За речници с много малък брой обвързани елементи, е разбираемо речникът да се имплементира, чрез асоциативен списък, един свързан списък от елементи. С тази имплементация, времето да се извършат основните операции на речника е линейно спрямо броя елементи. Въпреки че е лесно да се имплементира, константите фактори по време на изпълнение са малки.^[1][7]

Друга лесна техника за имплементация, практична когато ключовете са ограничени в един малък интервал от цели числа, е директно обръщане към масив: стойността за даден ключ k е запазена в клетката на масив – A[k], или ако не съществува обвързващ елемент за k тогава клетката запазва една специална сентинел стойност, която показва липсата на обвързване. Тази техника освен че е лесна, е и бърза – всяка операция на речника взима константно време. Но, изискването за памет за тази структура е размера на целия обект (keyspace), което я прави непрактична, ако той не е малък.^[4]

Имплементацията на асоциативен масив с хеш-таблица е най-често използваната за общо предназначение – един масив от обвързани елементи с хеш-функция, която записва всеки възможен ключ в масив от индекси. Основната идея на една хеш-таблица е, че елемента на даден ключ се запазва в позиция дадена чрез прилагането на хеш-функцията към този ключ и lookup операциите се изпълняват като се гледа тази клетка от масива и използвайки елемента намерен там. Въпреки това, речници базирани на хеш-таблица трябва да се справят с колизии, които се случват когато два ключа се записани от хеш-фунцията на същия индекс. Много различни решения за тази пречка са намерени, често основани или на отворена адресация(търси се в поредица от индекси на хеш-таблица вместо всеки един индекс, докато не намери или дадения ключ или празна клетка) или с нареждане в списък (запазване на малък асоциативен списък вместо елемент във всяка клетка).^[1][2][4][8]

Друг често срещан подход е един асоциативен масив да се имплементира с червено-черно дърво.^[9]

Също така речниците може да се запазват в двоично дърво за търсене или в структури от данни специализирани в определен тип ключ като радикс дърво, префиксно дърво, Жуди масиви или ван Емде Боас дървета, но тези имплементационни методи са по-малко ефикасни от хеш-таблиците, както и при поставяне на по-големи ограничения на типа данни, с които могат да се справят. Предимствата на тези алтернативни структури идват от възможността да се справят с операции повече от основните на асоциативния масив, като да се намери елемент, чийто ключ е най-близо до търсения, когато самата заявка не съществува в набора на елементи.

Реализация на речник с червено-черно дърво в Java

^[10] Класът TreeMap<K, V> (червено-черно дърво) идва наготово заедно със стандартните библиотеки на Java. Червено-черното дърво е подредено двоично балансирано дърво за претърсване. Ето защо едно от важните изисквания, които са наложени върху множеството от ключове при използването на TreeMap<K, V>, е те да имат наредба. Това означава, че ако имаме два ключа, то или единият е по-голям от другия, или те са равни.

Използването на двоично дърво ни носи едно силно предимство: ключовете в речника се пазят сортирани. Благодарение на това свойство, ако данните ни трябват подредени по ключ, няма нужда да ги сортираме допълнително. Всъщност това свойство е единственото предимство на тази реализация пред реализацията с хеш-таблица. Пазенето на ключовете сортирани идва със своята цена. Работата с балансирани дървета е малко по-бавна от работата с хеш-таблици. По тази причина, ако няма специални изисквания за наредба на ключовете, за предпочитане е да се използва HashMap<K, V>.

Стандартните операции, свързани с наредбата на елементите:

• извличане на най-малък и най-голям елемент – firstEntry(), lastEntry(), firstKey(), lastKey();
• извличане на всички елементи, по-малки или по-големи от даден ключ – headMap(key), tailMap(key);
• извличане на всички елементи в даден диапазон (примерно със стойност на ключа между 100 и 200) – subMap(startKey, endKey).

Tези операции може да са много полезни при решавани на задачи, свързани с бързо извличане на подмножества на дадено множество. Използването на реализация на речник чрез балансирано дърво ни дава свойството, че когато обхождаме елементите му те ще бъдат сортирани по ключа. о този начин реализираме допълнително наложеното условие думите да са сортирани по азбучен ред. Нека имаме следният проблем: да намерим всички различни думи в текстов файл, както и колко пъти се срещат всяка от тях в текста като искаме да въведем намерените думи по азбучен ред:

private static Map<String, Integer> createWordsCounts(String text) {
    Scanner textScanner = new Scanner(text);
    Map<String, Integer> words = new TreeMap<String, Integer>();

    while (textScanner.hasNext()) {
        String word = textScanner.next();
        Integer count = words.get(word);
        if (count == null) {
            count = 0; }
            words.put(word, count + 1);
        }
    return words;
}

Реализация на асоциативен масив с хеш таблица в Java^[10]

Класът HashMap<K, V> е стандартна имплементация на речник с хеш-таблица в Java Collections Framework. Структурата от данни хеш-таблица реализира по един изключително ефективен начин абстрактната структура данни „речник“. Реализацията с хеш-таблица има важното предимство, че времето за достъп до стойност от речника, при правилно използване, не зависи от броя на елементите в него (поне на теория).

Основни операции с класа HashMap<K, V>:

• V put(K, V) добавя нова стойност за даден ключ или презаписва вече съществуващата за този ключ. В резултат се връща старата стойност за посочения ключ или null, ако няма стара стойност.
• void putAll(Map<K,V>) добавя всички наредени двойки от друг речник в текущия. звикването на този метод е еквивалентно на извикването на put(K, V) за всеки един елемент на речника, който е подаден като параметър.
• V get(Object) връща стойността за дадения ключ или null, ако няма елемент с такъв ключ.
• V remove(K) изтрива от речника елемента с този ключ.
• void clear() премахва всички елементи от речника.
• boolean containsKey(K) проверява дали в речника присъства наредена двойка с посочения ключ.
• boolean containsValue(V) проверява дали в речника присъстват една или повече наредени двойки с посочената стойност. Тази операция работи бавно, тъй като проверява всеки елемент на хеш-таблицата.
• boolean isEmpty() връща true ако в речника няма нито една наредена двойка и false в противен случай.
• int size() връща броя на наредените двойки в речника.
• Set<Map.Entry<K, V> entriesSet() връща множество от наредените двойки в речника. Така можем лесно да ги обходим в цикъл.
• Set<K> keySet() връща множество от всички ключове в речника.
• Collection<V> връща колекция (може да има повторения) от всички стойности в речника.

Следният пример онагледява горепосочените операции. Имаме студенти. Всеки от тях би могъл да има най-много една оценка. Искаме да съхраняваме оценките в някаква структура, в която можем бързо да търсим по име на студент:

Map<String, Double> studentsNarks = new HashMap<String, Double>(6);
studentsNarks.put("Pesho", 3.00);
studentsNarks.put("Gosho", 4.50);
studentsNarks.put("Nakov", 5.50);
studentsNarks.put("Vesko", 3.50);
studentsNarks.put("Tsanev", 4.00);
studentsNarks.put("Nerdy", 6.00);
Double tsanevMark = studentsNarks.get("Tsanev");
studentsNarks.remove("Tsanev");
studentsNarks.containsKey("Tsanev"));
studentsNarks.put("Nerdy", 3.25);
for (Map.Entry<String, Double> studentMark : studentsNarks.entrySet()) {
System.out.printf("%s has %.2f%n", studentMark.getKey(), studentMark.getValue());
}

Изходът от принтирането би изгледал така:

Nerdy has 3,25
Nakov has 5,50
Vesko has 3,50
Gosho has 4,50
Pesho has 3,00

Редът, в който се отпечатват студентите е напълно случаен. Това е така, защото при хеш-таблиците (за разлика от балансираните дървета) елементите не се пазят сортирани. Дори ако текущият капацитет на таблицата се промени докато работим с нея, много е вероятно да се промени и редът, в който се пазят наредените двойки. Ако се нуждаем от наредба на елементите, можем преди отпечатване да сортираме елементите. Друг вариант е да използваме TreeMap<K, V>.

Поддържани езици

Асоциативните масиви могат да бъдат приложени във всеки програмен език като пакет и много езици за програмиране ги предоставят като част от стандартната си библиотека. В някои езици, те освен че са вградени в стандартната система, но имат и специален синтаксис, използавайки индексиране подобно на мсивите. Вградената синтактична поддръжка за асоциативни масиви е въведена от SNOBOL4, под името „table“. MUMPS са направили многомерни асоциативни масиви, които продължават да съществуват и в наши дни, техните ключове са структура от данни. SETL ги поддържа като възможна имплементация на сетове и карти. Повечето съвременни скриптови езици, като се започне с AWK и включва Rexx, Perl, Tcl, JavaScript, Python, Ruby и Lua поддържат асоциативни масиви като първичен тип контейнер. В много повече езици, те са на разположение като библиотечни функции, без специален синтаксис.

В различните езици този тип контейнери на информация или структури от данни се наричат различно – колекции, речници, карти, таблици и т.н. Най-популярните езици поддържащи речници/карти са Java, C#, Python и C++. В Smalltalk, Objective-C, .NET, Python, и REALbasic и Switt те са наречени речници; в Perl и Ruby те са наречени хешове; в C ++, Java, Go, Clojure и Scala те са наречени карти (виж карта (C++), неподредена карта (C++), и Карта; в Common Lisp и в Windows PowerShell, те се наричат хеш таблици (тъй като обикновено използват тази имплементация). В PHP, всички масиви могат да бъдат асоциативни, само че ключовете са ограничени до цели числа и низове (низове). В JavaScript (виж също JSON), всички обекти имат поведение на асоциативни масиви с низове като валидни ключове, докато другите карти и речници вземат произволни обекти като ключове. В Lua, те се наричат таблици, и се използва като примитивен градивен елемент за всички структури от данни. В Visual FoxPro, те се наричат колекции. Езикът за програмиране D също поддържа асоциативни масиви^[11].

Перманентно запазване

Повечето програми които използват асоциативни масиви в определен момент трябва да запазят тази информация за постоянно, като например в база данни или файл. Често решение на този проблем е генерализираната концепция позната като архивиране или сериализация, която произвежда текст или бинарна репрезентация на оригиналния обект която вече директно може да бъде записана във файл. Това е най-често имплементирано в подлежащия обектен модел на примерно .Net или Cocoa, които съдържат стандартни функции конвертиращи информацията в текстови формат. Програмата може да създаде цялостна текстова репрезентация на всяка група обекти като извика методи вече имплементирани в базовия клас на речника.^[12]

За програми които използват много голям обем от данни такъв тип индивидуално запазване на файловете не е удачно, за това се налага използването на Система за управление на бази от данни. Някои от тези системи имат вградени модули които могат да запазват речници като сериализират информацията и след това запазват тези сериализирани стойности и ключове. Индивидуални карти могат да бъдат заредени или запазени в базата данни използвайки ключът който се отнася за тях. Тези ключ-стойност контейнери са използвани от много години и имат история дълга колкото най-срещаните релационни бази данни(RDBs), но липсата на стандартизация, освен други причини, лимитира тяхната употреба до определени нишови роли. RDBs са използвани за тези роли в повечето случаи, въпреки че запазването на обекти в RDB може да бъде сложен проблем, познат като обектно-релационно несъответствие на съпротивлението.

След 2010 нуждата за по-производителни бази данни подходящи за облачни изчисления и нуждата за по-близо съответствие на базите към вътрешната структура на програмите доведе до ренесанс в пазара на запазването на асоциативни масиви. Тези системи могат да запазват и извличат карти с вградени техники, което драстично подобрява производителноста на повечето уеб-ориентирани работни процеси.

Вижте също

• Function (mathematics)
• JSON
• Бази данни
• Java

Източници

1. Goodrich, Michael T. и др. Data Structures & Algorithms in Java // 9.1 The Map Abstract Data Type. Wiley, 2006. с. 368 – 371.
2. Mehlhorn, Kurt и др. Algorithms and Data Structures: The Basic Toolbox // 4 Hash Tables and Associative Arrays. Springer, 2008. с. 81 – 98.
3. Anderson, Arne. Optimal Bounds on the Dictionary Problem // Proc. Symposium on Optimal Algorithms. Springer Verlag, 1989. с. 106 – 114.
4. Cormen, Thomas H. и др. Introduction to Algorithms // 2nd. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. с. 221 – 252..
5. Goodrich & Tamassia (2006), pp. 597 – 599.
6. Goodrich & Tamassia (2006), pp. 389 – 397.
7. When should I use a hash table instead of an association list? // lisp-faq/part2, 20 февруари 1996.
8. Klammer, F. и др. Ext. Abstracts GIS-l 2006 // Pathfinders for associative maps. GIS-I, 2006. с. 71 – 74..
9. Joel Adams and Larry Nyhoff. "Trees in STL". Quote: „The Standard Template library ... some of its containers -- the set<T>, map<T1, T2>, multiset<T>, and multimap<T1, T2> templates -- are generally built using a special kind of self-balancing binary search tree called a red-black tree.“
10. „Въведение в програмирането с Java“. Светлин Наков и колектив, 2008 г.
11. „Associative Arrays, the D programming language“. Digital Mars.
12. „Archives and Serializations Programming Guide“, Apple Inc., 2012

Външни препратки

• NIST's Dictionary of Algorithms and Data Structures: Associative Array

Тази страница частично или изцяло представлява превод на страницата Associative_array в Уикипедия на английски. Оригиналният текст, както и този превод, са защитени от Лиценза „Криейтив Комънс – Признание – Споделяне на споделеното“, а за съдържание, създадено преди юни 2009 година – от Лиценза за свободна документация на ГНУ. Прегледайте историята на редакциите на оригиналната страница, както и на преводната страница, за да видите списъка на съавторите. ​ ВАЖНО: Този шаблон се отнася единствено до авторските права върху съдържанието на статията. Добавянето му не отменя изискването да се посочват конкретни източници на твърденията, които да бъдат благонадеждни.​