Асоціативний масив

Асоціати́вний маси́в (англ. 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;
}

Посилання

Класи або модулі, що реалізовують асоціативний масив або його розширення в різних мовах програмування:

• Контейнер 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.