Rust HashMap: como pesquisar e inserir dados de forma eficiente

Como pesquisar e inserir dados de forma eficiente no HashMap em Rust: olhando por baixo dos panos

Você já escreveu código em Rust e pensou: "Como faço para verificar se uma chave existe no HashMap e, se não existir, inserir um novo valor?" Essa pergunta atormenta milhares de desenvolvedores no Stack Overflow. E não é à toa: uma solução ingênua pode matar o desempenho da sua aplicação. Hoje não vamos apenas dar a resposta — vamos mergulhar dentro do Rust HashMap e ver como ele é estruturado. Você descobrirá por que get e insert separadamente são um caminho para a dor e como usar corretamente a API entry.

Este artigo é para quem já conhece os fundamentos do Rust, mas quer entender mais profundamente como as coleções funcionam internamente. Vamos lá!

O problema: duas chamadas — trabalho dobrado

Imagine uma tarefa típica: você tem um HashMap para contar o número de ocorrências de palavras em um texto. A abordagem ingênua é assim:

use std::collections::HashMap;\n\nfn count_words_naive(words: &[&str]) -> HashMap<String, u32> {\n    let mut map = HashMap::new();\n    \n    for word in words {\n        if map.contains_key(*word) {\n            let count = map.get(*word).unwrap();\n            map.insert(word.to_string(), count + 1);\n        } else {\n            map.insert(word.to_string(), 1);\n        }\n    }\n    \n    map\n}\n

O que há de errado aqui? Acessamos o HashMap duas vezes para cada palavra: primeiro contains_key, depois get, e ainda insert. Cada chamada envolve calcular o hash, procurar no bucket e comparar chaves. Para um texto curto, isso é imperceptível, mas para milhões de registros é um desastre.

Por baixo dos panos: como o HashMap funciona no Rust

Para entender por que isso é ruim, vamos ver como o HashMap funciona no Rust. A base é uma tabela hash com endereçamento aberto (Robin Hood hashing). Aqui estão os pontos-chave:

\n
• Hashing: A chave é transformada em um código hash usando uma função hash (padrão SipHash-2-4).
\n
• Buckets: O código hash determina o índice em um array de buckets. No Rust, cada bucket é um slot que pode estar vazio, ocupado ou removido.
\n
• Colisões: Quando duas chaves diferentes caem no mesmo bucket, o Robin Hood hashing tenta "roubar" o lugar do vizinho mais "rico" para equilibrar as distâncias de busca.
\n
• Redimensionamento: Quando a tabela fica cheia (load factor ~0.9), ela dobra de tamanho e todos os elementos são rehashados.
\n

Agora imagine: cada chamada de get ou insert é um ciclo completo: hashing, busca pelo índice, comparação de chaves (possivelmente várias vezes devido a colisões). Duas chamadas = trabalho dobrado. E se entre as chamadas ocorrer um redimensionamento? Trabalho triplicado!

Solução: Entry API — seu salva-vidas

Rust oferece uma solução elegante — a Entry API. É um mecanismo que permite realizar a busca e, possivelmente, a inserção em uma única passagem. Veja como fica o código correto para contar palavras:

use std::collections::HashMap;\n\nfn count_words_efficient(words: &[&str]) -> HashMap<String, u32> {\n    let mut map = HashMap::new();\n    \n    for word in words {\n        let entry = map.entry(word.to_string());\n        *entry.or_insert(0) += 1;\n    }\n    \n    map\n}\n

Conciso, bonito, eficiente. Mas como isso funciona internamente? Vamos detalhar passo a passo.

Passo 1: Método entry()

A chamada map.entry(key) retorna uma enumeração Entry, que pode estar em dois estados:

\n
• Entry::Occupied — a chave já existe na tabela.
\n
• Entry::Vacant — a chave não existe e temos um local pronto para inserção.
\n

Importante: neste