Hash table : littéralement tableau de hâchage, mais l'anglicisme "table" de hâchage est le plus souvent utilisé.

Ou "tableau associatif" (associative array) : associant une clé à une valeur.

Besoin

Accès rapide aux éléments d'un dictionnaire.

Analyse

Une table de hâchage est une structure de données possible pour un dictionnaire.

L'hypothèse de base d'un tableau de hâchage est que le moyen le plus rapide pour retrouver des éléments dans un tableau est de connaître leur indice : si je veux savoir si x est dans le tableau, je cherche si l'élement tableau[x] est pris ou non. De même, si je veux insérer x dans le tableau, je remplis tableau [x]. Le principe se révèle particulièrement efficace, avec une performancede O(1).

Les clés d'un dictionnaire n'étant pas forcément des indices de tableau, une fonction de hâchage (hash function) est chargée d'associer à toute clé un entier représentant cet indice.

Conception

On associe les clés à des cases du tableau à l'aide d'une fonction de hâchage (hash function). Suivant cette fonction, des collisions peuvent intervenir entre éléments différents affectés à la même case. La résolution de ces collisions peut être réalisée par un :

  • adressage ouvert : toutes les cases possibles sont dans le tableau (consommateur en mémoire)
  • chaînée: stockage des collisions dans une structure annexe (souvent une liste chaînée)

Un tableau de hâchage utilise généralement une répartition en listes (slots). Le nombre de slots par élément du tableau (élements/slots) détermine alors le facteur de charge (load factor) du tableau de hâchage, qui détermine le compromis performance/consommation mémoire.

Le hâchage peut être dynamique : le tableau grandit au fur et à mesure que l'on y place des éléments (voire rétrécit au fur et à mesure que l'on en enlève). La fonction de hâchage doit alors varier en conséquence.

Implémentation

L'API Java propose des classes de tableaux de hâchage depuis ses débuts, au sein de son package java.util. Ces classes examinent sur les objets-clés qu'on leur fournit :

  • la fonction de hâchage implémentée par la méthode hashCode() des clés.
  • equals() pour comparer les clés entre elles.
Tableau de hâchage Java Version 1
Commentaire
Release 0 1 2 3 4 5
Elément Fixpack 2
Hashtable Oui Obsolète Thread-safe (synchronisé).
HashMap Non Oui Implémente une interface de dictionnaire (java.util.Map). Non thread-safe par défaut.
HashSet Non Oui Ensemble (set) implémenté avec une HashMap. Non thread-safe par défaut.
WeakHashMap Non Oui Tableau de hâchage avec des clés faibles (weak). Non thread-safe par défaut.
IdentityHashMap
Non Oui Utilisant l'égalité de références (==) au lieu de l'égalité de contenu (equals()) pour la comparaison des clés (et valeurs). Non thread-safe par défaut.
LinkedHashMap
Non Oui Dictionnaire à ordre d'itération prédictible. Non thread-safe par défaut.
LinkedHashSet Non Oui Ensemble à ordre d'itération prédictible. Non thread-safe par défaut.

Exemples

Un exemple d'utilisation de tâble de hâchage est :

import java.util.*

java.util.Map myMap = new java.util.HashMap(10);

myMap.put (someKey1, someValue1);
myMap.put (someKey2, someValue2);

Object foundValue = myMap.get (someKey2);

Limitations

  • Rentabilité mémoire peut être faible (dépend du facteur de charge).

Notes

  • Souvent appellé "table" de hâchage en oubliant de traduire l'anglais "table" par "tableau".
  • Par défaut hashCode() fournit un entier basé sur l'adresse mémoire interne de l'objet.
  • Une fonction de hâchage "parfaite" (ne provoquant jamais de collisions) fait correspondre un entier différent à chaque clé.