LRU Cache em Rust: Implementação Completa com HashMap e Lista Duplamente Ligada

Introdução

O LRU Cache (Least Recently Used Cache) é uma das estruturas de dados mais cobradas em entrevistas técnicas e uma das mais utilizadas em sistemas reais. A ideia central é simples: quando o cache atinge sua capacidade máxima, o item menos recentemente usado é removido para dar espaço a novos dados.

Essa estratégia de evição é baseada no princípio da localidade temporal: dados acessados recentemente têm maior probabilidade de serem acessados novamente em breve. Navegadores web, bancos de dados, sistemas operacionais e servidores de aplicação — todos utilizam variações de LRU Cache internamente.

O desafio de implementação está em garantir que ambas as operações — get (busca) e put (inserção/atualização) — sejam executadas em tempo constante O(1). Para isso, combinamos duas estruturas: um HashMap para acesso rápido por chave e uma lista duplamente ligada para manter a ordem de uso.

Nesta página, vamos construir um LRU Cache completo em Rust, explorando os detalhes de implementação, as decisões de design e um exemplo prático de cache de respostas HTTP.

Conceito e Teoria

Como Funciona o LRU Cache

O LRU Cache mantém uma ordem de acesso entre seus elementos. Toda vez que um item é acessado (lido ou escrito), ele se move para o início da lista (posição “mais recente”). Quando a capacidade é excedida, o item no final da lista (posição “menos recente”) é removido.

Diagrama: Funcionamento do LRU Cache
=========================================

Estado inicial (capacidade = 3):

  HashMap                  Lista Duplamente Ligada
  +-------+-------+
  | chave | *nó   |       HEAD <-> [C] <-> [B] <-> [A] <-> TAIL
  +-------+-------+        ^                                  ^
  |   A   |  *----|-----+  |  mais recente       menos recente|
  |   B   |  *----|---+  |
  |   C   |  *----|--+  |
  +-------+-------+  |  |
                      |  |
                      v  v

Após get(A) — A vai para o início:

  HEAD <-> [A] <-> [C] <-> [B] <-> TAIL

Após put(D) — capacidade excedida, B (menos recente) é removido:

  HEAD <-> [D] <-> [A] <-> [C] <-> TAIL
  (B foi evicado!)

Estrutura Interna

A combinação de HashMap + lista duplamente ligada é o que permite O(1) em todas as operações:

Arquitetura do LRU Cache:
===========================

  +--------------------------------------------------+
  |                    LRU Cache                      |
  |                                                   |
  |  +-------------------+   +---------------------+  |
  |  |     HashMap       |   | Lista Dupl. Ligada  |  |
  |  |                   |   |                     |  |
  |  |  chave -> *nó     |   |  HEAD               |  |
  |  |                   |   |    |                 |  |
  |  |  "user:1" -> *----|---|---->[user:1, dados]  |  |
  |  |                   |   |        |             |  |
  |  |  "user:2" -> *----|---|---->[user:2, dados]  |  |
  |  |                   |   |        |             |  |
  |  |  "user:3" -> *----|---|---->[user:3, dados]  |  |
  |  |                   |   |    TAIL              |  |
  |  +-------------------+   +---------------------+  |
  +--------------------------------------------------+

  - HashMap: busca O(1) por chave
  - Lista: mover para início O(1), remover do final O(1)
  - Combinação: todas as operações em O(1)!

Operações Fundamentais

get(chave): Busca o valor associado à chave. Se encontrado, move o nó para o início da lista (marca como recente). Retorna None se não existir.
put(chave, valor): Insere ou atualiza um par chave-valor. Se a chave já existe, atualiza o valor e move para o início. Se a capacidade for excedida, remove o item do final da lista (menos recente) antes de inserir.
Evição: Quando len == capacidade e precisamos inserir, removemos o nó que está no final da lista (TAIL), e removemos a entrada correspondente do HashMap.

Complexidade

Operação	Tempo	Espaço	Observação
`get(chave)`	O(1)	O(1)	HashMap lookup + mover nó na lista
`put(chave, val)`	O(1)	O(1)	HashMap insert + inserir no início
`evição`	O(1)	O(1)	Remover do final da lista + HashMap
`contains`	O(1)	O(1)	Apenas HashMap lookup
`len`	O(1)	O(1)	Contador mantido internamente
Espaço total		O(n)	n = capacidade do cache

A constante O(1) para todas as operações é o que torna o LRU Cache tão eficiente. Sem a lista duplamente ligada, precisaríamos de O(n) para encontrar e remover o item menos recente.

Implementação em Rust

Implementar uma lista duplamente ligada em Rust é um desafio clássico devido ao sistema de ownership. Usaremos ponteiros brutos (*mut) encapsulados em uma interface segura.

use std::collections::HashMap;
use std::ptr;

/// Nó da lista duplamente ligada.
/// Cada nó armazena uma chave (para remoção no HashMap)
/// e o valor associado.
struct Node<K, V> {
    chave: K,
    valor: V,
    anterior: *mut Node<K, V>,
    proximo: *mut Node<K, V>,
}

impl<K, V> Node<K, V> {
    fn novo(chave: K, valor: V) -> *mut Self {
        Box::into_raw(Box::new(Node {
            chave,
            valor,
            anterior: ptr::null_mut(),
            proximo: ptr::null_mut(),
        }))
    }
}

/// LRU Cache com operações O(1) para get e put.
///
/// Utiliza um HashMap para acesso rápido por chave e uma
/// lista duplamente ligada para manter a ordem de uso.
pub struct LruCache<K, V>
where
    K: Eq + std::hash::Hash + Clone,
{
    capacidade: usize,
    mapa: HashMap<K, *mut Node<K, V>>,
    /// Nó sentinela — cabeça da lista (mais recente)
    cabeca: *mut Node<K, V>,
    /// Nó sentinela — cauda da lista (menos recente)
    cauda: *mut Node<K, V>,
}

impl<K, V> LruCache<K, V>
where
    K: Eq + std::hash::Hash + Clone,
{
    /// Cria um novo LRU Cache com a capacidade especificada.
    ///
    /// # Panics
    /// Entra em pânico se a capacidade for zero.
    pub fn novo(capacidade: usize) -> Self {
        assert!(capacidade > 0, "Capacidade deve ser maior que zero");

        // Criamos nós sentinelas para simplificar a lógica de inserção/remoção.
        // Sentinelas evitam verificações de ponteiro nulo nas bordas.
        let cabeca = Node::novo(unsafe { std::mem::zeroed() }, unsafe {
            std::mem::zeroed()
        });
        let cauda = Node::novo(unsafe { std::mem::zeroed() }, unsafe {
            std::mem::zeroed()
        });

        unsafe {
            (*cabeca).proximo = cauda;
            (*cauda).anterior = cabeca;
        }

        LruCache {
            capacidade,
            mapa: HashMap::with_capacity(capacidade),
            cabeca,
            cauda,
        }
    }

    /// Busca o valor associado à chave.
    /// Move o item para o início da lista (marca como recente).
    /// Retorna None se a chave não existir no cache.
    pub fn get(&mut self, chave: &K) -> Option<&V> {
        if let Some(&no_ptr) = self.mapa.get(chave) {
            // Remove o nó da posição atual
            self.desconectar_no(no_ptr);
            // Move para o início (mais recente)
            self.inserir_apos_cabeca(no_ptr);

            unsafe { Some(&(*no_ptr).valor) }
        } else {
            None
        }
    }

    /// Insere ou atualiza um par chave-valor no cache.
    /// Se a capacidade for excedida, remove o item menos recente.
    pub fn put(&mut self, chave: K, valor: V) {
        if let Some(&no_ptr) = self.mapa.get(&chave) {
            // Chave já existe — atualiza o valor e move para o início
            unsafe {
                (*no_ptr).valor = valor;
            }
            self.desconectar_no(no_ptr);
            self.inserir_apos_cabeca(no_ptr);
        } else {
            // Chave nova — verifica capacidade
            if self.mapa.len() == self.capacidade {
                // Remove o item menos recente (antes da cauda)
                self.remover_menos_recente();
            }

            // Cria novo nó e insere
            let novo_no = Node::novo(chave.clone(), valor);
            self.inserir_apos_cabeca(novo_no);
            self.mapa.insert(chave, novo_no);
        }
    }

    /// Retorna o número de itens no cache.
    pub fn len(&self) -> usize {
        self.mapa.len()
    }

    /// Verifica se o cache está vazio.
    pub fn esta_vazio(&self) -> bool {
        self.mapa.is_empty()
    }

    /// Verifica se a chave existe no cache (sem alterar a ordem).
    pub fn contem(&self, chave: &K) -> bool {
        self.mapa.contains_key(chave)
    }

    // --- Métodos auxiliares (privados) ---

    /// Remove um nó da lista duplamente ligada (sem desalocar).
    fn desconectar_no(&self, no: *mut Node<K, V>) {
        unsafe {
            let anterior = (*no).anterior;
            let proximo = (*no).proximo;
            (*anterior).proximo = proximo;
            (*proximo).anterior = anterior;
        }
    }

    /// Insere um nó logo após a cabeça (posição mais recente).
    fn inserir_apos_cabeca(&self, no: *mut Node<K, V>) {
        unsafe {
            let primeiro = (*self.cabeca).proximo;
            (*no).anterior = self.cabeca;
            (*no).proximo = primeiro;
            (*self.cabeca).proximo = no;
            (*primeiro).anterior = no;
        }
    }

    /// Remove e desaloca o nó menos recente (antes da cauda).
    fn remover_menos_recente(&mut self) {
        unsafe {
            let ultimo = (*self.cauda).anterior;
            if ultimo == self.cabeca {
                return; // Lista vazia (apenas sentinelas)
            }
            self.desconectar_no(ultimo);
            let chave_removida = &(*ultimo).chave;
            self.mapa.remove(chave_removida);
            // Desaloca o nó
            drop(Box::from_raw(ultimo));
        }
    }
}

/// Implementação de Drop para liberar toda a memória alocada.
impl<K, V> Drop for LruCache<K, V>
where
    K: Eq + std::hash::Hash + Clone,
{
    fn drop(&mut self) {
        // Libera todos os nós de dados
        unsafe {
            let mut atual = (*self.cabeca).proximo;
            while atual != self.cauda {
                let proximo = (*atual).proximo;
                drop(Box::from_raw(atual));
                atual = proximo;
            }
            // Libera os sentinelas
            drop(Box::from_raw(self.cabeca));
            drop(Box::from_raw(self.cauda));
        }
    }
}

fn main() {
    let mut cache = LruCache::novo(3);

    // Inserir dados
    cache.put("usuario:1", "Alice");
    cache.put("usuario:2", "Bruno");
    cache.put("usuario:3", "Carla");

    println!("Tamanho do cache: {}", cache.len()); // 3

    // Acessar um item (move para o início)
    if let Some(nome) = cache.get(&"usuario:1") {
        println!("Encontrado: {}", nome); // Alice
    }

    // Inserir além da capacidade — "usuario:2" será evicado
    // pois "usuario:1" foi acessado recentemente
    cache.put("usuario:4", "Daniel");

    // "usuario:2" foi removido (menos recente)
    assert!(cache.get(&"usuario:2").is_none());
    println!("usuario:2 evicado: {}", !cache.contem(&"usuario:2"));

    // Estado final: usuario:4, usuario:1, usuario:3
    println!("usuario:1 = {:?}", cache.get(&"usuario:1"));
    println!("usuario:3 = {:?}", cache.get(&"usuario:3"));
    println!("usuario:4 = {:?}", cache.get(&"usuario:4"));
}

Versão Segura com `LinkedList` Simplificada

Para quem prefere evitar ponteiros brutos, podemos usar uma abordagem baseada em Vec com índices, sacrificando um pouco de elegância mas mantendo segurança total:

use std::collections::HashMap;

/// LRU Cache implementado com Vec e índices (sem unsafe).
/// Usa uma "lista ligada" baseada em array com slots livres.
pub struct LruCacheSeguro<K, V>
where
    K: Eq + std::hash::Hash + Clone,
{
    capacidade: usize,
    mapa: HashMap<K, usize>,         // chave -> índice no vetor
    entradas: Vec<Entrada<K, V>>,     // pool de nós
    cabeca: Option<usize>,            // índice do mais recente
    cauda: Option<usize>,             // índice do menos recente
    livres: Vec<usize>,               // slots disponíveis para reuso
}

struct Entrada<K, V> {
    chave: K,
    valor: V,
    anterior: Option<usize>,
    proximo: Option<usize>,
    ativo: bool,
}

impl<K, V> LruCacheSeguro<K, V>
where
    K: Eq + std::hash::Hash + Clone + Default,
    V: Default,
{
    pub fn novo(capacidade: usize) -> Self {
        assert!(capacidade > 0);
        LruCacheSeguro {
            capacidade,
            mapa: HashMap::with_capacity(capacidade),
            entradas: Vec::with_capacity(capacidade),
            cabeca: None,
            cauda: None,
            livres: Vec::new(),
        }
    }

    pub fn get(&mut self, chave: &K) -> Option<&V> {
        if let Some(&idx) = self.mapa.get(chave) {
            self.mover_para_frente(idx);
            Some(&self.entradas[idx].valor)
        } else {
            None
        }
    }

    pub fn put(&mut self, chave: K, valor: V) {
        if let Some(&idx) = self.mapa.get(&chave) {
            // Atualiza valor existente
            self.entradas[idx].valor = valor;
            self.mover_para_frente(idx);
        } else {
            // Evicta se necessário
            if self.mapa.len() == self.capacidade {
                self.remover_cauda();
            }

            // Aloca slot
            let idx = if let Some(livre) = self.livres.pop() {
                self.entradas[livre] = Entrada {
                    chave: chave.clone(),
                    valor,
                    anterior: None,
                    proximo: self.cabeca,
                    ativo: true,
                };
                livre
            } else {
                let idx = self.entradas.len();
                self.entradas.push(Entrada {
                    chave: chave.clone(),
                    valor,
                    anterior: None,
                    proximo: self.cabeca,
                    ativo: true,
                });
                idx
            };

            // Atualiza a cabeça antiga
            if let Some(cabeca_antiga) = self.cabeca {
                self.entradas[cabeca_antiga].anterior = Some(idx);
            }
            self.cabeca = Some(idx);

            // Se lista estava vazia, a cauda também é o novo nó
            if self.cauda.is_none() {
                self.cauda = Some(idx);
            }

            self.mapa.insert(chave, idx);
        }
    }

    fn mover_para_frente(&mut self, idx: usize) {
        if self.cabeca == Some(idx) {
            return; // Já está na frente
        }

        // Desconecta o nó
        let ant = self.entradas[idx].anterior;
        let prox = self.entradas[idx].proximo;

        if let Some(a) = ant {
            self.entradas[a].proximo = prox;
        }
        if let Some(p) = prox {
            self.entradas[p].anterior = ant;
        }
        if self.cauda == Some(idx) {
            self.cauda = ant;
        }

        // Insere na frente
        self.entradas[idx].anterior = None;
        self.entradas[idx].proximo = self.cabeca;
        if let Some(cabeca_antiga) = self.cabeca {
            self.entradas[cabeca_antiga].anterior = Some(idx);
        }
        self.cabeca = Some(idx);
    }

    fn remover_cauda(&mut self) {
        if let Some(cauda_idx) = self.cauda {
            let chave = self.entradas[cauda_idx].chave.clone();
            let ant = self.entradas[cauda_idx].anterior;

            self.mapa.remove(&chave);
            self.entradas[cauda_idx].ativo = false;
            self.livres.push(cauda_idx);

            self.cauda = ant;
            if let Some(nova_cauda) = self.cauda {
                self.entradas[nova_cauda].proximo = None;
            } else {
                self.cabeca = None; // Lista ficou vazia
            }
        }
    }
}

Exemplo Prático

Cache de Respostas HTTP para Servidor Web

Um caso de uso real e muito comum: cachear respostas de um servidor web para evitar reprocessamento de requisições frequentes.

use std::collections::HashMap;
use std::time::{Duration, Instant};

/// Representa uma resposta HTTP cacheada.
#[derive(Clone, Debug)]
struct RespostaHttp {
    codigo_status: u16,
    corpo: String,
    tipo_conteudo: String,
    criado_em: Instant,
    ttl: Duration,
}

impl RespostaHttp {
    fn expirou(&self) -> bool {
        self.criado_em.elapsed() > self.ttl
    }
}

/// Cache HTTP usando LRU para respostas de API.
/// Remove respostas expiradas e evicta as menos usadas.
struct CacheHttpLru {
    capacidade: usize,
    mapa: HashMap<String, (RespostaHttp, usize)>, // url -> (resposta, posição)
    ordem: Vec<String>,  // ordem de acesso (simplificado)
    acertos: u64,
    erros: u64,
}

impl CacheHttpLru {
    fn novo(capacidade: usize) -> Self {
        CacheHttpLru {
            capacidade,
            mapa: HashMap::with_capacity(capacidade),
            ordem: Vec::with_capacity(capacidade),
            acertos: 0,
            erros: 0,
        }
    }

    /// Busca uma resposta no cache pela URL.
    fn buscar(&mut self, url: &str) -> Option<RespostaHttp> {
        if let Some((resposta, _)) = self.mapa.get(url) {
            // Verifica se expirou
            if resposta.expirou() {
                // Remove entrada expirada
                self.mapa.remove(url);
                self.ordem.retain(|u| u != url);
                self.erros += 1;
                return None;
            }

            // Atualiza ordem de acesso (move para o início)
            self.ordem.retain(|u| u != url);
            self.ordem.insert(0, url.to_string());

            self.acertos += 1;
            Some(resposta.clone())
        } else {
            self.erros += 1;
            None
        }
    }

    /// Armazena uma resposta no cache.
    fn armazenar(&mut self, url: String, resposta: RespostaHttp) {
        // Se já existe, atualiza
        if self.mapa.contains_key(&url) {
            self.ordem.retain(|u| u != &url);
        } else if self.mapa.len() >= self.capacidade {
            // Evicta o menos recente
            if let Some(menos_recente) = self.ordem.pop() {
                self.mapa.remove(&menos_recente);
                println!("  [EVICÇÃO] Removido do cache: {}", menos_recente);
            }
        }

        self.ordem.insert(0, url.clone());
        self.mapa.insert(url, (resposta, 0));
    }

    /// Retorna estatísticas do cache.
    fn estatisticas(&self) -> String {
        let total = self.acertos + self.erros;
        let taxa = if total > 0 {
            (self.acertos as f64 / total as f64) * 100.0
        } else {
            0.0
        };
        format!(
            "Cache: {} itens | Acertos: {} | Erros: {} | Taxa: {:.1}%",
            self.mapa.len(),
            self.acertos,
            self.erros,
            taxa
        )
    }
}

fn main() {
    let mut cache = CacheHttpLru::novo(3);

    // Simulação de requisições HTTP
    let resposta_api = RespostaHttp {
        codigo_status: 200,
        corpo: r#"{"usuarios": [...]}"#.to_string(),
        tipo_conteudo: "application/json".to_string(),
        criado_em: Instant::now(),
        ttl: Duration::from_secs(300), // 5 minutos
    };

    // Armazena respostas
    cache.armazenar("/api/usuarios".to_string(), resposta_api.clone());
    cache.armazenar("/api/produtos".to_string(), RespostaHttp {
        codigo_status: 200,
        corpo: r#"{"produtos": [...]}"#.to_string(),
        tipo_conteudo: "application/json".to_string(),
        criado_em: Instant::now(),
        ttl: Duration::from_secs(60),
    });
    cache.armazenar("/api/pedidos".to_string(), RespostaHttp {
        codigo_status: 200,
        corpo: r#"{"pedidos": [...]}"#.to_string(),
        tipo_conteudo: "application/json".to_string(),
        criado_em: Instant::now(),
        ttl: Duration::from_secs(120),
    });

    // Busca com acerto
    if let Some(resp) = cache.buscar("/api/usuarios") {
        println!("Acerto no cache! Status: {}", resp.codigo_status);
    }

    // Inserir nova entrada — evicta /api/produtos (menos recente)
    cache.armazenar("/api/relatorios".to_string(), RespostaHttp {
        codigo_status: 200,
        corpo: r#"{"relatorios": [...]}"#.to_string(),
        tipo_conteudo: "application/json".to_string(),
        criado_em: Instant::now(),
        ttl: Duration::from_secs(600),
    });

    // /api/produtos foi evicado
    assert!(cache.buscar("/api/produtos").is_none());

    println!("{}", cache.estatisticas());
}

Exercícios

Exercício 1 — LRU Cache com TTL

Modifique o LRU Cache para que cada entrada tenha um tempo de vida (TTL) individual. Itens expirados devem ser tratados como inexistentes no get e removidos proativamente. Implemente um método limpar_expirados() que remove todas as entradas cujo TTL foi ultrapassado.

Dica: Adicione um campo Instant a cada nó e verifique a expiração no get.

Exercício 2 — LRU Cache Thread-Safe

Envolva o LRU Cache com Arc<Mutex<>> para criar uma versão thread-safe. Teste com múltiplas threads fazendo get e put concorrentes. Meça o impacto do lock contention com 4, 8 e 16 threads.

Desafio extra: Implemente uma versão com RwLock onde leituras (get) possam ocorrer em paralelo. Qual é a dificuldade? (Pense: get também modifica a ordem da lista!)

Exercício 3 — Comparação de Políticas de Evição

Implemente um benchmark que compare LRU com uma política FIFO simples e uma política aleatória. Use uma sequência de acessos com distribuição Zipf (onde poucos itens são acessados com muito mais frequência). Qual política tem a melhor taxa de acerto (hit rate)?

Dica: Use a crate rand para gerar acessos e calcule acertos / total_de_acessos para cada política.

Conclusão

O LRU Cache é uma estrutura elegante que combina HashMap e lista duplamente ligada para atingir O(1) em todas as operações. Em Rust, a implementação com ponteiros brutos exige cuidado extra com unsafe, mas nos dá controle total sobre a memória.

Os pontos principais desta estrutura são:

O(1) para get e put: A combinação HashMap + lista duplamente ligada é a chave.
Evição previsível: O item menos recentemente usado é sempre removido primeiro.
Localidade temporal: Funciona excepcionalmente bem quando acessos recentes predizem acessos futuros.
Trade-off de memória: Cada entrada armazena ponteiros extras (anterior/próximo), consumindo mais memória que um HashMap simples.

Na prática, considere usar a crate lru para produção, que oferece uma implementação otimizada, testada e segura. Para aprendizado, implementar do zero como fizemos aqui é insubstituível para entender como caches funcionam internamente.

No próximo passo, explore o LFU Cache (Least Frequently Used), que usa frequência de acesso em vez de recência — uma alternativa poderosa para cenários onde popularidade importa mais que acesso recente.