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

от Уикипедия, свободната енциклопедия
Направо към навигацията Направо към търсенето
Карта
Асоциативен масив

В програмирането абстрактната структура данни „асоциативен масив“ представлява съвкупност от наредени двойки (ключ, стойност), заедно с дефинирани операции за достъп до стойностите по ключ. Алтернативно тази структура може да бъде наречена още „карта“ (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 нуждата за по-производителни бази данни подходящи за облачни изчисления и нуждата за по-близо съответствие на базите към вътрешната структура на програмите доведе до ренесанс в пазара на запазването на асоциативни масиви. Тези системи могат да запазват и извличат карти с вградени техники, което драстично подобрява производителноста на повечето уеб-ориентирани работни процеси.

Вижте също[редактиране | редактиране на кода]

Източници[редактиране | редактиране на кода]

  1. а б в г д Goodrich, Michael T.; Tamassia, Roberto (2006), "9.1 The Map Abstract Data Type", „Data Structures & Algorithms in Java“ (4th ed.), Wiley, pp. 368 – 371 
  2. а б в г Mehlhorn, Kurt; Sanders, Peter (2008), "4 Hash Tables and Associative Arrays", „Algorithms and Data Structures: The Basic Toolbox“, Springer, pp. 81 – 98, http://people.mpi-inf.mpg.de/~mehlhorn/ftp/Toolbox/HashTables.pdf 
  3. Anderson, Arne. Optimal Bounds on the Dictionary Problem. // Proc. Symposium on Optimal Algorithms. Springer Verlag, 1989. с. 106 – 114.
  4. а б в Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), "11 Hash Tables", „Introduction to Algorithms“ (2nd ed.), MIT Press and McGraw-Hill, pp. 221 – 252, ISBN 0-262-03293-7 .
  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, 1996-02-20.
  8. Klammer, F.; Mazzolini, L. (2006), "Pathfinders for associative maps", „Ext. Abstracts GIS-l 2006“, GIS-I, pp. 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

Външни препратки[редактиране | редактиране на кода]

Криейтив Комънс - Признание - Споделяне на споделеното Лиценз за свободна документация на ГНУ Тази страница частично или изцяло представлява превод на страницата „Associative_array“ в Уикипедия на английски. Оригиналният текст, както и този превод, са защитени от Лиценза „Криейтив Комънс - Признание - Споделяне на споделеното“, а за съдържание, създадено преди юни 2009 година — от Лиценза за свободна документация на ГНУ. Прегледайте историята на редакциите на оригиналната страница, както и на преводната страница. Вижте източниците на оригиналната статия, състоянието ѝ при превода, и списъка на съавторите.