HashMap est une structure de données qui stocke les données en paires (Clé, Valeur), similaire au Dictionnaire en python si vous êtes dans ce domaine !
Pour comprendre le fonctionnement interne de Hashmap, familiarisons-nous avec les termes suivants :
HASHING:
Le hachage est le processus de conversion d’une clé donnée en une autre valeur basée sur une formule utilisant une fonction. Une fonction de hachage est utilisée pour générer la nouvelle valeur selon un algorithme mathématique. Le résultat d’une fonction de hachage est connu sous le nom de valeur de hachage ou, plus simplement, de hachage. Il est utilisé pour indexer et récupérer des éléments et pour
les algorithmes de cryptage.
Une vraie fonction de hachage doit suivre cette règle –
« La fonction de hachage doit retourner le même code de hachage à chaque fois que la fonction est appliquée sur des objets identiques ou égaux. En d’autres termes, deux objets égaux doivent produire le même code de hachage de manière cohérente. »
Tous les objets en Java héritent d’une implémentation par défaut de la fonction hashCode() définie dans la classe Object.
COLLISIONS :
Gardez à l’esprit que deux clés peuvent générer le même hachage qui peut conduire à la même adresse. Ce phénomène est connu sous le nom de collision.
Fonctions de hashMap
1. Public V get(Object key) : c’est-à-dire récupérer une valeur de la carte sur la base de la clé.
2. Public V put(K key, V value) : ou pour insérer une paire clé , valeur dans la carte.
Note : Il est généralement nécessaire de surcharger la méthode hashCode() chaque fois que la méthode equals() est surchargée, de manière à maintenir le contrat général pour la méthode hashCode(), qui stipule que des objets égaux doivent avoir des codes de hachage égaux.
HashMap in JAVA
Manières d’instancier un HashMap en java:
1. Construit une HashMap vide avec la
capacité initiale et le facteur de charge spécifiés.
public HashMap(int initialCapacity, float loadFactor)
2. Construit une HashMap vide avec la
capacité initiale spécifiée et le facteur de charge par défaut (0,75).
public HashMap(int initialCapacity)
3. Construit un HashMap vide avec la capacité initiale par défaut (16) et le facteur de charge par défaut (0.75).
public HashMap()
Facteur de charge et capacité initiale.
Une instance de HashMap possède deux paramètres qui affectent ses performances :
1. Capacité initiale
2. Facteur de charge.
Capacité initiale :
La capacité est le nombre de godets dans la table de hachage, et la capacité initiale est simplement la capacité au moment de la création de la table de hachage.
Facteur de charge :
Le facteur de charge est une mesure de la façon dont la table de hachage est autorisée à se remplir avant que sa capacité soit automatiquement augmentée. Lorsque le nombre d’entrées dans la table de hachage dépasse le produit du facteur de charge et de la capacité actuelle, la table de hachage est rehaussée (c’est-à-dire que les structures de données internes sont reconstruites) afin que la table de hachage ait environ deux fois le nombre de godets.
NOTE:
En règle générale, le facteur de charge par défaut (.75) offre un bon compromis entre les coûts de temps et d’espace. Des valeurs plus élevées diminuent le surcoût d’espace mais augmentent le coût de recherche (reflété dans la plupart des opérations de la classe HashMap, y compris get et put.
Le nombre prévu d’entrées dans la carte et son facteur de charge doivent être pris en compte lors de la définition de sa capacité initiale, de manière à minimiser le nombre d’opérations de rehash. Si la capacité initiale est supérieure au nombre maximal d’entrées divisé par le facteur de charge, aucune opération de rehash ne se produira jamais.
HashMap in Java 8
Un HashMap(de java 8) stocke les données dans plusieurs listes d’entrées liées de manière simple ou plusieurs Red BlacK Trees ou un mélange des deux , selon le seuil, également appelés buckets ou bins.
Toutes les listes/arbres sont enregistrés dans un tableau d’entrée (tableau Entry<K,V>) et la capacité par défaut de ce tableau intérieur est de 16.
Chacun des enregistrements uniques ou une paire unique de Clé et une valeur dans un HashMap est appelé comme Entry<Key,Value>.
Entry
Les HashMaps utilisent une classe interne pour stocker les données : l’Entry<K, V>.
Cette entrée est une simple paire clé-valeur avec deux valeurs supplémentaires qui sont les suivantes :
1. Une référence à une autre entrée afin qu’un HashMap puisse stocker des entrées comme des listes singulièrement liées, ou comme un Arbre avec des nœuds gauche et droit pour fournir une meilleure recherche.
2. Une valeur de hachage qui représente la valeur de hachage de la clé. Cette valeur de hachage est stockée pour éviter le calcul du hachage chaque fois que le HashMap en a besoin.
L’entrée en java 8 peut être de 2 types Nœud de LinkedList ou Nœud d’Arbre RedBlack.
*size de ceci comme discuté ci-dessus est soit défini pendant l’instanciation ou par défaut 16. Sur la base du facteur de charge, elle augmente jusqu’à deux fois la taille précédente de manière à accueillir d’autres entrées.
Nœud transitoire<K,V> table ; //contenu toutes les entrées.
Dans la table, chaque index est un nœud d’une LinkedList ou d’un RedBlackTree.
La hiérarchie d’entrée va comme ceci:
Map.Entry<K,V> → implements → Node<K,V> → extends → TreeNode<K,V>
Nœud de LinkedList:
classe statique Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next ; //pour maintenir une LinkedList.
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
TreeNode:
HashMap, en java 8 , utilise RedBlackTree après un certain seuil connu sous le nom de TREEIFY_THRESHOLD(valeur par défaut 8), car il donne une complexité temporelle dans le pire des cas de O(log n), par rapport à LinkedList qui donne la recherche en O(n).
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> { TreeNode<K,V> parent ; // liens arborescents rouge-noir
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev ; // nécessaire pour délier next lors de la suppression
boolean red;
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
Fonctionnement des fonctions HashMap
1. Elle vérifie que la clé est nulle ou non . Notez qu’il ne peut y avoir qu’une seule clé nulle dans HashMap.Si la clé est nulle , alors les clés nulles mappent toujours à hash 0, donc à l’index 0 de la table.
2. Si la clé n’est pas nulle alors, la méthode appelle la méthode hashCode() sur l’objet clé(Overriden par l’utilisateur dans la classe Key respective) et applique hashValue retournée à sa propre fonction de hachage statique pour trouver un emplacement de seau(tableau de sauvegarde) où les clés et les valeurs sont stockées sous la forme d’une classe imbriquée appelée Entry.
L’emplacement du seau est un index de l’Entry à savoir le tableau.
NOTE : nous calculons à nouveau la valeur de hachage en utilisant hash(hashValue) car elle se défend contre une fonction de hachage de mauvaise qualité.
3. La valeur de hachage finale est utilisée pour trouver l’emplacement du seau dans lequel l’objet Entry est stocké.
La complexité de get() et put() est O(1) ,en supposant que la fonction de hachage disperse correctement les éléments parmi les seaux.
Note : Comme nous savons maintenant qu’en cas de collision de hachage les objets d’entrée sont stockés comme un nœud dans une liste liée et la méthode equals() est utilisée pour comparer les clés. Cette comparaison pour trouver la bonne clé avec dans une liste liée est une opération linéaire donc dans un pire scénario la complexité devient O(n).
Pour résoudre ce problème, les éléments de hachage Java 8 utilisent des arbres équilibrés au lieu de listes liées après un certain seuil. Ce qui signifie que HashMap commence par stocker les objets d’entrée dans une liste liée, mais après que le nombre d’éléments dans un hachage devient plus grand qu’un certain seuil, le hachage passera de l’utilisation d’une liste liée à un arbre équilibré, ce qui améliorera les performances dans le pire des cas de O(n) à O(log n).
Que faire lorsque deux clés différentes ont le même code de hachage ?
4. À un index, nous pouvons avoir plusieurs valeurs puisque nous pouvons avoir des collisions dans le hachage. Pour savoir laquelle nous avons besoin, HashMap prend l’aide de equals().
Solution, la méthode equals() vient à la rescousse. Puisque le seau est un et que nous avons deux objets avec le même code de hachage .
Donc après avoir récupéré l’index de la clé, il récupère le premier nœud présent sur cet index. Le premier nœud est alors comparé à la clé en utilisant equals(), Si c’est le nœud désiré ,il renvoie la valeur directement à partir d’ici.
Else, il trouve l’instance du Node, pour déterminer si les données contenantes stockées dans cet index sont au format de liste liée ou d’arbre RedBlack.
Une fois que nous avons déterminé cela, nous parcourons la LinkedList ou l’arbre , en comparant les clés dans chaque entrées en utilisant keys.equals() jusqu’à ce qu’il retourne vrai. On renvoie alors l’objet d’entrée correspondant Value .
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.valeur;
}final Node<K,V> getNode(int hash, Object key) {
Node<K,V> tab ; //représente le tableau d’entrée
Node<K,V> first, e;
int n ; K k;/* Vérifier si la table a des entrées .*/
/* Aussi, trouver l’index sur la base du hachage calculé dans les étapes précédentes, où l’entrée est stockée soit comme liste ou nœud d’arbre.*/if ((tab = table) != null && (n = tab.length) > 0 &&(first = tab) != null) {
/*Rechercher le premier nœud dans l’index obtenu sur la base du hachage.*/
if (first.hash == hash && /* toujours vérifier le premier noeud*/
((k = first.key) == key|| (key != null && key.equals(k))))
return first;/*Si le premier noeud de cet index n’est pas la valeur que nous recherchons ,alors il va pour traverser.*/
if ((e = first.next) != null) {
if (first instance of TreeNode)
/*Fetching from Red Black Tree if starting Node on the index if of TreeNode .*/return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {/*Fetching from LinkedList if the starting node is of type Node and not of Tree.*/
if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
while ((e = e.next) != null);
}
return null;
}
PUT:
1. Elle vérifie si la clé est nulle ou non. Si la clé est nulle, alors les clés nulles correspondent toujours au hachage 0, donc à l’index 0 de la table.
2. Si la clé n’est pas nulle, la méthode appelle la méthode hashCode() sur l’objet clé (surchargée par l’utilisateur dans la classe de clé respective) et applique la valeur de hachage retournée à sa propre fonction de hachage statique pour trouver un emplacement de seau (tableau de sauvegarde) où les clés et les valeurs doivent être stockées sous la forme d’une classe imbriquée appelée Entry.L’emplacement du seau est un index de l’Entry à savoir le tableau.
3. La valeur de hachage finale est utilisée pour trouver l’emplacement du seau dans lequel l’objet Entry doit être stocké. Ensuite, les Keys sont parcourus de la même manière que celle décrite dans le get(), pour vérifier si la clé existe déjà si elle existe la valeur est remplacée par la nouvelle valeur.
Else, la taille de la liste est vérifiée,
Si elle dépasse le TREEIFY_THRESHOLD(par défaut 8), les nœuds sont restructurés en RedBlackTree et la nouvelle clé est stockée avec la valeur qu’elle contient.
Si le seuil n’est pas dépassé, la nouvelle entrée est créée avec la clé-valeur respective, et est stockée.
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true) ;}final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K,V> tab;
Node<K,V> p ;
int n, i;
if ((tab = table) = null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab) == null)
tab = newNode(hash, key, value, null);
else {
/*SAME traversing as in get()*/
Node<K,V> e ; K k;
if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0 ; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
/*Pour vérifier si le TREEIFY_THRESHOLD est dépassé ou non.*/if (binCount >= TREEIFY_THRESHOLD – 1) /* -1 pour le 1er*/
treeifyBin(tab, hash);
break;}if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}if (e != null) { /* mapping existant pour la clé*/
V oldValue = e.value;
if (!onlyIfAbsent || oldValue = null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}++modCount;
if (++size > seuil)
resize() 😉
afterNodeInsertion(evict);
return null;}
Plus à lire
Immutabilité des clés :
Pourquoi les chaînes et les entiers sont une bonne implémentation des clés pour HashMap ? Principalement parce qu’elles sont immuables ! Si vous choisissez de créer votre propre classe de clé et que vous ne la rendez pas immuable, vous risquez de perdre des données à l’intérieur du HashMap.
Rehashing:
Le rehashing est le processus de recalcul du hashcode des entrées déjà stockées (paires Clé-Valeur), pour les déplacer vers un autre hashmap de plus grande taille lorsque le seuil du facteur de charge est atteint.
Lorsque le nombre d’éléments dans le hashmap, franchit la limite du Load factor, à ce moment-là, le hashmap double sa capacité et le hashcode est recalculé des éléments déjà stockés pour une distribution uniforme des paires clé-valeur dans les nouveaux buckets.
Pourquoi c’est nécessaire ?
Après avoir doublé la capacité, que faire avec les paires clé-valeur déjà présentes dans les buckets ?
Si nous gardons les paires clé-valeur existantes telles quelles, alors doubler la capacité peut ne pas aider,parce que la complexité O(1) sera atteinte seulement si les éléments sont distribués uniformément sur tous les buckets.
Donc, pour chaque paire clé-valeur existante, le hashcode est calculé à nouveau avec l’augmentation de la capacité de hashmap comme paramètre, ce qui a pour résultat de placer l’élément soit dans le même godet, soit dans un godet différent.
.