I informatikk er en assosiativ matrise (også kalt en ordbok eller assosiasjonstabell ) en type data som forbinder et sett med nøkler med et tilsvarende sett med verdier . Hver nøkkel er knyttet til en enkeltverdi (høyst): en assosiativ matrise tilsvarer derfor en endelig domene anvendelse i matematikk.
Fra programmererens synspunkt kan den assosiative matrisen sees på som en generalisering av matrisen : mens den tradisjonelle matrisen assosierer fortløpende heltall med verdier, assosierer den assosiative matrisen nøkler av en vilkårlig type med verdier av en annen.
Operasjonene som vanligvis tilbys av en assosiativ matrise er:
Assosiative matriser brukes ofte i informatikk, for eksempel i filsystemer , for å administrere symboltabellen til kompilatorer under leksikalanalyse, for å få tilgang til virtuelt minne eller for å rute pakker i en ruter .
Du kan tenke på en telefonbok som en assosiativ matrise, der navn er nøkler og telefonnumre er verdier. Et annet eksempel er en ordbok (i tradisjonell forstand), der ordene er nøklene og definisjonene verdiene. En databasetabell er også en assosiativ matrise der verdiene er komplette poster (rader). En hel database kan sees på som et sett med assosiative matriser bundet av begrensningene i Edgar Codds regler .
Assosiative matriser brukes oftest når søkeoperasjonen er den hyppigste. Av denne grunn favoriserer designet oftest denne operasjonen, til skade for effektiviteten av tillegget og minnebesetningen sammenlignet med andre datastrukturer (for eksempel tilknytningslister). I rutere, for tilgang til virtuelt minne, eller mer generelt når tilgangstid er svært begrenset, kan en assosiativ matrise implementeres på maskinvarenivå (se minne adresserbart av innhold ).
I det følgende betegner n antall elementer i den assosiative matrisen.
Det er to datastrukturer som er effektive for å representere assosiative matriser: hasjtabellen og det balanserte treet . De respektive fordelene og ulempene med disse to løsningene er som følger:
Ineffektivt (men enklere) å utføre en assosiativ matrise (introdusert i Lisp i 1957) er en liste over tilknytning , koblet liste over nøkkelverdipar. Søket består da av å gå gjennom listen sekvensielt til en gitt nøkkel blir funnet; det er derfor av kompleksitet O ( n ). Foreningslisten har følgende fordeler:
Hvis tastene er av en bestemt type, er det noen ganger mulig å oppnå bedre ytelse ved å bruke en spesialisert datastruktur. Det er for eksempel mulig å bruke et Patricia-tre hvis tastene er heltall (når tastene er for sparsomme til at en tradisjonell matrise kan brukes). Mer generelt kan en sortering brukes så snart tastene har en ordstruktur. Tallrike sammenligninger unngås da når flere nøkler har vanlige prefikser, noe som for eksempel er i rutetabeller .
Kildekode C ++ ved hjelp av en assosiativ matrise som bruker klassen maptil standardbiblioteket :
#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; }Den assosiative matrisen ovenfor kalles også en ordbok, spesielt fordi den lar deg gjøre raske søk uten å gå gjennom hele matrisen.
OCaml- språket gir tre typer assosiative matriser i standardbiblioteket . Den enkleste er en liste over par:
# 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"Den andre er en polymorf hash-tabell :
# 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"Til slutt er den siste en rent applikativ ordbok (produsert av AVL-trær ):
# 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"Lister over par og ordbøker er vedvarende datastrukturer fordi de er rent funksjonelle . Hash-tabeller er tvert imot tvingende datastrukturer , mer effektive enn lister og AVL-er generelt .
I JavaScript kalles assosiative matriser objekter, og baseklassen blir navngitt 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`) })Merk at det er fra denne javascript-objektnotasjonen at standard JavaScript Object Notation datautvekslingsformat , forkortet JSON, kommer fra .
PHP kildekode ved hjelp av en assosiativ matrise:
$dico = array( "lundi"=>"dodo", "mardi"=>"dodo", "mercredi"=>"resto" ); echo $dico["lundi"]; foreach($dico as $key=>$value) { echo "Le $key c'est $value."; }Den samme koden i 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"; }
Skjermutgang i begge tilfeller:
Python- kildekode oppretter og viser innholdet i en assosiativ matrise, mer kjent som en ordbok:
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]))
Som eksemplet viser, kan ordbøker inneholde alle typer variabler eller objekter. Denne egenskapen gjelder også for lister eller tupler. Resultatet blir: