Pouvez-vous expliquer la structure interne et le fonctionnement de HashMap en Java?

HashMap en Java est une structure de données pour stocker des paires clé-valeur avec un accès rapide par clé.

Structure interne :

• HashMap utilise un tableau de buckets.
• Pour la clé, un code de hachage (hashCode) est calculé, puis transformé en un indice du tableau.
• Dans chaque bucket, les éléments avec le même indice sont stockés, généralement sous forme de liste chaînée ou d'arbre (avec Java 8, en cas de nombreuses collisions).

Fonctionnement :

• Lors de l'insertion d'un objet, l'indice est calculé à partir du hash de la clé.
• Si le bucket est vide, l'élément y est placé.
• Si le bucket est occupé, une vérification de l'égalité des clés (equals) est effectuée pour mettre à jour la valeur ou ajouter un nouvel élément.
• Lors de la recherche par clé, l'indice est également calculé, puis les éléments du bucket sont parcourus pour trouver la correspondance.

Exemple :

HashMap<String, Integer> map = new HashMap<>();
map.put("apple", 5);
int value = map.get("apple"); // 5

Ainsi, HashMap garantit un temps d'accès amorti de O(1), mais en cas de nombreuses collisions, il peut se dégrader jusqu'à O(n).