Table associative

Table associative

Tableau associatif

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. Ces ensembles sont bien entendu finis. 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.

Sommaire

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 base de données peut être également vue comme un ensemble de tableaux associatifs liés par les contraintes que constituent les règles d'Edgar Codd.

Structures de données pour les tableaux associatifs

Les tableaux associatifs sont le plus souvent utilisés lorsque l'opération de recherche est la plus fréquente. Pour cette raison, la conception privilégie le plus souvent cette opération, au détriment de l'efficacité de l'ajout et de l'occupation mémoire par rapport d'autres structures de données (telles que les listes d'association). Dans de rares cas, un tableau associatif peut être implémenté à un niveau matériel (voir mémoire adressable par contenu).

Représentations efficaces

Deux structures de données se montrent efficaces pour représenter les tableaux associatifs : la table de hachage et l'arbre équilibré. Les avantages et inconvénients respectifs de ces deux solutions sont les suivants :

  • Les tables de hachage ont une meilleure complexité en moyenne pour l'insertion et la recherche (O(1)), alors que les arbres équilibrés ont une meilleure complexité dans le pire des cas (O(log(n)), au lieu de O(n) pour les tables de hachage).
  • Les tables de hachage ont une représentation mémoire généralement plus compacte.
  • Les arbres équilibrés peuvent aisément fournir des structures de données persistantes, ce qui est particulièrement mis en avant dans la programmation fonctionnelle.
  • Les tables de hachage nécessitent la définition d'une bonne fonction de hachage, ce qui peut être difficile à réaliser dans certains cas, alors que les arbres équilibrés ne demandent qu'un ordre total sur les clefs. Inversement, les tables de hachages peuvent être utilisées sur des clefs non ordonnées.
  • Les arbres équilibrés préservent l'ordre des clefs, permettant notamment d'effectuer un parcours des clefs dans l'ordre ou de localiser efficacement une clé proche d'une valeur donnée. Les tables de hachage, en revanche, ne préservent pas l'ordre des clefs (lorsqu'il existe).

Listes d'association

Une manière inefficace (mais simple), de réaliser un tableau associatif est une liste d'association, liste chaînée de paires clef-valeur. La recherche consiste alors à parcourir séquentiellement la liste jusqu'à trouver une clef donnée ; elle est donc de complexité O(n). La liste d'association possède les avantages suivants :

  • Aucune fonction sur les clefs n'est nécessaire (telle qu'une relation d'ordre ou une fonction de hachage).
  • L'ajout est réalisable en temps constant (il suffit de l'effectuer en tête de liste).
  • Pour de très petits tableaux associatifs (premiers téléphones mobiles, par exemple), les listes d'associations consomment moins de mémoire que d'autres structures de données.

Représentations spécialisées

Si les clefs ont un type particulier, il est parfois possible d'obtenir de meilleurs performances en utilisant une structure de données spécialisée. Par exemple, il est possible d'utiliser un arbre de Patricia si les clefs sont des entiers (lorsque les clefs sont trop clairsemées pour qu'un tableau traditionnel puisse être utilisé). D'une manière plus générale, un trie peut être utilisé dès que les clefs ont une structure de mots. On évite alors de nombreuses comparaisons lorsque plusieurs clefs ont des préfixes communs, ce qui est le cas par exemple dans les tables de routage.

Support 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 :

#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;
}

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.

  • Portail de l’informatique Portail de l’informatique
  • Portail de la programmation informatique Portail de la programmation informatique
Ce document provient de « Tableau associatif ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Table associative de Wikipédia en français (auteurs)

Игры ⚽ Поможем написать реферат

Regardez d'autres dictionnaires:

  • Table des symboles — Une table de symboles est une centralisation des informations rattachées aux identificateurs d un programme informatique. C est une fonction accélératrice de compilation, dont l efficacité dépend de la conception. Dans une table des symboles, on… …   Wikipédia en Français

  • Associative array — In computer science, an associative array (also called a map or a dictionary) is an abstract data type composed of a collection of (key,value) pairs, such that each possible key appears at most once in the collection. Operations associated with… …   Wikipedia

  • Associative Entities — An associative entity is an element of the Entity relationship model. The database relational model doesn t offer direct support to many to many relationships, even though such relationships happen frequently in normal usage. The solution to this …   Wikipedia

  • Associative agnosia — People with associative agnosia fail in assigning meaning to an object, animal or building that they can see clearly. Most cases have injury to the occipital and temporal lobes and the critical site of injury appears to be in the left occipito… …   Wikipedia

  • Hash table — Not to be confused with Hash list or Hash tree. Unordered map redirects here. For the proposed C++ class, see unordered map (C++). Hash Table Type unsorted dictionary Invented 1953 Time complexity in big O notation Average Worst case Space …   Wikipedia

  • Control table — This simple control table directs program flow according to the value of the single input variable. Each table entry holds a possible input value to be tested for equality (implied) and a relevant subroutine to perform in the action column. The… …   Wikipedia

  • Advanced Load Address Table — The Advanced Load Address Table (ALAT) is a functional unit in the Intel Itanium processor architecture. It is implemented with an associative memory. The ALAT is used to store information related to advance load instructions, as part of the… …   Wikipedia

  • Lookup table — In computer science, a lookup table is a data structure, usually an array or associative array, often used to replace a runtime computation with a simpler array indexing operation. The savings in terms of processing time can be significant, since …   Wikipedia

  • Junction table — In database management systems following the relational model, a junction table is a table that contains common fields from two or more tables. It is on the many side of a one to many relationship with each of the other tables. Junction tables… …   Wikipedia

  • Cayley table — A Cayley table, after the 19th century British mathematician Arthur Cayley, describes the structure of a finite group by arranging all the possible products of all the group s elements in a square table reminiscent of an addition or… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”