Aller au contenu

Java — HashMap

Principe

HashMap<K, V> est la structure clé-valeur la plus utilisée en Java. Elle permet un accès en O(1) en moyenne grâce au hashing.

Fonctionnement interne

Structure

HashMap = tableau de buckets (Node[])

Chaque bucket contient une liste chaînée (ou un arbre rouge-noir si > 8 éléments).

Processus de put

  1. Calculer hashCode() de la clé
  2. Déterminer l'index du bucket : index = hash & (capacity - 1)
  3. Si le bucket est vide → insérer le nœud
  4. Si le bucket est occupé → parcourir la liste chaînée
    • si une clé equals() existe → remplacer la valeur
    • sinon → ajouter en fin de liste

Processus de get

  1. Calculer le hash de la clé
  2. Aller au bucket correspondant
  3. Parcourir la liste/arbre et comparer avec equals()

Exemple

Map<String, Integer> scores = new HashMap<>();
scores.put("Ali", 95);
scores.put("Sara", 88);

int score = scores.get("Ali"); // 95
scores.getOrDefault("Unknown", 0); // 0

Capacity et Load Factor

new HashMap<>(16, 0.75f);
//           ^capacity  ^loadFactor
Paramètre Défaut Rôle
Initial capacity 16 Taille initiale du tableau
Load factor 0.75 Seuil de remplissage avant resize

Quand size > capacity * loadFactor, la HashMap double sa capacité et rehash toutes les entrées.

Warning

Le rehashing est coûteux en O(n). Si le nombre d'éléments est connu à l'avance, initialiser avec la bonne capacité.

hashCode() et equals()

Le contrat est strict :

  • si a.equals(b) → a.hashCode() == b.hashCode() (obligatoire)
  • si a.hashCode() == b.hashCode() → a.equals(b) n'est pas garanti (collision)

Un mauvais hashCode() concentre les éléments dans peu de buckets → O(n) au lieu de O(1).

// Mauvais — toutes les clés dans le même bucket
@Override
public int hashCode() { return 1; }

// Bon — distribution uniforme
@Override
public int hashCode() { return Objects.hash(name, email); }

Null keys et values

map.put(null, "value");  // OK — une seule clé null autorisée
map.put("key", null);    // OK — valeurs null autorisées

À noter : Hashtable et ConcurrentHashMap n'acceptent pas les null.

Itération

// Par entrées
for (Map.Entry<String, Integer> entry : map.entrySet()) {
    System.out.println(entry.getKey() + " → " + entry.getValue());
}

// Par clés
for (String key : map.keySet()) { ... }

// Par valeurs
for (Integer value : map.values()) { ... }

Warning

L'ordre d'itération n'est pas garanti. Pour un ordre prévisible, utiliser LinkedHashMap (insertion) ou TreeMap (tri naturel).

Complexité

Opération Moyenne Pire cas
put O(1) O(n)
get O(1) O(n)
remove O(1) O(n)
containsKey O(1) O(n)
containsValue O(n) O(n)

Le pire cas (O(n)) survient quand toutes les clés tombent dans le même bucket. Depuis Java 8, les buckets avec plus de 8 éléments sont convertis en arbres rouge-noir → O(log n).

Thread safety

HashMap n'est pas thread-safe. En environnement concurrent :

  • utiliser ConcurrentHashMap
  • ou Collections.synchronizedMap(new HashMap<>()) (moins performant)

À retenir

  • HashMap offre O(1) en moyenne pour get/put
  • toujours redéfinir hashCode() et equals() ensemble pour les clés custom
  • pas de garantie d'ordre — utiliser LinkedHashMap ou TreeMap si nécessaire
  • pas thread-safe — utiliser ConcurrentHashMap en concurrent
  • initialiser avec la bonne capacité si le nombre d'éléments est connu

Voir aussi