La caché LRU significa Least Recently Used Cache (caché de uso menos reciente). Como el propósito de la caché es proporcionar una forma rápida y eficiente de recuperar los datos, necesita cumplir ciertos requisitos.
Algunos de los requisitos son
- Tamaño fijo: La caché necesita tener algunos límites para limitar el uso de la memoria.
- Acceso rápido: Las operaciones de inserción y búsqueda en la caché deben ser rápidas, preferiblemente en tiempo O(1).
- Reemplazo de la entrada en caso de que se alcance el límite de memoria: Una caché debe tener un algoritmo eficiente para desalojar la entrada cuando la memoria está llena.
En el caso de la caché LRU desalojamos la entrada menos utilizada recientemente, por lo que tenemos que hacer un seguimiento de las entradas utilizadas recientemente, las entradas que no se han utilizado desde hace mucho tiempo y las que se han utilizado recientemente. además la operación de búsqueda e inserción debe ser lo suficientemente rápida.
Cuando pensamos en la búsqueda O(1), la estructura de datos obvia que viene a nuestra mente es HashMap. Pero HashMap no tiene un mecanismo para rastrear qué entrada ha sido consultada recientemente y cuál no.
Para rastrear esto necesitamos otra estructura de datos que proporcione una rápida inserción, eliminación y actualización, en el caso de LRU usamos Doubly Linkedlist. La razón para elegir una lista doblemente enlazada es la eliminación, actualización e inserción de O(1) si tenemos la dirección del nodo en el que se realiza esta operación. En la que HashMap mantendrá las claves y la dirección de los Nodos de Doubly LinkedList . Y la Doubly LinkedList contendrá los valores de las claves.
Como necesitamos hacer un seguimiento de las entradas utilizadas recientemente, utilizaremos un enfoque inteligente. Vamos a eliminar el elemento de la parte inferior y añadir el elemento en el inicio de LinkedList y cada vez que se accede a cualquier entrada, se moverá a la parte superior. de modo que las entradas utilizadas recientemente estará en la parte superior y menos utilizado estará en la parte inferior.
Implementemos el LRU Cache.
Espero que el código y el tutorial sean autoexplicativos.