La cache LRU sta per Least Recently Used Cache. Poiché lo scopo della cache è quello di fornire un modo veloce ed efficiente di recuperare i dati, è necessario soddisfare determinati requisiti: La cache deve avere dei limiti per limitare l’uso della memoria.
In caso di cache LRU espelliamo la voce usata più di recente, quindi dobbiamo tenere traccia delle voci usate di recente, voci che non sono state usate da molto tempo e che sono state usate di recente. inoltre le operazioni di ricerca e inserimento dovrebbero essere abbastanza veloci.
Quando pensiamo a O(1) di ricerca, la struttura dati ovvia che ci viene in mente è HashMap. HashMap fornisce O(1) per l’inserimento e la ricerca. ma HashMap non ha un meccanismo di tracciamento di quale voce è stata interrogata di recente e quale no.
Per tracciare questo abbiamo bisogno di un’altra struttura dati che fornisca inserimento, cancellazione e aggiornamento veloci, nel caso di LRU usiamo Doubly Linkedlist. La ragione per la scelta di Doublely LinkList è O(1) cancellazione, aggiornamento e inserimento se abbiamo l’indirizzo del nodo su cui questa operazione deve essere eseguita.
Quindi la nostra implementazione della cache LRU avrà HashMap e Doubly LinkedList. In cui HashMap conterrà le chiavi e l’indirizzo dei nodi di Doubly LinkedList. E Doubly LinkedList conterrà i valori delle chiavi.
Come abbiamo bisogno di tenere traccia delle voci usate di recente, useremo un approccio intelligente. Rimuoveremo l’elemento dal fondo e aggiungeremo l’elemento all’inizio della LinkedList e ogni volta che si accede a qualsiasi voce, sarà spostata in alto. in modo che le voci usate di recente saranno in alto e quelle meno usate saranno in basso.
Implementiamo la LRU Cache.
Spero che il codice e il tutorial siano auto esplicativi.