Implementando um Cache LRU em Java: Uma Abordagem Simples com LinkedHashMap

Introdução

Para desenvolvedores de software, especialmente aqueles buscando ingressar em big techs, entender e implementar um cache LRU (Least Recently Used) é um conhecimento essencial. De acordo com o LeetCode, a implementação de um LRU cache é um desafio comum em entrevistas técnicas, dado o seu papel crítico em otimizar o acesso a dados em sistemas com restrições de memória. Neste artigo, exploraremos como implementar um cache LRU (Least Recently Used) em Java utilizando a classe LinkedHashMap.

O que é um cache?

Um cache é uma camada de armazenamento de alta velocidade que armazena uma quantidade limitada de dados. A ideia central é reduzir o tempo de acesso aos dados, evitando operações mais lentas de I/O ou operações repetitivas.

A implementação de cache é um pilar fundamental para otimização de desempenho em sistemas computacionais e é amplamente utilizada em diversas áreas da computação.

O que é o LRU Cache?

LRU, ou Least Recently Used, é um algoritmo de cache que descarta o item menos utilizado recentemente quando o cache está cheio e um novo item precisa ser adicionado. Ele é ideal para situações onde os dados mais antigos são menos prováveis de serem usados novamente.

Imagine um sistema de recomendação de produtos em um site de vendas. Esse serviço precisa acessar rapidamente informações sobre produtos que os usuários visualizaram ou compraram para fazer recomendações de itens semelhantes aos usuários. No entanto, com milhões de produtos e usuários, não é viável manter todas as informações na memória principal.

Neste exemplo, um cache LRU pode ser utilizado para armazenar detalhes dos produtos mais recentemente visualizados ou comprados. Quando um usuário navega pelo site, o serviço pode rapidamente recuperar informações dos produtos a partir do LRU cache para fornecer recomendações personalizadas.

Implementação do LRU Cache

O LRU Cache pode ser implementado utilizando uma lista duplamente encadeada junto a um HashMap, porém, em Java esta implementação pode ser abstraida utilizando a classe LinkedHashMap, que internamente implementa um lista duplamente encadeada para manter a ordem dos elementos, e um HashMap para armazenar as chaves e valores, proporcionando acesso rápido aos elementos.

Implementação em Java utilizando LinkedHashMap

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacidade;

    public LRUCache(int capacidade) {
        super(capacidade, 0.75f, true);
        this.capacidade = capacidade;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > this.capacidade;
    }
}

A classe o LRUCache ao estender LinkedHashMap, herda uma estrutura de dados que pode manter a ordem de inserção ou de acesso dos elementos. Para o LRU Cache, é necessário manter uma ordem de acesso, ou seja, quando um item é lido ou escrito, ele se move para o final da lista.

No construtor da classe LRUCache, devemos chamar o construtor da superclasse LinkedHashMap com três parâmetros: inicial capacity, load factor e access order.

• Initial Capacity/capacidade: O parâmetro capacidade define o tamanho máximo do cache. Quando o cache atinge sua capacidade máxima, ele deve remover o elemento menos recentemente usado antes de adicionar um novo elemento.
• Load Factor: é uma medida de quão cheio o HashMap pode ficar antes de sua capacidade ser aumentada automaticamente. No nosso exemplo acima definimos 75% da sua capacidade, mas, neste caso ele não será aumentado já que o item menos utilizado recentemente será removido.
• Access Order: é um parâmetro booleano que indica se a ordem deve ser mantida com base na ordem de acesso em vez da ordem de inserção.

Precisamos sobrescrever o método removeEldestEntry de LinkedHashMap. Esse método é chamado pelos métodos put e putAll. Se o método retornar true, a entrada mais antiga será removida do map. No contexto do LRU, a entrada mais velha é aquela que foi acessada menos recentemente. A lógica do método é bem simple, se o tamanho do mapa for maior que a capacidade definida, o entrada mais antiga será removida(LRU Eviction).

Exemplo de Uso da Classe LRUCache

    public static void main(String[] args) {
        LRUCache<Integer, Integer> cache = new LRUCache<>(2);

        cache.put(1, 1);
        cache.put(2, 2);
        System.out.println(cache); //saída {1=1, 2=2}
        cache.get(1);    // retorna 1
        System.out.println(cache); //saida {2=2, 1=1}
        cache.put(3, 3); // Remove o 2 e adiciona o 3
        System.out.println(cache); //saída {1=1, 3=3}
        cache.get(2);    // retorna null
        cache.put(4, 4); // Remove o 1 e adiciona o 4
        System.out.println(cache); //Saída {3=3, 4=4}
        cache.get(3);    // retorna o 3
        System.out.println(cache); //Saída {4=4, 3=3}
        cache.get(4);    // return 4
        System.out.println(cache); //Saída {3=3, 4=4}
    }

Conclusão

O uso de um LRU Cache é uma maneira eficaz de otimizar a recuperação de dados em aplicações que dependem fortemente de tempos de resposta rápidos. A implementação em Java utilizando LinkedHashMap é apenas uma das formas de implmentar este algoritmo, proporcionando um equilíbrio entre complexidade e eficiência. Esperamos que este artigo tenha esclarecido o conceito e a implementação do LRU Cache, e que você possa utilizar esse conhecimento para melhorar o desempenho de suas aplicações.

Queremos ouvir de você! Se você implementou o LRU Cache em seu projeto ou tem alguma dúvida, compartilhe conosco nos comentários. Sua contribuição é valiosa para a comunidade e pode ajudar outros desenvolvedores a encontrar soluções e inspiração.