devstory

Le Tutoriel de Java HashMap

  1. HashMap
  2. Comment fonctionne-t-il HashMap?

1. HashMap

HashMap<K,V> est une classe de Java Collection Framework implémentant l'interface Map<K,V>. HashMap dispose de l'intégralité de fonctionnalités spécifiées dans l'interface de Map, y compris les fonctionnalités facultatives.
HashMap permet de stocker des paires clé et valeur. Les clés ne peuvent pas être dupliquées.
public class HashMap<K,V> extends AbstractMap<K,V>
                      implements Map<K,V>, Cloneable, Serializable
Les caractéristiques de HashMap:
  • HashMap contient des paires clé et valeur.
  • Il peut avoir une clé null et plusieurs valeurs null.
  • HashMap ne maintient pas l'ordre des clés.
  • Il fonctionne sur la base de la technique de hachage. (Voir plus d'explications sur cette technique ci-dessous).
Observer un exemple simple: on utilise HashMap pour simuler un répertoire dans lequel le numéro de téléphone est la clé et le nom du propriétaire est la valeur. Les clés ne sont jamais dupliquées.
HashMapEx1.java
package org.o7planning.hashmap.ex;

import java.util.HashMap;
import java.util.Map;
import java.util.Set;
 
public class HashMapEx1 {
 
    public static void main(String[] args) {
        Map<String, String> phonebook = new HashMap<String, String>();
 
        phonebook.put("01000005", "Tom");
        phonebook.put("01000002", "Jerry");
        phonebook.put("01000003", "Tom");
        phonebook.put("01000004", "Donald");
        
        Set<String> phoneNumbers = phonebook.keySet();
 
        for (String phoneNumber : phoneNumbers) {
            String name = phonebook.get(phoneNumber);
            
            System.out.println("Phone Number: " + phoneNumber + " ==> Name: " + name);
        }
    }
}
Output:
Phone Number: 01000004 ==> Name: Donald
Phone Number: 01000003 ==> Name: Tom
Phone Number: 01000005 ==> Name: Tom
Phone Number: 01000002 ==> Name: Jerry
En règle générale, toutes les fonctionnalités de HashMap sont conformes à la spécification de l'interface Map, vous pouvez donc lire l'article ci-dessous sur Map pour mieux comprendre la manière d'utilisation de HashMap:
Voir aussi: La classe WeakHashMap est une variante de mémoire économe de la classe HashMap. Les mappages qui ne s'avèrent pas réellement nécessaires seront automatiquement supprimé par Java Garbage Collector(le collecteur d'ordures de Java).

2. Comment fonctionne-t-il HashMap?

Les développeurs Java ont utilisé la technique de hachage à l'égard de la classe HashMap pour stocker des données et améliorer ses performances. Observer comment cette technique est utilisée dans HashMap. On analyse essentiellement ce qui se passe lorsque l'on appelle ces méthodes: HashMap.put(K,V), HashMap.get(K) et HashMap.remove(key).
HashMap<K,V> gère un tableau d'objets Node<K,V> qui seront remplacés par un autre plus grand tableau si tous ses éléments ont reçu une valeur.
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
La classe Node<K,V> se compose de 4 champs (field). Le champ next est une référence à l'objet Node suivant. Il ne s'agit probablement pas le prochain élément du tableau.
static class Node<K,V> implements Map.Entry<K,V> {
    int hashcode;
    K key;
    V value;
    Node<K,V> next;
}
HashMap garantit que ce(s) Node(s) ayant le même hashcode auront des références consécutives. Cela l'aide à trouver rapidement tous les Node(s) avec le même hashcode spécifié.
HashMap.put(key,value)
Au cours de l'appel de la méthode HashMap.put(key,value), HashMap recherche Node avec la condition node.hashcode == hash(key). Si aucune correspondance n'est trouvée, un nouvel objet Node est affecté au tableau. (Voir l'image ci-dessous).
Sinon, HashMap identifie rapidement ces Node(s) consécutifs satisfaisant à la condition node.hashcode == hash(key) et réduit considérablement la portée du ou des Node(s) à rechercher par key.
  • Si le Node correspondant à key est trouvé, une nouvelle valeur sera affectée à Node.value.
  • Sinon, un nouvel objet Node est créé et affecté au tableau (Voir l'image ci-dessous).
HashMap.get(key)
Lorsque la méthode HashMap.get(key) est convoquée, HashMap identifie rapidement les Node(s) consécutifs qui satisfont à la condition node.hashcode == hash(key), ce qui réduit considérablement la portée du ou des Nodes(s) à rechercher par key. Ensuite, il recherche Node par key et renvoie node.value s'il est trouvé, sinon il renvoie null.
HashMap.remove(key)
Conclusion: La méthode Object.hashcode() renvoie le hashcode d'un objet, qui est généré par JVM par défaut, et rarement dupliqué. Les sous-classes de la classe Object peuvent remplacer cette méthode pour renvoyer un hashcode personnalisé.
HashMap utilise une technique de hachage pour améliorer ses performances, car comparer 2 nombres est toujours plus rapide que de le faire entre 2 objets.

Tutoriels de Java Collections Framework

Show More

Articles les plus récents

Show More