LRU-cache står för Least Recently Used Cache, vilket innebär att den minst nyligen använda posten rensas ut. Eftersom syftet med cachen är att tillhandahålla ett snabbt och effektivt sätt att hämta data måste den uppfylla vissa krav.
Vissa krav är
- Fixerad storlek: Cache måste ha vissa gränser för att begränsa minnesanvändningen.
- Snabb åtkomst:
- Förbättrad åtkomst: Cache Insert and lookup operation should be fast , preferably O(1) time.
- Replace of Entry in case , Memory Limit is reached: En cache bör ha en effektiv algoritm för att avlägsna posten när minnet är fullt.
Med LRU-cache avlägsnar vi den minst nyligen använda posten, så vi måste hålla reda på nyligen använda poster, poster som inte har använts under lång tid och som har använts nyligen. HashMap ger O(1) för insättning och uppslag, men HashMap har ingen mekanism för att spåra vilken post som nyligen har frågats och vilken som inte har frågats.
För att spåra detta behöver vi en annan datastruktur som ger snabb insättning, radering och uppdatering, när det gäller LRU använder vi Doubly Linkedlist . Anledningen till att vi väljer dubbel LinkList är att vi kan ta bort, uppdatera och lägga in O(1) om vi har adressen till den nod som operationen ska utföras på.
Så vår implementering av LRU-cache kommer att ha HashMap och Doubly LinkedList. HashMap kommer att innehålla nycklarna och adresserna till noderna i Doubly LinkedList . Och Doubly LinkedList kommer att innehålla nycklarnas värden.
Vidare vi måste hålla reda på nyligen använda poster kommer vi att använda ett smart tillvägagångssätt. Vi kommer att ta bort element från botten och lägga till element i början av LinkedList och närhelst en post är tillgänglig kommer den att flyttas till toppen, så att nyligen använda poster kommer att vara på toppen och minst använda kommer att vara på botten.
Låt oss implementera LRU Cache.
Jag hoppas koden och handledningen är självförklarande.