Tableau associatif - Définition
La liste des auteurs de cet article est disponible ici.
Introduction
En informatique, un tableau associatif (aussi appelé dictionnaire ou table d'association) est un type de données associant à un ensemble de clefs un ensemble correspondant de valeurs. Chaque clef est associée à une valeur : un tableau associatif correspond donc à une fonction d'injection en mathématiques.
Du point de vue du programmeur, le tableau associatif peut être vu comme une généralisation du tableau : alors que le tableau traditionnel associe des entiers consécutifs à des valeurs d'un certain type, le tableau associatif associe des valeurs d'un type arbitraire à des valeurs d'un autre type.
Les opérations usuellement fournies par un tableau associatif sont :
- ajout : association d'une nouvelle valeur à une nouvelle clef ;
- modification : association d'une nouvelle valeur à une ancienne clef ;
- suppression : suppression d'une clef ;
- recherche : détermination de la valeur associée à une clef, si elle existe.
Exemples
On peut voir un annuaire téléphonique comme un tableau associatif, où les noms constituent les clefs et les numéros de téléphone les valeurs. Un autre exemple est celui d'un dictionnaire (au sens traditionnel), où les mots sont les clefs et les définitions les valeurs. Une table de base de données constitue également une sorte de tableau associatif dans lequel les valeurs sont des enregistrements complets. Une base de données entière peut être vue comme un ensemble de tableaux associatifs liés par les contraintes que constituent les règles d'Edgar Codd.
Prise en charge dans les langages de programmation
PHP et Perl
Code source PHP utilisant un tableau associatif :
$dico = array( "lundi"=>"dodo", "mardi"=>"dodo", "mercredi"=>"resto" ); echo $dico["lundi"]; foreach($dico as $key=>$value) { echo "Le $key c'est $value."; }
Le même code en Perl :
%dico = qw ( lundi dodo mardi dodo mercredi resto ) ; print "$dico{lundi}\n"; foreach $key (sort keys %dico) { print "Le $key c'est $dico{$key}.\n"; }
Sortie écran dans les deux cas :
dodo Le lundi c'est dodo Le mardi c'est dodo Le mercredi c'est resto
C++
Code source C++ utilisant un tableau associatif via la classe map de la bibliothèque standard :
Le tableau associatif ci-dessus est aussi appelé dictionnaire notamment parce qu'il permet de faire des recherches rapides, sans parcourir le tableau entier.
Objective Caml
Le langage Objective Caml fournit trois sortes de tableaux associatifs dans sa bibliothèque standard. La plus simple est une liste de paires :
# 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"
La seconde est une table de hachage polymorphe :
# 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"
Enfin, la dernière est un dictionnaire purement applicatif (réalisé par des arbres AVL) :
# include (Map.Make(String));; ... # let m = add "Sally Smart" "555-9999" empty let m = add "John Doe" "555-1212" m let m = add "J. Random Hacker" "553-1337" m;; val m : string t = <abstr> # find "John Doe" m;; - : string = "555-1212"
Les listes de paires et les dictionnaires sont des structures de données persistantes, car purement fonctionnelles. Les tables de hachage sont au contraire des structures de données impératives, de meilleure efficacité que les listes et les AVL en général.
