Асоціати́вний маси́в () (або словник, хеш, в англійській літературі також застосовуються терміни 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). Операція вставки виконується довго, коли коефіцієнт заповнення стає високим і необхідно перебудувати індекс хеш-таблиці.

Хеш-таблиці погані також тим, що на їхній основі не можна реалізувати швидкі додаткові операції пошуку мінімального та максимального значень, і алгоритм обходу всіх збережених пар в порядку зростання або спадання ключів.

Підтримка асоціативних масивів в мовах програмування

Бібліотека STL мови C++ Тут приведений простий консольний застосунок, що надає інтерфейс телефонної книжки. Він реалізований на основі контейнера 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 сторінка допомоги std::map на SGI STL сторінка допомоги std::hashmap SGI STL Клас Hash в Ruby Модуль Array в Tcl Клас Dict в Python Клас TreeDictionary в C# Інтерфейс Map в Java

Теорія NIST's Dictionary of Algorithms and Data Structures: Associative Array NIST's Dictionary of Algorithms and Data Structures: Association List

Див. також Хеш-таблиця

Джерела