Dans quelles conditions les opérations dans HashMap ont-elles une complexité temporelle proportionnelle à la taille de la collection?

Les opérations dans HashMap (par exemple, get, put) ont généralement une complexité temporelle amortie de O(1). Cependant, dans certains cas, la complexité peut augmenter jusqu’à O(n), où n est la taille de la collection. Cela se produit si :

• Toutes les clés tombent dans un seul compartiment (bucket) en raison d’une mauvaise fonction de hachage, ce qui entraîne une longue liste ou un arbre dans une seule case.
• Les collisions ne sont pas réparties uniformément, et la structure de données à l’intérieur du compartiment se dégrade.

Dans Java 8 et versions supérieures, si un compartiment contient trop d’éléments, HashMap transforme la liste chaînée en un arbre équilibré (TreeNode), ce qui réduit le pire cas à O(log n), mais pas à O(1).

Ainsi, les opérations deviennent proportionnelles à la taille de la collection en cas de collisions fortes et de mauvaise distribution des hash.