Matrice asociativă

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 26 iulie 2020; verificările necesită 6 modificări .

O matrice asociativă este un tip de date abstract ( o interfață către un depozit de date) care vă permite să stocați perechi de forma „(cheie, valoare)” și suportă operațiunile de adăugare a unei perechi, precum și căutarea și ștergerea unei perechi prin cheie:

INSERT(cheie, valoare)
FIND(cheie)
REMOVE(cheie)

Se presupune că o matrice asociativă nu poate stoca două perechi cu aceleași chei.

Într-o pereche , valoarea se numește valoarea asociată cheii . Unde este cheia , a este valoarea . Semantica și numele operațiilor de mai sus pot diferi în diferite implementări ale matricei asociative. $(k, v)$ $v$ $k$ $k$ $v$

Operația FIND(cheie) returnează valoarea asociată cu cheia dată sau un obiect UNDEF special care indică faptul că nu există nicio valoare asociată cu cheia dată. Celelalte două operațiuni nu returnează nimic (cu excepția, poate, dacă operația a avut succes sau nu).

Din punctul de vedere al interfeței, este convenabil să se considere o matrice asociativă ca o matrice obișnuită , în care nu numai numerele întregi, ci și valori de alte tipuri, cum ar fi șirurile de caractere, pot fi folosite ca indici.

Suportul pentru tablourile asociative se găsește în multe limbaje de programare interpretate la nivel înalt , cum ar fi Perl , PHP , Python , Ruby , Tcl , JavaScript [1] și altele. Pentru limbile care nu au matrice asociative încorporate, există multe implementări sub formă de biblioteci .

Un exemplu de matrice asociativă este un director telefonic: în acest caz, valoarea este combinația „ Nume complet + adresă”, iar cheia este numărul de telefon, un număr de telefon are un singur proprietar, dar o persoană poate avea mai multe numere .

Cele trei operațiuni principale sunt adesea completate de altele, cele mai populare extensii fiind:

CLEAR - ștergeți toate intrările
EACH - „rulează” prin toate perechile stocate,
MIN - găsiți perechea cu valoarea minimă a cheii,
MAX - găsiți perechea cu valoarea maximă a cheii.

În ultimele două cazuri, este necesar ca operația de comparare să fie definită pe taste.

Implementări de matrice asociative

Există multe implementări diferite ale unui tablou asociativ.

Cea mai simplă implementare se poate baza pe o matrice obișnuită ale cărei elemente sunt perechi (cheie, valoare). Pentru a accelera operația de căutare, puteți sorta elementele acestei matrice după cheie și puteți efectua o metodă de căutare binară . Dar acest lucru va crește timpul de execuție al operației de adăugare a unei noi perechi, deoarece va fi necesar să „împingeți” elementele matricei pentru a plasa o nouă intrare în celula goală rezultată.

Cele mai populare implementări se bazează pe diferiți arbori de căutare . Deci, de exemplu, în biblioteca standard STL a limbajului C++ , containerul hărții este implementat pe baza unui arbore roșu-negru . Limbile D , Java , Ruby , Tcl , Python folosesc una dintre variantele tabelului hash . Există și alte implementări.

Fiecare implementare are propriile sale avantaje și dezavantaje. Este important ca toate cele trei operațiuni să fie efectuate atât în medie, cât și în cel mai rău caz în timp , unde este numărul curent de perechi stocate. Pentru arbori de căutare echilibrați (inclusiv arbori roșu-negru), această condiție este îndeplinită. $O(\log n)$ $n$

În implementările bazate pe tabele hash, timpul mediu este estimat ca , ceea ce este mai bun decât în implementările bazate pe arbori de căutare. Dar acest lucru nu garantează o viteză mare de execuție a unei singure operații: timpul operației INSERT este estimat cel mai rău ca . Operația INSERT durează mult timp când factorul de umplere devine ridicat și indexul tabelului hash trebuie reconstruit. $O(1)$ $Pe)$

Tabelele hash sunt, de asemenea, proaste, deoarece nu pot fi folosite pentru a implementa operațiuni suplimentare rapide MIN, MAX și un algoritm pentru ocolirea tuturor perechilor stocate în ordinea crescătoare sau descrescătoare a cheilor.

Note

↑ În JavaScript , obiectele acceptă crearea de proprietăți cu o cheie arbitrară (șir), deci implementează și proprietățile de bază ale unui tablou asociativ. Vezi: Obiecte ca tablouri asociative . Tutorial JavaScript . Data accesului: 20 decembrie 2012. Arhivat din original la 23 decembrie 2012. (nedefinit)

Link -uri

Tipuri de date
Ininterpretabil	Pic Ciuguli octet qubit Trata Trăsătură Cuvânt
Numeric	Întreg punct fix punctul de plutire Raţional Complex Lung interval
Text	Simbolic Şir
Referinţă	Abordare Legătură Indicator Înveliș
Compozit	Tip de date algebrice ( generic ) Clasă Tip produs ( Scrie Tuplu structura ) Un obiect Consolidare ( etichetat ) Pereche comandată
abstract	matrice Listă Întoarce-te Grămadă Matrice asociativă (afișare, hartă ) Multe multiset Tip Grafic
Alte	Logic Inferior Superior Polimorfă Funcţional enumerabil Colectie Excepție Gen ( Metaclasă ) Monadă Semafor curgere gol
subiecte asemănătoare	Tip de date abstracte tip primitiv Structură de date Generic variabilă de tip Interfață Constructor (OOP) Constructor (FP) Constructor de tip Tip turnare Prototip Tip sistem