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.
Accès rapide aux éléments d'un dictionnaire.
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.
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 :
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.
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 :
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. | |||||
Un exemple d'utilisation de tâble de hâchage est :
import <strong>java.util</strong>.*<br> <br> <strong>java.util.Map </strong>myMap = new <strong>java.util.HashMap</strong>(10);<br> <br> myMap.<strong>put </strong>(someKey1, someValue1);<br> myMap.<strong>put </strong>(someKey2, someValue2);<br> <br> Object foundValue = myMap.<strong>get</strong> (someKey2);
hashCode() fournit un entier basé sur l'adresse mémoire interne de l'objet.