Cache de LRU para Cache Menos Usado Recentemente. que despejam a entrada menos usada recentemente. Como o propósito do Cache é fornecer uma forma rápida e eficiente de recuperação de dados. ele precisa satisfazer certos requisitos.
Alguns dos Requisitos são
- Tamanho Fixo: Cache precisa ter alguns limites para limitar o uso de memória.
- Acesso rápido: A operação de inserção e pesquisa do Cache deve ser rápida , de preferência O(1) tempo.
- Substituição de Entrada em caso de , o Limite de Memória é atingido: Uma cache deve ter um algoritmo eficiente para despejar a entrada quando a memória estiver cheia.
No caso da cache LRU despejamos a entrada menos usada recentemente, então temos que manter o controle das entradas usadas recentemente, entradas que não foram usadas há muito tempo e que foram usadas recentemente. mais a operação de busca e inserção deve ser rápida o suficiente.
Quando pensamos em O(1) lookup , a estrutura de dados óbvia vem em nossa mente é HashMap. HashMap fornece O(1) inserção e procura. mas HashMap não tem mecanismo de rastreamento qual entrada foi consultada recentemente e qual não.
Para rastrear isto nós precisamos de outra estrutura de dados que forneça rápida inserção, exclusão e updation , no caso da LRU usamos Doubly Linkedlist . A razão para escolher duplamente LinkList é O(1) delete , updation e inserção se tivermos o endereço do Node no qual esta operação tem de ser executada.
Então a nossa implementação de cache LRU terá HashMap e Doubly LinkedList. Em que HashMap terá as chaves e endereço dos Nodos da Doubly LinkedList . E a Doubly LinkedList conterá os valores das chaves.
Como precisamos manter um registro das entradas usadas recentemente, usaremos uma abordagem inteligente. Vamos remover elementos da parte inferior e adicionar elementos no início da LinkedList e sempre que qualquer entrada for acessada , ela será movida para cima. de modo que as entradas recentemente usadas estarão em cima e as menos usadas estarão em baixo.
Deixe implementar o Cache LRU.
O código de esperança e tutorial é auto-explicativo.