HashMap

Tableau associatif

Description

En informatique, un tableau associatif (aussi appelé dictionnaire ou table d'association) est un type de données associant à un ensemble de clés un ensemble correspondant de valeurs. Chaque clé est associée à une valeur : un tableau associatif correspond donc à une injection (ou fonction injective) en mathématiques. En d'autres termes, un tableau associatif peut être vu comme un ensemble de paires {(clé,valeur)} où chaque clé ne peut apparaître qu'une seule fois.
Du point de vue du programmeur, on peut considérer le tableau associatif comme une généralisation du tableau : alors que le tableau traditionnel associe des valeurs d'un certain type à des entiers consécutifs (les indices), le tableau associatif associe des valeurs d'un type arbitraire à des clés d'un autre type.
Les opérations usuellement fournies par un tableau associatif sont :
- ajout : association d'une nouvelle valeur à une nouvelle clé ;
- modification : association d'une nouvelle valeur à une ancienne clé ;
- suppression : suppression d'une clé et de sa valeur associée ;
- recherche : détermination de la valeur associée à une clé, si elle existe ;
- liste : liste l'ensemble des clés du tableau associatif.

Exemples

Les tableaux associatifs sont utilisés couramment en informatique, par exemple dans les systèmes de fichiers ou pour gérer la table des symboles des compilateurs durant l'analyse lexicale. On peut également voir un annuaire téléphonique comme un tableau associatif, où les noms constituent les clés 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 clés 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.

Implémentation en Java

La classe HashMap en Java est une implémentation possible d'un tableau associatif.
Pour bien utiliser la classe HashMap, il est indispensable de préciser le type des clés et le type des valeurs à la déclaration et à la création de la table. Par rapport aux tableaux associatifs, la classe HashMap fournit en plus une méthode qui retourne la liste de toutes les valeurs et une méthode qui retourne la liste de toutes les paires (clé,valeur).

Pour tester votre compréhension

Pour chacune des 5 opérations sur les tableaux associatifs, pouvez vous associer la méthode de la classe HashMap qui l'implémente ?

ajout :
modification :
suppression :
recherche :
liste :

Pour vous aider, voici un exemple de programme utilisant la classe HashMap avec des cléfs et des valeurs de même type et un autre exemple de programme utilisant des types différents pour les cléfs et les valeurs.

After one or two more years at ESIEE, you'll be able to understand what is inside a HashTable as described here in English.
Cette ressource a été crée par Denis Bureau, Jean Cousty, Pierre Lefebvre et Benjamin Perret à partir entre autre de : http://fr.wikipedia.org/wiki/Tableau_associatif.