I datalogi er et associerende array (også kaldet en ordbog eller en associeringstabel ) en type data, der forbinder et sæt nøgler med et tilsvarende sæt værdier . Hver nøgle er forbundet med en enkelt værdi (højst): et associativt array svarer derfor til en finite domæne anvendelse i matematik.
Fra programmørens synspunkt kan den associerende matrix ses som en generalisering af matrixen : mens den traditionelle matrix forbinder fortløbende heltal med værdier, associerer den associerende matrix nøgler af en vilkårlig type med værdier af en anden.
Operationer, der normalt leveres af et associerende array, er:
Associerede arrays bruges almindeligvis inden for datalogi, for eksempel i filsystemer , til at styre symboltabellen for kompilatorer under leksikalanalyse, for at få adgang til virtuel hukommelse eller for at dirigere pakker i en router .
Du kan tænke på en telefonbog som et associerende array, hvor navne er nøgler og telefonnumre er værdier. Et andet eksempel er en ordbog (i traditionel forstand), hvor ordene er nøglerne og definitionerne værdierne. En databasetabel er også et associerende array, hvor værdierne er komplette poster (rækker). En hel database kan ses som et sæt associerende arrays bundet af begrænsningerne i Edgar Codds regler .
Associerede arrays bruges oftest, når søgningen er den hyppigste. Af denne grund favoriserer designet oftest denne operation til skade for effektiviteten ved tilføjelsen og hukommelsesbesættelsen sammenlignet med andre datastrukturer (såsom associeringslister). I routere, for at få adgang til virtuel hukommelse, eller mere generelt, når adgangstiden er meget begrænset, kan en associativ matrix implementeres på hardwareniveau (se hukommelse, der kan adresseres efter indhold ).
I det følgende betegner n antallet af elementer i det associerende array.
Der er to datastrukturer, der er effektive til at repræsentere associerende arrays: hash-tabellen og det afbalancerede træ . De respektive fordele og ulemper ved disse to løsninger er som følger:
Ineffektivt (men enklere) at foretage en associativt array (indført i Lisp i 1957) er en liste over forening , forbundet liste over nøgleværdipar. Søgningen består derefter af at gå gennem listen sekventielt, indtil en given nøgle er fundet; det er derfor af kompleksitet O ( n ). Foreningslisten har følgende fordele:
Hvis tasterne er af en bestemt type, er det undertiden muligt at opnå bedre ydeevne ved hjælp af en specialiseret datastruktur. For eksempel er det muligt at bruge et Patricia-træ, hvis nøglerne er heltal (når tasterne er for sparsomme til, at en traditionel matrix kan bruges). Mere generelt kan en slags bruges, så snart tasterne har en ordstruktur. Talrige sammenligninger undgås derefter, når flere nøgler har fælles præfikser, hvilket f.eks. Er tilfældet i rutetabeller .
Kildekode C ++ ved hjælp af et associerende array ved hjælp af klassen mapi 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; }Det associerende array ovenfor kaldes også en ordbog, især fordi det giver dig mulighed for at foretage hurtige søgninger uden at gå gennem hele arrayet.
OCaml- sproget giver tre slags associerende arrays i dets standardbibliotek . 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 anden er en polymorf hash-tabel :
# 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"Endelig er den sidste en rent applikativ ordbog (produceret af AVL træer ):
# 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øger er vedvarende datastrukturer, fordi de er rent funktionelle . Hash-tabeller er tværtimod absolut nødvendige datastrukturer , mere effektive end lister og AVL'er generelt .
I JavaScript kaldes associerende arrays objekter, hvor basisklassen navngives 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`) })Bemærk, at det er fra denne javascript-objektnotation, at standard JavaScript Object Notation -dataudvekslingsformat , forkortet JSON, kommer fra .
PHP kildekode ved hjælp af et associerende array:
$dico = array( "lundi"=>"dodo", "mardi"=>"dodo", "mercredi"=>"resto" ); echo $dico["lundi"]; foreach($dico as $key=>$value) { echo "Le $key c'est $value."; }Den samme kode 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"; }
Skærmoutput i begge tilfælde:
Python- kildekode opretter og viser indholdet af et associerende array, mere almindeligt kendt som en ordbog:
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øger indeholde enhver type variabel eller objekt. Denne egenskab gælder også for lister eller tupler. Resultatet bliver: