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

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

Посилання

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

Теорія

Див. також

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.