¿Bajo qué condiciones las operaciones en HashMap tienen una complejidad temporal proporcional al tamaño de la colección?

Las operaciones en HashMap (por ejemplo, get, put) generalmente tienen una complejidad temporal amortizada de O(1). Sin embargo, en algunos casos, la complejidad puede aumentar hasta O(n), donde n es el tamaño de la colección. Esto ocurre si:

• Todas las claves caen en un solo cubo (bucket) debido a una mala función de hash, lo que conduce a una lista larga o un árbol en una sola celda.
• Las colisiones no se distribuyen uniformemente, y la estructura de datos dentro del cubo se degrada.

En Java 8 y versiones superiores, si hay demasiados elementos en un cubo, HashMap convierte la lista enlazada en un árbol equilibrado (TreeNode), lo que reduce el peor caso a O(log n), pero no a O(1).

Por lo tanto, las operaciones se vuelven proporcionales al tamaño de la colección en caso de colisiones fuertes y mala distribución de hashes.