Асоціати́вний маси́в (англ. associative array) (або словник, хеш, в англійській літературі також застосовуються терміни associative container, map, mapping, hash, dictionary, finite map) — абстрактний тип даних (інтерфейс до сховища даних), що дозволяє зберігати дані у вигляді набору пар ключ — значення та доступом до значень за їх ключем.
Реалізації асоціативних масивів зазвичай підтримують операції додавання пари, а також пошуку та видалення пари за ключем:
- вставити (ключ, значення)
- шукати (ключ)
- вилучити (ключ)
Передбачається, що асоціативний масив не може містити дві пари з однаковими ключами. У парі (k, v) значення v називається значенням, що асоціюється з ключем k. Залежно від реалізації, ключі та значення можуть задаватися і множинами значень.
Операція шукати(ключ)
повертає значення, що асоціюється із заданим ключем, або якийсь спеціальний об'єкт, що вказує на відсутність такого асоційованого значення. Дві інші операції нічого не повертають. Зазвичай, у різних реалізаціях асоціативного масиву семантика і назви операцій можуть відрізнятися.
Асоціативний масив з погляду інтерфейсу зручно розглядати як звичайний масив, в якому як індекси можна використовувати не тільки цілі числа, але і значення інших типів, наприклад, рядка.
Підтримка асоціативних масивів з допомогою стандартних засобів є в багатьох інтерпретованих мовах програмування високого рівня, таких як Swift, Perl, PHP, Python, Ruby, Tcl, JavaScript тощо. У асоціативний масив підтримується на рівні шаблонних класів бібліотеки 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 [ 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
- Модуль в Tcl
- Клас в Python
- Клас в 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.]
Див. також
Джерела
- Томас Кормен; Чарльз Лейзерсон, Рональд Рівест, Кліфорд Стайн (2009) [1990]. 10. Елементарні структури даних. Вступ до алгоритмів (вид. 3rd). MIT Press і McGraw-Hill. ISBN .
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет