Middle — Middle+
¿Cuál es la complejidad temporal de obtener un elemento de un HashMap si se utiliza un árbol rojo-negro en su interior?
sobes.tech AI
Respuesta de la IA
En Java, a partir de la versión 8, si en un bucket de HashMap hay demasiadas colisiones (más de 8 elementos), la lista dentro del bucket se transforma en un árbol rojo-negro para mejorar el rendimiento.
La complejidad temporal para obtener un elemento de HashMap en este caso cambia de O(1) amortizado (al usar una lista enlazada) a O(log n), donde n es la cantidad de elementos en ese bucket (es decir, la profundidad del árbol).
Por lo tanto, al usar un árbol rojo-negro dentro del bucket, la búsqueda de un elemento se realiza en O(log n).