LRU cache je zkratka pro Least Recently Used Cache, která evikuje nejméně používanou položku. Protože účelem vyrovnávací paměti je poskytnout rychlý a efektivní způsob načítání dat. musí splňovat určité požadavky.
Některé z požadavků jsou
- Fixní velikost:
- Rychlý přístup: Mezipaměť musí mít určité hranice, aby se omezilo využití paměti:
- Výměna záznamu v případě , že je dosaženo paměťového limitu:
V případě cache LRU evikujeme nejméně používaný záznam, takže musíme sledovat nedávno použité záznamy, záznamy, které nebyly dlouho používány a které byly použity nedávno. navíc operace vyhledávání a vkládání by měly být dostatečně rychlé.
Když přemýšlíme o O(1) vyhledávání , zřejmá datová struktura, která nás napadne, je HashMap. HashMap poskytuje O(1) vkládání a vyhledávání. ale HashMap nemá mechanismus sledování, který záznam byl nedávno dotazován a který ne.
Pro toto sledování potřebujeme jinou datovou strukturu, která poskytuje rychlé vkládání, mazání a aktualizaci, v případě LRU použijeme Doubly Linkedlist . Důvodem pro volbu Doubly LinkList je O(1) mazání , aktualizace a vkládání, pokud máme adresu uzlu, na kterém se má tato operace provést.
Takže naše implementace LRU cache bude mít HashMap a Doubly LinkedList. V níž bude HashMap uchovávat klíče a adresy uzlů Doubly LinkedList . A Doubly LinkedList bude uchovávat hodnoty klíčů.
Jelikož potřebujeme sledovat nedávno použité položky, použijeme chytrý přístup. Odstraníme prvek zespodu a přidáme prvek na začátek LinkedListu a kdykoli bude nějaká položka zpřístupněna , bude přesunuta nahoru. takže nedávno použité položky budou nahoře a nejméně použité budou dole.
Nechte implementovat LRU Cache.
Doufám, že kód a návod jsou srozumitelné.