В програмирането абстрактната структура данни „асоциативен масив“ представлява съвкупност от наредени двойки (ключ, стойност), заедно с дефинирани операции за достъп до стойностите по ключ. Алтернативно тази структура може да бъде наречена още „карта“ (map) или „речник“ (dictionary).
Операции, свързани с тази структура от данни позволяват: Добавянето на двойка (ключ-стойност) към колекцията Премахването на двойка (ключ-стойност) от колекцията Променяне на съществуваща двойка (ключ-стойност) Търсене на стойност свързана с даден ключ Проблемът „речник“ е един класически проблем в компютърните науки: задачата да се създаде една структура от данни, която да поддържа набор от информация по време на операциите „търси“, „изтрий“ и „добави“. Едно стандартно решение на този проблем е хеш-таблицата. В някои случаи е възможно проблема да се реши с използването на директно адресирани масиви, двоични дървета за търсене или други по-специални структури..
Много програмни езици включват асоциативните масиви като примитивни типове данни, а при други те са достъпни чрез софтуерни библиотеки. Асоциативната памет е вид на директна поддръжка на асоциативния масив на хардуерно ниво.
Асоциативните масиви имат много приложения, включително и при основни шаблони за дизайн като мемоизация и декоратор (шаблон).Goodrich & Tamassia (2006), pp. 597 – 599.
Примери Да предположим, че имаме низ от заети книги в една библиотека и това е представено в структура от данни. Всяка книга в библиотеката може да е заета само от един човек в определен момент. Един човек обаче може да е заел много на брой книги в един и същ отрязък от време. Оттук насетне информацията с това коя книга е заета от кой човек може да бъде представена с асоциативен масив, в който името на книгата е „ключ“, а държателя е „стойност“.
В повечето езици двойката (ключ, стойност) би изглеждала по следният начин:{ "Great Expectations": "John", "Pride and Prejudice": "Alice", "Wuthering Heights": "Alice" }
Операции В асоциативния масив асоциацията между ключ и стойност често се нарича „съвкупност“, и същата дума може да се използва за процеса на създаване на нова асоциация.
Операциите които обикновено са дефинирани при този тип масив са: Add or Insert – добавя нова съвкупност (ключ, стойност) в колекцията като ключа се обвързва с новата стойност. Аргументите при тази операция са ключа и стойността. Reassign – заменя стойността в един от ключовете които вече са в колекцията, обвързвайки старият ключ с новата стойност. Както при добавянето аргументите на тази операция отново са (key, value). Remove or delete – премахва (key, value) двойката от колекцията като двата елемента вече не са обвързани. Аргументът в тази операция е ключът. Lookup – намира стойността (ако има такава) която е обвързана към даден ключ. Аргументът при тази операция е ключът, а стойността се връча като резултат от операцията. Ако стойност не е намерена някои имплементации може да върнат изключение (exception).
В допълнение, асоциативните масиви може също да съдържат други операции като примерно намиране броя на съвкупности или конструирането на итератор който да обходи в цикъл всичките съвкупности. Обикновено при такава операция редът при който двойките се връщат като резултат варира.
Мултикарта генерализира асоциативен масив позволявайки много на брой стойности да бъдат асоциирани с един-единствен ключGoodrich & Tamassia (2006), pp. 389 – 397.. Двупосочна карта е близък абстрактен тип карта в който обвързването работи в двете посоки: всяка стойност трябва да е асоциирана с уникален ключ, като втора операция за обхождане взима стойност като аргумент и търси ключа асоцииран с тази стойност
Имплементация За речници с много малък брой обвързани елементи, е разбираемо речникът да се имплементира, чрез асоциативен списък, един свързан списък от елементи. С тази имплементация, времето да се извършат основните операции на речника е линейно спрямо броя елементи. Въпреки че е лесно да се имплементира, константите фактори по време на изпълнение са малки.
Друга лесна техника за имплементация, практична когато ключовете са ограничени в един малък интервал от цели числа, е директно обръщане към масив: стойността за даден ключ k е запазена в клетката на масив – A[k], или ако не съществува обвързващ елемент за k тогава клетката запазва една специална сентинел стойност, която показва липсата на обвързване. Тази техника освен че е лесна, е и бърза – всяка операция на речника взима константно време. Но, изискването за памет за тази структура е размера на целия обект (keyspace), което я прави непрактична, ако той не е малък.
Имплементацията на асоциативен масив с хеш-таблица е най-често използваната за общо предназначение – един масив от обвързани елементи с хеш-функция, която записва всеки възможен ключ в масив от индекси. Основната идея на една хеш-таблица е, че елемента на даден ключ се запазва в позиция дадена чрез прилагането на хеш-функцията към този ключ и lookup операциите се изпълняват като се гледа тази клетка от масива и използвайки елемента намерен там. Въпреки това, речници базирани на хеш-таблица трябва да се справят с колизии, които се случват когато два ключа се записани от хеш-фунцията на същия индекс. Много различни решения за тази пречка са намерени, често основани или на отворена адресация(търси се в поредица от индекси на хеш-таблица вместо всеки един индекс, докато не намери или дадения ключ или празна клетка) или с нареждане в списък (запазване на малък асоциативен списък вместо елемент във всяка клетка)..
Друг често срещан подход е един асоциативен масив да се имплементира с червено-черно дърво.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.“
Също така речниците може да се запазват в двоично дърво за търсене или в структури от данни специализирани в определен тип ключ като радикс дърво, префиксно дърво, Жуди масиви или ван Емде Боас дървета, но тези имплементационни методи са по-малко ефикасни от хеш-таблиците, както и при поставяне на по-големи ограничения на типа данни, с които могат да се справят. Предимствата на тези алтернативни структури идват от възможността да се справят с операции повече от основните на асоциативния масив, като да се намери елемент, чийто ключ е най-близо до търсения, когато самата заявка не съществува в набора на елементи.
Реализация на речник с червено-черно дърво в Java „Въведение в програмирането с Java“. Светлин Наков и колектив, 2008 г. Класът 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 Класът 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