LRU Cache — o que é, algoritmo de despejo e como funciona

O que é LRU Cache?

LRU Cache (Least Recently Used Cache) é uma estrutura de dados de tamanho fixo que armazena um número limitado de elementos e remove automaticamente aqueles que foram acessados com menos frequência. Quando uma aplicação solicita um elemento, ele se move para a parte “fresca” do cache, enquanto elementos não utilizados por muito tempo deslocam-se para o final e são removidos quando o limite é atingido.

O nome “Least Recently Used” descreve a política de despejo: o elemento que não foi usado por mais tempo entre todos os armazenados é removido. Isso se baseia na suposição de localidade de referência (locality of reference) — dados solicitados recentemente têm alta probabilidade de serem necessários novamente. É por isso que o LRU é considerado uma das estratégias de cache mais eficazes para a maioria das aplicações.

A implementação clássica de LRU Cache requer duas estruturas de dados: uma tabela hash para acesso O(1) a qualquer elemento por chave e uma lista duplamente ligada para rastrear a ordem de uso. A tabela hash armazena referências aos nós da lista, e a lista mantém a ordem do elemento mais novo (cabeça) ao mais antigo (cauda).

Operações básicas de LRU Cache

A operação get(key) verifica se a chave existe na tabela hash. Se encontrado, o elemento é movido para a cabeça da lista (torna-se o mais novo) e seu valor é retornado. Se não encontrado, null é retornado ou uma exceção é lançada. A operação put(key, value) insere um novo elemento: se a chave já existe, o valor é atualizado e o elemento é movido para a cabeça. Se o cache estiver cheio, o elemento da cauda é removido antes da inserção. Todas as operações são executadas em tempo constante O(1).

Como o LRU Cache funciona

O algoritmo LRU Cache é baseado em dois princípios: contagem de acesso em ordem temporal e o mecanismo de despejo por estouro. Cada elemento é armazenado em um nó de lista duplamente ligada, e os ponteiros para esses nós são mantidos na tabela hash. A cada acesso, o elemento é destacado de sua posição atual e inserido no início da lista.

Quando o tamanho do cache atinge seu valor máximo (maxSize) e chega uma solicitação de inserção de um novo elemento, o algoritmo remove o elemento da cauda da lista duplamente ligada — este é o elemento menos recentemente usado. Após a remoção, espaço é liberado para o novo elemento, que é inserido na cabeça da lista. A tabela hash é atualizada de acordo: a chave antiga é removida, uma nova é adicionada.

Uma característica do LRU é sua sensibilidade a padrões de acesso com repetição cíclica. Se a aplicação acessa periodicamente um conjunto de dados maior que o tamanho do cache, o LRU pode sofrer de thrashing — substituição frequente de elementos onde cada nova solicitação despeja a anterior. Em tais cenários, LFU (Least Frequently Used) ou algoritmos adaptativos podem ser mais eficazes.

Tamanho do cache e métricas

Escolher o tamanho do LRU Cache é um compromisso entre consumo de memória e hit-ratio (percentual de acessos bem-sucedidos). Valores típicos para aplicações móveis: 10–20% da memória disponível para cache de imagens e 50–200 entradas para cache de respostas de rede. Um hit-ratio de 80–95% é considerado bom, onde o cache justifica os custos de memória. Para monitoramento, são usados os contadores hitCount e missCount, disponíveis na implementação LruCache no Android.

Implementação de LRU Cache: HashMap + Doubly Linked List

A implementação canônica de LRU Cache usa uma combinação de uma tabela hash e uma lista duplamente ligada. A tabela hash fornece acesso O(1) a qualquer nó por chave, enquanto a lista duplamente ligada permite mover um nó para a cabeça e removê-lo da cauda em O(1). Crucialmente, a lista é duplamente ligada: isso permite destacar um nó do meio da lista sem iterar sobre todos os elementos.

class LruCache<K, V>(
    private val maxSize: Int
) {
    private val map = mutableMapOf<K, Node<V>>()
    private val head = Node<V>(null)
    private val tail = Node<V>(null)

    init {
        head.next = tail
        tail.prev = head
    }

    fun get(key: K): V? {
        val node = map[key] ?: return null
        removeNode(node)
        addToHead(node)
        return node.value
    }

    fun put(key: K, value: V) {
        map[key]?.let { node ->
            removeNode(node)
            node.value = value
            addToHead(node)
            return
        }
        if (map.size >= maxSize) {
            tail.prev?.let { toRemove ->
                removeNode(toRemove)
                removeKeyByValue(toRemove)
            }
        }
        val newNode = Node(value)
        addToHead(newNode)
    }
}

Na implementação, cada nó (Node) armazena um valor e referências aos nós anterior e seguinte. Os nós sentinela head e tail simplificam os casos limite — não é necessário verificar null na inserção e remoção. O método get move o nó encontrado para a cabeça, e put remove o elemento da cauda em caso de estouro. Um método separado removeKeyByValue encontra a chave na tabela hash por referência ao nó e a remove.

Implementação incorporada de LruCache no Android

O SDK do Android fornece uma classe LruCache pronta no pacote android.util, que implementa o algoritmo LRU usando LinkedHashMap em modo access-order. A classe é thread-safe, suporta contagem de hit/miss e fornece o callback entryRemoved para limpeza de recursos ao despejar um elemento. O tamanho do cache é definido em unidades arbitrárias (bytes, número de elementos) — basta sobrescrever o método sizeOf.

LRU Cache vs FIFO e LIFO

Os três algoritmos — LRU, FIFO e LIFO — resolvem o mesmo problema: limitar o consumo de memória despejando elementos ao estourar. No entanto, eles usam critérios fundamentalmente diferentes para selecionar a vítima, o que determina sua eficácia em diferentes cenários.

FIFO despeja o elemento mais antigo por tempo de inserção, independentemente de quantas vezes foi acessado. Isso pode ser ineficiente se um elemento antigo ainda for relevante. LRU evita essa desvantagem considerando o padrão de acesso. LIFO despeja o elemento adicionado mais recentemente — útil para cenários de desfazer, mas inadequado para cache, já que novos dados são frequentemente mais necessários que os antigos. LRU é considerado o equilíbrio ótimo entre complexidade de implementação e hit-ratio para a maioria das aplicações.

Exemplos de código LRU Cache

Vamos considerar o uso da classe incorporada LruCache do SDK do Android para armazenar em cache imagens baixadas. O exemplo mostra a inicialização do cache para 1/8 da memória disponível da aplicação, que é a recomendação padrão do Google para cache de imagens.

import android.util.LruCache

class ImageCache(context: Context) {
    private val maxMemory = (Runtime.getRuntime().maxMemory() / 1024).toInt()
    private val cacheSize = maxMemory / 8

    private val lruCache = object : LruCache<String, Bitmap>(cacheSize) {
        override fun sizeOf(key: String, bitmap: Bitmap): Int {
            return bitmap.rowBytes * bitmap.height / 1024
        }
    }

    fun getBitmap(key: String): Bitmap? {
        return lruCache.get(key)
    }

    fun putBitmap(key: String, bitmap: Bitmap) {
        lruCache.put(key, bitmap)
    }
}

O método sizeOf retorna o tamanho do elemento nas mesmas unidades em que cacheSize é especificado. Aqui, o tamanho do Bitmap em kilobytes é usado (rowBytes × height / 1024). Quando a soma de sizeOf de todos os elementos excede cacheSize, LruCache despeja automaticamente os Bitmaps menos recentemente usados. O callback entryRemoved pode ser usado para chamar bitmap.recycle() — liberando memória antes do despejo.

Implementação de LRU Cache em Swift

iOS não tem uma classe LRU Cache incorporada, mas é fácil de implementar usando NSCache (que usa uma política de despejo similar, mas não documentada) ou através de uma implementação personalizada usando Dictionary + Doubly Linked List, como mostrado abaixo.

class LRUCache<Key: Hashable, Value> {
    private let maxSize: Int
    private var dict = [Key: Node<Value>]()
    private var head: Node<Value>?
    private var tail: Node<Value>?

    init(maxSize: Int) {
        self.maxSize = maxSize
    }

    func get(key: Key) -> Value? {
        guard let node = dict[key] else { return nil }
        moveToHead(node)
        return node.value
    }

    func put(key: Key, value: Value) {
        if let node = dict[key] {
            node.value = value
            moveToHead(node)
            return
        }
        if dict.count >= maxSize {
            tail.map { removeNode($0) }
        }
        let node = Node(value: value)
        dict[key] = node
        addToHead(node)
    }
}

Nesta implementação em Swift, Node é uma classe interna com campos value, next e prev. O método moveToHead destaca um nó de sua posição atual e o insere no início da lista. Em caso de estouro, a cauda — o elemento menos recentemente usado — é removida. Para produção, recomenda-se adicionar segurança de threads via NSLock ou uma fila DispatchQueue.