Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
Асоціати́вний маси́в (англ. 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.]
Див. також
Джерела
- Дональд Кнут. Fundamental Algorithms // The Art of Computer Programming. — 3rd. — Massachusetts : Addison–Wesley, 1997. — Т. 1. — 650 с. — .(англ.)
- Т. Кормен; Ч. Лейзерсон; Р. Рівест; К. Стайн (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, Інтернет
Asociati vnij masi v angl associative array abo slovnik hesh v anglijskij literaturi takozh zastosovuyutsya termini associative container map mapping hash dictionary finite map abstraktnij tip danih interfejs do shovisha danih sho dozvolyaye zberigati dani u viglyadi naboru par klyuch znachennya ta dostupom do znachen za yih klyuchem Realizaciyi asociativnih masiviv zazvichaj pidtrimuyut operaciyi dodavannya pari a takozh poshuku ta vidalennya pari za klyuchem vstaviti klyuch znachennya shukati klyuch viluchiti klyuch Peredbachayetsya sho asociativnij masiv ne mozhe mistiti dvi pari z odnakovimi klyuchami U pari k v znachennya v nazivayetsya znachennyam sho asociyuyetsya z klyuchem k Zalezhno vid realizaciyi klyuchi ta znachennya mozhut zadavatisya i mnozhinami znachen Operaciya shukati klyuch povertaye znachennya sho asociyuyetsya iz zadanim klyuchem abo yakijs specialnij ob yekt sho vkazuye na vidsutnist takogo asocijovanogo znachennya Dvi inshi operaciyi nichogo ne povertayut Zazvichaj u riznih realizaciyah asociativnogo masivu semantika i nazvi operacij mozhut vidriznyatisya Asociativnij masiv z poglyadu interfejsu zruchno rozglyadati yak zvichajnij masiv v yakomu yak indeksi mozhna vikoristovuvati ne tilki cili chisla ale i znachennya inshih tipiv napriklad ryadka Pidtrimka asociativnih masiviv z dopomogoyu standartnih zasobiv ye v bagatoh interpretovanih movah programuvannya visokogo rivnya takih yak Swift Perl PHP Python Ruby Tcl JavaScript tosho U C asociativnij masiv pidtrimuyetsya na rivni shablonnih klasiv biblioteki STL map ta sporidneni klasi PrikladiProstim prikladom asociativnogo masivu ye telefonnij dovidnik Klyuchem u comu vipadku ye sukupnist PIB adresa a znachennyam nomer telefonu Inshim prikladom mozhe buti baza danih domennih imen v Interneti yaka domennomu imeni zistavlyaye IP adresu Tut domenne im ya bude klyuchem a IP adresa znachennyam Rozshirennya asociativnogo masivuVkazani tri operaciyi chasto dopovnyuyutsya inshimi Tipovi rozshirennya vklyuchayut nastupni operaciyi ochishennya vidaliti vsi zapisi obhid probigtisya po vsih parah sho zberigayutsya minimalne klyuch znajti paru z minimalnim znachennyam klyucha maksimalne klyuch znajti paru z maksimalnim znachennyam klyucha U ostannih dvoh vipadkah neobhidno shob na klyuchah bula viznachena operaciya porivnyannya Realizaciyi asociativnogo masivuIsnuyut rizni sposobi realizaciyi asociativnogo masivu Najprostisha realizaciya mozhe gruntuvatisya na zvichajnomu masivi elementami yakogo ye pari klyuch znachennya Dlya priskorennya operaciyi poshuku mozhna uporyadkuvati elementi cogo masivu po klyuchu i zdijsnyuvati poshuk metodom dilennya navpil Ale ce zbilshit chas vikonannya operaciyi dodavannya novoyi pari oskilki neobhidno bude rozsuvati elementi masivu shob v porozhnye misce sho utvorilosya pomistiti novij zapis Najpopulyarnishi realizaciyi zasnovani na riznih derevah poshuku Tak napriklad v standartnij biblioteci STL movi S kontejner map realizovanij na osnovi chervono chornogo dereva U movah Ruby Tcl Python vikoristovuyetsya odin z variantiv hesh tablici Ye j inshi realizaciyi U kozhnoyi realizaciyi ye svoyi perevagi i nedoliki Vazhlivo shob vsi tri operaciyi vikonuvalisya yak v serednomu tak i u girshomu razi za chas O log n de n potochna kilkist par sho zberigayutsya Dlya zbalansovanih derev poshuku zokrema dlya chervono chornih derev cya umova vikonana U realizaciyah pobudovanih na hesh tablicyah serednij chas ocinyuyetsya yak O 1 sho krashe nizh v realizaciyah pobudovanih na derevah poshuku Ale pri comu ne garantuyetsya visoka shvidkist vikonannya okremoyi operaciyi chas operaciyi vstavki v girshomu vipadku ocinyuyetsya yak O n Operaciya vstavki vikonuyetsya dovgo koli koeficiyent zapovnennya staye visokim i neobhidno perebuduvati indeks hesh tablici Hesh tablici pogani takozh tim sho na yihnij osnovi ne mozhna realizuvati shvidki dodatkovi operaciyi poshuku minimalnogo ta maksimalnogo znachen i algoritm obhodu vsih zberezhenih par v poryadku zrostannya abo spadannya klyuchiv Pidtrimka asociativnih masiviv v movah programuvannyaBiblioteka STL movi C Tut privedenij prostij konsolnij zastosunok sho nadaye interfejs telefonnoyi knizhki Vin realizovanij na osnovi kontejnera map include lt iostream gt include lt string gt include lt map gt using namespace std int main string cmd name phone map lt string string gt book while cin gt gt cmd if cmd add cin gt gt name gt gt phone book name phone cout lt lt Added lt lt endl else if cmd find cin gt gt name cout lt lt name lt lt s phone is lt lt phone name lt lt endl else if cmd del cin gt gt name book erase name cout lt lt Deleted lt lt endl else if cmd view map lt string string gt iterator i for i book first i book end i cout lt lt i first lt lt t lt lt i second lt lt endl else if cmd quit return 0 else cerr lt lt Bad command lt lt cmd lt lt lt lt endl return 0 PosilannyaKlasi abo moduli sho realizovuyut asociativnij masiv abo jogo rozshirennya v riznih movah programuvannya Kontejner map v STL storinka dopomogi std map na MSDN 23 bereznya 2009 u Wayback Machine storinka dopomogi std map na SGI STL 23 lyutogo 2009 u Wayback Machine storinka dopomogi std hashmap SGI STL 30 grudnya 2017 u Wayback Machine Klas Hash 4 veresnya 2011 u Wayback Machine v Ruby Modul v Tcl Klas v Python Klas v C Interfejs Map 4 bereznya 2016 u Wayback Machine v Java Teoriya NIST s Dictionary of Algorithms and Data Structures Associative Array 30 sichnya 2009 u Wayback Machine NIST s Dictionary of Algorithms and Data Structures Association List 16 grudnya 2008 u Wayback Machine Div takozhHesh tablicyaDzherelaDonald Knut Fundamental Algorithms The Art of Computer Programming 3rd Massachusetts Addison Wesley 1997 T 1 650 s ISBN 0 201 89683 4 angl T Kormen Ch Lejzerson R Rivest K Stajn 2009 1990 10 Elementarni strukturi danih Vstup do algoritmiv vid 3rd MIT Press i McGraw Hill ISBN 0 262 03384 4