Reinventarlo

Construye la caché LRU

La caché de imágenes tiene tamaño límite. Al llenarse, expulsa la imagen usada hace más tiempo. Operaciones: obtener(url) y guardar(url, imagen), las dos en O(1).

Piezas: una tabla hash y una lista doble.

Una caché de imágenes con tamaño límite expulsa, al llenarse, la imagen usada hace más tiempo. Obtener y guardar deben ser O(1). Tienes una tabla hash y una lista doble. ¿Cómo se combinan?El hash guarda la imagen y su hora de último uso; para expulsar se recorre la tabla buscando la hora más antiguaUn heap por hora de uso guarda las imágenes, y el hash solo sirve para evitar duplicados al guardarEl hash va de url al nodo de la lista, que guarda las imágenes en orden de uso; usar una imagen mueve su nodoEl hash va de url a la imagen, y la lista guarda solo las url en orden de uso; usar una imagen busca su url en la lista