LRU cache stand pour Least Recently Used Cache. qui évince l’entrée la moins récemment utilisée. Comme le but du cache est de fournir un moyen rapide et efficace de récupérer des données. il doit répondre à certaines exigences.
Certaines de ces exigences sont
- Fixed Size : Le cache doit avoir certaines limites pour limiter les utilisations de la mémoire.
- Accès rapide : L’opération d’insertion et de consultation du cache doit être rapide, de préférence en temps O(1).
- Remplacement de l’entrée au cas où , la limite de mémoire est atteinte : Un cache doit avoir un algorithme efficace pour expulser l’entrée lorsque la mémoire est pleine.
Dans le cas d’un cache LRU, nous expulsons l’entrée la moins récemment utilisée, donc nous devons garder une trace des entrées récemment utilisées, des entrées qui n’ont pas été utilisées depuis longtemps et qui ont été utilisées récemment. plus l’opération de lookup et d’insertion doit être assez rapide.
Lorsque nous pensons à O(1) lookup , la structure de données évidente vient dans notre esprit est HashMap. HashMap fournit O(1) d’insertion et de recherche. mais HashMap n’a pas de mécanisme de suivi de l’entrée qui a été récemment interrogée et qui ne l’a pas été.
Pour suivre cela, nous avons besoin d’une autre structure de données qui fournit l’insertion rapide ,la suppression et la mise à jour , dans le cas de LRU nous utilisons Doubly Linkedlist . La raison du choix de la liste doublement liée est O(1) suppression, mise à jour et insertion si nous avons l’adresse du noeud sur lequel cette opération doit être effectuée.
Donc notre implémentation du cache LRU aura HashMap et Doubly LinkedList. Dans lequel HashMap tiendra les clés et l’adresse des Nœuds de Doubly LinkedList . Et Doubly LinkedList contiendra les valeurs des clés.
Comme nous devons garder la trace des entrées récemment utilisées, nous utiliserons une approche intelligente. Nous allons retirer l’élément du bas et ajouter l’élément au début de LinkedList et chaque fois qu’une entrée est accédée , elle sera déplacée vers le haut. de sorte que les entrées récemment utilisées seront en haut et les moins utilisées seront en bas.
Mettons en œuvre le cache LRU.
J’espère que le code et le tutoriel sont explicites.