Eu estava olhando para esse problema de implementação do cache LRU, onde após o tamanho do cache estar cheio, o item menos usado recentemente é exibido e é substituído pelo novo ite

Tenho duas implementações em mente:

1). Crie dois mapas que se parecem com isso

std::map<timestamp, k> time_to_key
std::map<key, std::pair<timestamp, V>> LRUCache

Para inserir um novo elemento, podemos colocar o timestamp e o valor atuais no LRUCache. Embora quando o tamanho do cache esteja cheio, podemos remover o elemento menos recente encontrando o menor carimbo de data / hora presente emTemp_parachav e remover a chave correspondente de LRUCache. A inserção de um novo item é O (1), a atualização do registro de data e hora é O (n) (porque precisamos pesquisar ok correspondente ao registro de data e hora emTemp_parachav.

2). Tenha uma lista vinculada na qual o cache usado menos recentemente esteja presente no cabeçalho e o novo item seja adicionado no final. Quando chega um item que já está presente no cache, o nó correspondente à chave desse item é movido para o final da lista. A inserção de um novo item é O (1), a atualização do registro de data e hora é novamente O (n) (porque precisamos ir para o final da lista) e a exclusão de um elemento é O (1).

gora tenho as seguintes perguntas:

ual dessas implementações é melhor para um LRUCach

Existe outra maneira de implementar o cache LR

Em Java, devo usar o HashMap para implementar o LRUCache

Vi perguntas como implementar um cache LRU genérico e também vi perguntas como implementar um cache LRU. O cache LRU genérico é diferente do cache LRU?

Desde já, obrigado!!

EDITAR

Outra maneira (mais fácil) de implementar o LRUCache em Java é usando o LinkedHashMap e substituindo a função booleana removeEldestEntry (Map.entry eldest