¿Cómo se determina el tiempo de acceso a un elemento en la estructura de datos HashMap?

El tiempo de acceso a un elemento en la estructura de datos HashMap en Java generalmente se considera constante — O(1). Esto se logra mediante el uso de una función hash que convierte la clave en un índice del array donde se almacena el valor.

Sin embargo, en la práctica, el tiempo de acceso puede aumentar hasta O(n) en el peor de los casos, si hay muchas colisiones (diferentes claves con el mismo hash), y los elementos se almacenan en una lista enlazada o en un árbol dentro de una misma celda.

A partir de Java 8, para reducir el tiempo de acceso en caso de colisiones, se transforma la lista enlazada en un árbol equilibrado (TreeMap), lo que reduce el tiempo de búsqueda a O(log n) en tales casos.

Por lo tanto, el tiempo medio de acceso es cercano a O(1), pero en los peores casos puede ser O(log n) o O(n).