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