Quelle est la complexité de rechercher un élément par clé dans un HashMap?

La complexité moyenne est O(1), dans le pire des cas — O(n).

• Cas moyen (O(1)) : Avec une bonne fonction de hachage et une distribution uniforme des éléments dans les buckets, la recherche se réduit à calculer le hachage de la clé et accéder directement au bucket correspondant dans le tableau. À l’intérieur du bucket, si aucune collision n’est présente, l’élément est trouvé en temps constant.
• Cas worst (O(n)) : Se produit lorsque tous les éléments sont hachés dans le même bucket. Dans ce cas, la recherche devient une recherche linéaire dans une liste chaînée (ou dans un arbre équilibré en Java 8+ pour les buckets avec beaucoup d’éléments, mais même parcourir l’arbre peut prendre O(log n), ce qui, en cas de nombreuses collisions dans un seul bucket, se rapproche toujours de O(n) par rapport au nombre total d’éléments si tous tombent dans le même bucket).

Depuis Java 8, pour les buckets contenant plus d’un seuil défini (TREEIFY_THRESHOLD, par défaut 8) éléments, la liste chaînée est transformée en un arbre équilibré (arbre rouge-noir). Cela améliore la recherche dans un seul bucket à O(log n), mais si toutes les clés ont le même hash, la recherche globale peut toujours être proche de O(n).