În informatică , o matrice asociativă (numită și un dicționar sau tabel de asociere ) este un tip de date care asociază un set de chei cu un set de valori corespunzător . Fiecare cheie este asociată cu o singură valoare (cel mult): o matrice asociativă corespunde deci unei aplicații de domeniu finit în matematică.
Din punctul de vedere al programatorului, matricea asociativă poate fi văzută ca o generalizare a matricei : în timp ce matricea tradițională asociază numere întregi consecutive cu valori, matricea asociativă asociază chei de un tip arbitrar cu valori de alt tip.
Operațiunile oferite de obicei de o matrice asociativă sunt:
Tablourile asociative sunt utilizate în mod obișnuit în informatică, de exemplu în sistemul de fișiere pentru a gestiona tabelul de simboluri al compilatorului în timpul analizei lexicale, pentru a accesa memoria virtuală sau pentru a direcționa pachetele într-un router .
Vă puteți gândi la o agendă telefonică ca la o matrice asociativă, unde numele sunt chei și numerele de telefon sunt valori. Un alt exemplu este cel al unui dicționar (în sens tradițional), în care cuvintele sunt cheile și definițiile valorile. Un tabel de baze de date este, de asemenea, un tablou asociativ în care valorile sunt înregistrări complete (rânduri). O întreagă bază de date poate fi văzută ca un set de matrici asociative legate de constrângerile regulilor lui Edgar Codd .
Tablourile asociative sunt cele mai des utilizate atunci când operația de căutare este cea mai frecventă. Din acest motiv, designul favorizează cel mai adesea această operațiune, în detrimentul eficienței adăugării și a ocupării memoriei în comparație cu alte structuri de date (cum ar fi listele de asociere). În routere, pentru accesul la memoria virtuală sau, mai general, atunci când timpul de acces este foarte limitat, se poate implementa o matrice asociativă la nivel hardware (a se vedea memoria adresabilă prin conținut ).
În cele ce urmează, n desemnează numărul de elemente ale matricei asociative.
Există două structuri de date care sunt eficiente în reprezentarea matricilor asociative: tabelul hash și arborele echilibrat . Avantajele și dezavantajele respective ale acestor două soluții sunt următoarele:
Ineficient (dar mai simplu) pentru a realiza o matrice asociativă (introdusă în Lisp în 1957) este o listă de asocieri , o listă legată de perechi cheie-valoare. Căutarea constă atunci în parcurgerea listei secvențial până când se găsește o cheie dată; este deci de complexitate O ( n ). Lista asociației are următoarele avantaje:
Dacă cheile sunt de un anumit tip, uneori este posibil să se obțină performanțe mai bune prin utilizarea unei structuri de date specializate. De exemplu, este posibil să utilizați un arbore Patricia dacă tastele sunt întregi (când tastele sunt prea rare pentru a fi folosită o matrice tradițională). Mai general, un sort poate fi folosit de îndată ce tastele au o structură de cuvinte. Multe comparații sunt apoi evitate atunci când mai multe chei au prefixe comune, ceea ce este cazul de exemplu în tabelele de rutare .
Codul sursă C ++ , folosind o matrice asociativă utilizând clasa mapde biblioteca standard :
#include <map> #include <string> using namespace std; int main() { map <string, string> repertoire; repertoire["Jean Dupont"] = "01.02.03.04.05"; repertoire["François Martin"] = "02.03.04.05.06"; repertoire["Louis Durand"] = "03.04.05.06.07"; return 0; }Matricea asociativă de mai sus se mai numește dicționar, în special pentru că vă permite să faceți căutări rapide, fără a parcurge întreaga matrice.
Limbajul OCaml oferă trei tipuri de matrice asociative în biblioteca sa standard . Cea mai simplă este o listă de perechi:
# let m = ["Sally Smart", "555-9999"; "John Doe", "555-1212"; "J. Random Hacker", "553-1337"];; val m : (string * string) list = [("Sally Smart", "555-9999"); ("John Doe", "555-1212"); ("J. Random Hacker", "553-1337")] # List.assoc "John Doe" m;; - : string = "555-1212"Al doilea este un tabel hash polimorf:
# let m = Hashtbl.create 3;; val m : ('_a, '_b) Hashtbl.t = <abstr> # Hashtbl.add m "Sally Smart" "555-9999"; Hashtbl.add m "John Doe" "555-1212"; Hashtbl.add m "J. Random Hacker" "553-1337";; - : unit = () # Hashtbl.find m "John Doe";; - : string = "555-1212"În sfârșit, ultimul este un dicționar pur aplicativ (produs de arborii AVL ):
# include (Map.Make(String));; ... # let m = empty |> add "Sally Smart" "555-9999" |> add "John Doe" "555-1212" |> add "J. Random Hacker" "553-1337";; val m : string t = <abstr> # find "John Doe" m;; - : string = "555-1212"Listele de perechi și dicționare sunt structuri de date persistente, deoarece sunt pur funcționale . Tabelele Hash sunt, dimpotrivă , structuri de date imperative , mai eficiente decât listele și AVL-urile în general .
În JavaScript , matricile asociative se numesc obiecte, clasa de bază fiind denumită Object.
// définition de l'objet const agenda = { lundi: 'dodo', mardi: 'dodo', mercredi: 'resto' } // ajout dynamique de clés/valeurs agenda.jeudi = 'apero' // modification des clés/valeurs existante agenda.mardi = 'apero' delete agenda.lundi // Pour obtenir une liste des clés const jours = Object.keys(agenda) // Pour obtenir une liste des valeurs const activités = Object.values(agenda) // Plusieurs manières de faire une boucle sur ces valeurs for (const key in agenda) { const value = agenda[key] console.log(`${key} c'est ${value} : ça va être super bien`) } // ou bien Object.keys(agenda).forEach(key => { const value = agenda[key] console.log(`${key} c'est ${value} : ça va être super bien`) })Rețineți că din această notație de obiect javascript provine formatul standard de schimb de date Notare obiect JavaScript , prescurtat ca JSON .
Cod sursă PHP utilizând o matrice asociativă:
$dico = array( "lundi"=>"dodo", "mardi"=>"dodo", "mercredi"=>"resto" ); echo $dico["lundi"]; foreach($dico as $key=>$value) { echo "Le $key c'est $value."; }Același cod în Perl :
%dico = ( lundi => 'dodo', mardi => 'dodo', mercredi => 'resto' ); print "$dico{lundi}\n"; foreach $key (sort keys %dico) { print "Le $key c'est $dico{$key}.\n"; }
Ieșirea ecranului în ambele cazuri:
Cod sursă Python care creează și afișează conținutul unui tablou asociativ, mai cunoscut sub numele de dicționar:
monuments = {"La tour Eiffel": "à Paris", "La statue de la liberté": "à New-York", "Le nombre de visiteurs de la tour Eiffel": 6930000 } for clef in monuments: print("{} est {}".format(clef, monuments[clef]))
După cum arată exemplul, dicționarele pot conține orice tip de variabilă sau obiect. Această caracteristică este valabilă și pentru liste sau tupluri. Rezultatul va fi: