Complejidad Temporal
Mejor: O(1)
Prom: O(1)
Peor: O(n)
Una caché LRU (Least Recently Used) guarda un número fijo de entradas y desaloja la que lleva más tiempo sin usarse cuando se queda sin espacio. El reto es hacer get y put en O(1).
Por qué una sola estructura no basta:
1. Un hash map solo da acceso O(1) pero no sabe qué entrada es la más antigua
2. Una lista ordenada sola sabe cuál es la más antigua pero tarda O(n) en buscar una clave
3. Así que se combinan: el map responde "dónde", la lista responde "cuándo"
El diseño:
Hash map: clave → puntero a un nodo, O(1)
Lista doblemente enlazada: head = más reciente, tail = próximo a desalojar
Dos detalles fáciles de pasar por alto:
Cada nodo guarda su propia clave. El desalojo llega al nodo
por la cola de la lista, y necesita la clave para borrar la
entrada del map — si no, el map se queda con un huérfano.
La lista debe ser doblemente enlazada. Mover un nodo al
frente implica desenlazarlo del medio, y eso necesita su
puntero prev. Con una lista simple sería O(n).
Complejidad Temporal:
Mejor: O(1) para get y put
Promedio: O(1) — búsqueda hash más reenlazado constante de punteros
Peor: O(n) solo si todas las claves colisionan en el hash map
Complejidad Espacial: O(capacidad)
Aplicaciones: cachés de bases de datos y web, desalojo en Redis (aproximación por muestreo), reemplazo en cachés de CPU, historial atrás/adelante del navegador, memoización con memoria acotada
Algoritmos relacionados
Preguntas frecuentes
- ¿Qué es Caché LRU (LRU Cache)?
- Una caché LRU (Least Recently Used) guarda un número fijo de entradas y desaloja la que lleva más tiempo sin usarse cuando se queda sin espacio. El reto es hacer get y put en O(1).
- ¿Cuál es la complejidad de Caché LRU (LRU Cache)?
- Tiempo (promedio): O(1) — búsqueda hash más reenlazado constante de punteros · Espacio: O(capacidad)
- ¿Para quién es este visualizador de Caché LRU (LRU Cache)?
- La visualización de Caché LRU (LRU Cache) está pensada para nivel avanzado, dentro de la categoría Estructuras de Datos. Ideal para estudiantes, entrevistas técnicas y repaso práctico.
- ¿Qué algoritmos relacionados hay con Caché LRU (LRU Cache)?
- En la misma categoría (Estructuras de Datos) puedes explorar: Stack, Queue, Linked List. Todos tienen visualización interactiva.