¿Cuál es la complejidad de buscar un elemento por clave en un HashMap?

La complejidad media es O(1), en el peor caso es O(n).

• Caso promedio (O(1)): Con una buena función hash y una distribución uniforme de los elementos en las cubetas, la búsqueda se reduce a calcular el hash de la clave y acceder directamente a la cubeta correspondiente del array. Dentro de la cubeta, si no hay colisiones, el elemento se encuentra en tiempo constante.
• Peor caso (O(n)): Ocurre cuando todos los elementos se hashéan en la misma cubeta. En ese caso, la búsqueda se convierte en una búsqueda lineal en una lista enlazada (o en un árbol equilibrado en Java 8+ para cubetas con muchos elementos, pero incluso recorrer el árbol puede tomar O(log n), lo que en presencia de muchas colisiones en una sola cubeta aún se acerca a O(n) respecto al número total de elementos si todos caen en la misma cubeta).

Desde Java 8, para cubetas que contienen más de un umbral determinado (TREEIFY_THRESHOLD, por defecto 8) elementos, la lista enlazada se transforma en un árbol equilibrado (Árbol Rojo-Negro). Esto mejora la peor situación de búsqueda dentro de una cubeta a O(log n), pero si todos los claves tienen el mismo hash, la búsqueda general aún puede ser cercana a O(n).