Présentation générale

La collection java.util.Map définit une structure clé-valeur. Parmi ses implémentations, HashMap est la plus courante. Elle offre des performances d'accès élevées basées sur le hashCode des clés, mais n'assure aucun ordre d'itération. Une clé null est autorisée, tout comme plusieurs valeurs null. Son implémentation n'est pas thread-safe. Pour une alternative thread-safe, ConcurrentHashMap est recommandée.

Les autres implémentations notables incluent LinkedHashMap, qui préserve l'ordre d'insertion ou d'accès, et TreeMap, qui maintient les entrées triées selon la clé. Hashtable est une classe obsolète, synchronisée mais moins performante que ConcurrentHashMap.

Structure interne de HashMap en Java 8

En Java 8, HashMap utilise une combinaison de tableau, liste chaînée et arbre rouge-noir pour le stockage. Le tableau de base, appelé table, est un tableau de Node. Chaque Node contient le hash, la clé, la valeur et une référence vers le prochain nœud dans la chaîne.

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
    // ... constructeurs et méthodes ...
}

L'insertion dans la structure est déterminée par un algorithme de hash optimisé. La première étape consiste à calculer un hash à partir du hashCode() de la clé.

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

Ce hash est ensuite utilisé pour obtenir un index dans le tableau via une opération bit-à-bit (hash & (length - 1)). La longueur du tableau est toujours une puissance de 2, ce qui rend cette opération très efficace (équivalente à un modulo, mais plus rapide).

Lors de l'insertion d'une paire (put), si un nœud existe déjà à l'index calculé et que les clés ne correspondent pas, la paire est ajoutée à la fin de la chaîne. Si cette chaîne dépasse une longueur seuil (8 par défautt), elle est convertie en un arbre rouge-noir pour améliorer les performances de recherche de O(n) à O(log n).

Paramètres importants et redimensionnement

La capacité et le comportement de redimensionnement (resize) sont contrôlés par plusieurs champs :

• loadFactor (facteur de charge, par défaut 0.75) : rapport entre le nombre d'entrées et la capacité du tableau.
• threshold (seuil) : nombre maximum d'entrées avant redimensionnement. Il est calculé comme capacity * loadFactor.

Lorsque le nombre d'entrées dépasse le threshold, le tableau est redimensionné, généralement doublé en taille. La réaffectation des nœuds existants est optimisée en Java 8 : au lieu de recalculer tous les hashs, un simple test sur un bit spécifique détermine si un nœud reste à son ancien index ou est déplacé vers un nouvel index (ancien index + ancienne capacité).

Problèmes de concurrence et sécurité des threads

HashMap n'est pas conçu pour être utilisé en environnement multithread. Des opérations concurrentes, en particulier pendant un redimensionnement, peuvent corrompre la structure interne de la table et mener à des boucles infinies ou à une perte de données. L'exemple classique est la création d'une liste chaînée circulaire lors de la migration des nœuds, ce qui bloque les appels à get().

Performances : Java 8 vs Java 7

Les optimisations de Java 8 (l'arbre rouge-noir pour les longues chaînes) apportent un gain de performance significatif, surtout lorsque la fonction de hash produit des collisions. Pour un hash bien distribué, l'amélioration peut être de 15% ou plus. Dans le pire des cas (toutes les clés ont le même hash), la complexité passe de O(n) en Java 7 à O(log n) en Java 8 grâce à l'arbre, offrant une stabilité bien meilleure avec l'augmentation de la taille de la map.

Recommandations

1. Pré-dimensionnement : Estimez la taille finale de votre map et initialisez-la avec une capacité suffisante pour éviter des redimensionnements coûteux.
2. Facteur de charge : Ne le modifiez pas sans raison. Le défaut (0.75) offre un bon compromis entre espace mémoire et temps de recherche.
3. Thread-safety : Évitez HashMap dans un contexte multithread. Privilégiez ConcurrentHashMap.
4. Mise à jour JDK : L'implémentation optimisée de HashMap en Java 8 est une raison valable pour migrer depuis des versions antérieures.