Асоціативний масив
Асоціати́вний маси́в (англ. associative array) (або словник, хеш, в англійській літературі також застосовуються терміни associative container, map, mapping, hash, dictionary, finite map) — абстрактний тип даних (інтерфейс до сховища даних), що дозволяє зберігати дані у вигляді набору пар ключ — значення та доступом до значень за їх ключем.
Реалізації асоціативних масивів зазвичай підтримують операції додавання пари, а також пошуку та видалення пари за ключем:
- вставити (ключ, значення)
- шукати (ключ)
- вилучити (ключ)
Передбачається, що асоціативний масив не може містити дві пари з однаковими ключами. У парі (k, v) значення v називається значенням, що асоціюється з ключем k. Залежно від реалізації, ключі та значення можуть задаватися і множинами значень.
Операція шукати(ключ) повертає значення, що асоціюється із заданим ключем, або якийсь спеціальний об'єкт, що вказує на відсутність такого асоційованого значення. Дві інші операції нічого не повертають. Зазвичай, у різних реалізаціях асоціативного масиву семантика і назви операцій можуть відрізнятися.
Асоціативний масив з погляду інтерфейсу зручно розглядати як звичайний масив, в якому як індекси можна використовувати не тільки цілі числа, але і значення інших типів, наприклад, рядка.
Підтримка асоціативних масивів з допомогою стандартних засобів є в багатьох інтерпретованих мовах програмування високого рівня, таких як Swift, Perl, PHP, Python, Ruby, Tcl, JavaScript тощо. У C++ асоціативний масив підтримується на рівні шаблонних класів бібліотеки STL (map та споріднені класи).
Простим прикладом асоціативного масиву є телефонний довідник. Ключем у цьому випадку є сукупність ПІБ + адреса, а значенням — номер телефону.
Іншим прикладом може бути база даних доменних імен в Інтернеті, яка доменному імені зіставляє IP-адресу. Тут доменне ім'я буде ключем, а IP-адреса — значенням.
Вказані три операції часто доповнюються іншими. Типові розширення включають наступні операції:
- очищення — видалити всі записи
- обхід — «пробігтися» по всіх парах, що зберігаються
- мінімальне (ключ) — знайти пару з мінімальним значенням ключа
- максимальне (ключ) — знайти пару з максимальним значенням ключа
У останніх двох випадках необхідно, щоб на ключах була визначена операція порівняння.
Існують різні способи реалізації асоціативного масиву.
Найпростіша реалізація може ґрунтуватися на звичайному масиві, елементами якого є пари (ключ, значення). Для прискорення операції пошуку можна упорядкувати елементи цього масиву по ключу і здійснювати пошук методом ділення навпіл. Але це збільшить час виконання операції додавання нової пари, оскільки необхідно буде «розсувати» елементи масиву, щоб в порожнє місце, що утворилося, помістити новий запис.
Найпопулярніші реалізації засновані на різних деревах пошуку. Так, наприклад, в стандартній бібліотеці STL мови С++ контейнер map реалізований на основі червоно-чорного дерева. У мовах Ruby, Tcl, Python використовується один з варіантів хеш-таблиці. Є й інші реалізації.
У кожної реалізації є свої переваги і недоліки. Важливо, щоб всі три операції виконувалися як в середньому, так і у гіршому разі за час O(log n), де n — поточна кількість пар, що зберігаються. Для збалансованих дерев пошуку (зокрема для червоно-чорних дерев) ця умова виконана.
У реалізаціях, побудованих на хеш-таблицях, середній час оцінюється як O(1), що краще, ніж в реалізаціях, побудованих на деревах пошуку. Але при цьому не гарантується висока швидкість виконання окремої операції: час операції вставки в гіршому випадку оцінюється як O(n). Операція вставки виконується довго, коли коефіцієнт заповнення стає високим і необхідно перебудувати індекс хеш-таблиці.
Хеш-таблиці погані також тим, що на їхній основі не можна реалізувати швидкі додаткові операції пошуку мінімального та максимального значень, і алгоритм обходу всіх збережених пар в порядку зростання або спадання ключів.
Тут приведений простий консольний застосунок, що надає інтерфейс телефонної книжки. Він реалізований на основі контейнера map.
#include <iostream> #include <string> #include <map> using namespace std; int main(){ string cmd, name, phone; map <string, string> book; while ( cin >> cmd ) { if(cmd == "add") { cin >> name >> phone; book[name] = phone; cout << "Added" << endl; } else if (cmd == "find") { cin >> name; cout << name << "'s phone is " << phone[name] << endl; } else if(cmd == "del") { cin >> name; book.erase(name); cout << "Deleted" << endl; } else if(cmd == "view") { map<string,string>::iterator i; for(i = book.first(); i != book.end() ; i++) { cout << *i.first() << "\t " << *i.second << endl; } } else if(cmd == "quit") { return 0; } else { cerr << "Bad command '" << cmd << "'" << endl; } } return 0; } Класи або модулі, що реалізовують асоціативний масив або його розширення в різних мовах програмування:
- Контейнер
mapв STL- сторінка допомоги std::map на MSDN [Архівовано 23 березня 2009 у Wayback Machine.]
- сторінка допомоги std::map на SGI STL [Архівовано 23 лютого 2009 у Wayback Machine.]
- сторінка допомоги std::hashmap SGI STL [Архівовано 30 грудня 2017 у Wayback Machine.]
- Клас Hash [Архівовано 4 вересня 2011 у Wayback Machine.] в Ruby
- Модуль Array в Tcl
- Клас Dict в Python
- Клас TreeDictionary в C#
- Інтерфейс Map [Архівовано 4 березня 2016 у Wayback Machine.] в Java
- NIST's Dictionary of Algorithms and Data Structures: Associative Array [Архівовано 30 січня 2009 у Wayback Machine.]
- NIST's Dictionary of Algorithms and Data Structures: Association List [Архівовано 16 грудня 2008 у Wayback Machine.]
- Дональд Кнут. Fundamental Algorithms // The Art of Computer Programming. — 3rd. — Massachusetts : Addison–Wesley, 1997. — Т. 1. — 650 с. — ISBN 0-201-89683-4.(англ.)
- Т. Кормен; Ч. Лейзерсон; Р. Рівест; К. Стайн (2009) [1990]. 10. Елементарні структури даних. Вступ до алгоритмів (вид. 3rd). MIT Press і McGraw-Hill. ISBN 0-262-03384-4.