HashMap por dentro: como Java encontra um valor em O(1)?

Todo dev Java já escreveu algo como map.get("chave") sem pensar duas vezes. E quase todo mundo já ouviu que essa operação é O(1). Mas o que acontece de verdade entre a chamada do get e o valor voltando para você? Como uma estrutura com milhares (ou milhões) de elementos consegue achar um item sem percorrer todos eles?

Neste artigo vamos abrir o código do java.util.HashMap (OpenJDK 8+) e entender, passo a passo, o que torna essa mágica possível, e em quais situações ela deixa de ser mágica.

A ideia central: transformar a chave em um endereço

Um array é a estrutura mais rápida que existe para acesso: se você sabe o índice, array[i] é uma única operação, não importa o tamanho do array.

O problema é que chaves de um mapa não são índices. São String, Long, UUID, objetos seus. A sacada da tabela hash é simples:

Converter a chave em um número inteiro e usar esse número para calcular um índice no array.

Essa conversão é feita pela função hash. Em Java, o ponto de partida é o método hashCode() que todo objeto herda de Object.

Por dentro, o HashMap guarda os dados em um array chamado table:

transient Node<K,V>[] table;

Cada posição desse array é chamada de bucket (balde). E cada elemento é um Node:

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
}

Repare no campo next: cada bucket é, na prática, o início de uma lista encadeada. Já já vamos ver por quê.

Passo 1: calculando o hash

Quando você chama map.put(key, value) ou map.get(key), a primeira coisa que o HashMap faz é chamar este método estático:

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

Duas coisas interessantes aqui:

1. Chave null é permitida e sempre cai no hash 0 (ou seja, no bucket 0).
2. O hashCode() original passa por um "espalhamento": os 16 bits mais altos são combinados via XOR com os 16 bits mais baixos.

Por que isso? Porque, como veremos no próximo passo, o índice do bucket é calculado usando só os bits mais baixos do hash. Sem o espalhamento, dois hashCodes que diferem apenas nos bits altos cairiam sempre no mesmo bucket. O XOR faz os bits altos "participarem" da decisão, a um custo praticamente zero.

Passo 2: do hash ao índice do bucket

Com o hash em mãos, o índice é calculado assim:

int index = (n - 1) & hash;   // n = table.length

Se você esperava ver hash % n, não está errado — o resultado é equivalente. O truque é que a capacidade do HashMap é sempre uma potência de 2 (16, 32, 64…). Quando n é potência de 2, n - 1 em binário é uma sequência de uns:

n     = 16  -> 0001 0000
n - 1 = 15  -> 0000 1111

Então hash & 15 simplesmente "recorta" os 4 bits mais baixos do hash, gerando um número entre 0 e 15. Uma operação AND bit a bit é muito mais barata que uma divisão, e ainda evita o problema de % com números negativos.

É por isso que, mesmo se você pedir new HashMap<>(10), a capacidade real será 16: o método tableSizeFor arredonda para a próxima potência de 2.

Um exemplo concreto

Vamos seguir a chave "java" num HashMap com capacidade padrão (16):

"java".hashCode()        = 3254818     = 0x0031AA22
h >>> 16                 =              0x00000031
h ^ (h >>> 16)           =              0x0031AA13
(16 - 1) & 0x0031AA13    = 0x3         = bucket 3

Curiosidade: sem o espalhamento, o índice seria 0x22 & 0xF = 2. Os bits altos (0x31) mudaram o destino da chave.

O hashCode de String é calculado como s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1], e o resultado fica em cache dentro do objeto — por isso String é uma chave tão eficiente.

Passo 3: colisões (quando duas chaves querem o mesmo bucket)

Existem ~4 bilhões de valores possíveis de int, mas o array tem 16, 32, 64 posições. É matematicamente inevitável que chaves diferentes caiam no mesmo bucket. Isso é uma colisão.

O HashMap resolve colisões com a técnica de encadeamento separado (separate chaining): cada bucket guarda uma lista de nós. Visualmente:

table
┌────┐
│ 0  │ -> null
├────┤
│ 1  │ -> ["abc"=1] -> null
├────┤
│ 2  │ -> null
├────┤
│ 3  │ -> ["java"=10] -> ["xyz"=7] -> null   <- colisão
├────┤
│ ...│
└────┘

E é aqui que entram hashCode() e equals() juntos.

Passo 4: o get por dentro

Esta é uma versão simplificada do getNode do OpenJDK:

final Node<K,V> getNode(Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n, hash; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & (hash = hash(key))]) != null) {

        // 1. Confere o primeiro nó do bucket
        if (first.hash == hash &&
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;

        if ((e = first.next) != null) {
            // 2. Se o bucket virou árvore, busca na árvore
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);

            // 3. Senão, percorre a lista encadeada
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

Repare na ordem das comparações dentro de cada nó:

1. e.hash == hash — comparar dois int é baratíssimo. Se os hashes são diferentes, as chaves com certeza são diferentes, e o equals nem é chamado.
2. k == key — igualdade de referência. Se é o mesmo objeto, acabou.
3. key.equals(k) — só então a comparação "cara" é feita.

Essa sequência de curto-circuitos é um dos motivos de o HashMap ser rápido na prática, e não só na teoria.

Passo 5: o put e o crescimento da tabela

O put segue o mesmo caminho para achar o bucket. Se encontra um nó com chave igual, substitui o valor (e retorna o antigo). Se não encontra, adiciona um nó novo no final da lista (desde o Java 8; antes a inserção era no início).

Depois de inserir, vem uma verificação importante:

if (++size > threshold)
    resize();

Load factor e threshold

• Capacidade inicial padrão: 16
• Load factor padrão: 0.75
• Threshold: capacidade * loadFactor → 16 × 0.75 = 12

Quando o mapa passa de 12 elementos, a tabela dobra de tamanho (16 → 32 → 64…). O objetivo é manter as listas dos buckets curtas. O valor 0.75 é, segundo a própria documentação, um bom equilíbrio entre custo de memória e custo de busca.

Detalhe: a tabela é criada de forma preguiçosa (lazy). Um new HashMap<>() não aloca o array — isso só acontece no primeiro put.

O truque elegante do resize

Ao dobrar a capacidade, cada elemento precisaria ter seu índice recalculado. Mas como as capacidades são potências de 2, o HashMap sabe que cada nó só pode ir para dois lugares:

• ficar no mesmo índice i, ou
• ir para o índice i + capacidadeAntiga.

Quem decide é um único bit do hash:

if ((e.hash & oldCap) == 0)
    // fica na lista "lo" (mesmo índice)
else
    // vai para a lista "hi" (índice + oldCap)

Cada bucket antigo é dividido em duas listas, preservando a ordem relativa dos nós, sem precisar chamar hashCode() de novo (o hash já está salvo no campo hash do Node).

Como a tabela dobra, o custo do resize é diluído entre muitas inserções: o put é O(1) amortizado.

Passo 6: quando a lista vira árvore (Java 8+)

E se muitas chaves colidirem no mesmo bucket? A lista cresce e a busca naquele bucket vira O(n). Isso não é só um problema teórico: antes do Java 8, era possível montar ataques de negação de serviço enviando, por exemplo, parâmetros HTTP cujos nomes tinham o mesmo hashCode, derrubando servidores com uso de CPU.

A resposta veio com a JEP 180: buckets muito cheios são convertidos em árvores rubro-negras (red-black trees), com busca O(log n). As constantes que controlam isso:

static final int TREEIFY_THRESHOLD = 8;      // lista -> árvore
static final int UNTREEIFY_THRESHOLD = 6;    // árvore -> lista (no resize)
static final int MIN_TREEIFY_CAPACITY = 64;  // tamanho mínimo da tabela

Ou seja:

• Quando um bucket atinge 8 nós, ele vira árvore…
• …mas só se a tabela tiver pelo menos 64 posições. Se for menor, o HashMap prefere fazer resize(), porque provavelmente o problema é a tabela pequena demais, não um hashCode ruim.
• Se o bucket encolher para 6 nós ou menos durante um resize, volta a ser lista.

A diferença entre 8 e 6 evita que um bucket fique convertendo de um lado para o outro a cada inserção e remoção.

Para ordenar as chaves na árvore, o HashMap usa primeiro o hash; se houver empate e as chaves implementarem Comparable, usa compareTo. Por isso, chaves que implementam Comparable se comportam melhor em cenários de muitas colisões.

Com uma boa função hash, essa situação é raríssima. O próprio código-fonte do HashMap traz um comentário mostrando que, com load factor 0.75, a distribuição de nós por bucket segue aproximadamente uma distribuição de Poisson, e a probabilidade de um bucket chegar a 8 elementos é da ordem de 0,00000006. A árvore existe como um seguro contra hashCodes ruins ou maliciosos, não como caminho normal.

Então, é O(1) ou não é?

A resposta honesta é: O(1) no caso médio, assumindo que a função hash distribui bem as chaves.

O "O(1)" depende de três fatores trabalhando juntos: um hashCode() que espalha bem, o espalhamento extra do hash(), e o resize mantendo as listas curtas.

Armadilhas que isso tudo explica

Entender o funcionamento interno deixa várias "regras" do Java bem mais óbvias.

1. Sobrescreveu equals? Sobrescreva hashCode

O contrato de Object exige que objetos iguais segundo equals tenham o mesmo hashCode. Se você quebra isso, dois objetos "iguais" vão parar em buckets diferentes e o get simplesmente não os encontra:

class Cpf {
    String numero;
    Cpf(String numero) { this.numero = numero; }

    @Override
    public boolean equals(Object o) {
        return o instanceof Cpf c && c.numero.equals(numero);
    }
    // sem hashCode()!
}

Map<Cpf, String> clientes = new HashMap<>();
clientes.put(new Cpf("123"), "Maria");
clientes.get(new Cpf("123")); // null 😬

Com record, equals e hashCode são gerados automaticamente e de forma consistente:

record Cpf(String numero) {}

2. Nunca altere uma chave depois de inseri-la

O hash é calculado no momento do put e fica salvo no Node. Se você modifica um campo que participa do hashCode, o objeto continua no bucket antigo, mas o get vai procurar no bucket novo:

List<String> chave = new ArrayList<>(List.of("a"));
Map<List<String>, Integer> map = new HashMap<>();
map.put(chave, 1);

chave.add("b");               // hashCode da lista mudou
map.get(chave);               // null
map.containsKey(chave);       // false — mas o elemento está lá dentro!

Prefira chaves imutáveis: String, Integer, UUID, record com campos imutáveis.

3. Um hashCode ruim destrói a performance

Este hashCode é válido segundo o contrato, mas manda tudo para o mesmo bucket:

@Override
public int hashCode() { return 42; }

O mapa continua funcionando, mas vira uma única árvore (ou lista) gigante. Use Objects.hash(campo1, campo2) ou deixe a IDE/record gerar.

4. Dimensione o mapa se você já sabe o tamanho

Se você vai inserir 1.000 elementos em um new HashMap<>(), a tabela vai passar por vários resizes (16 → 32 → 64 → … → 2048). Se você já sabe a quantidade, dimensione de antemão. A partir do Java 19 existe um método de fábrica que já faz a conta considerando o load factor:

Map<String, Pedido> pedidos = HashMap.newHashMap(1_000);

Em versões anteriores, a conta manual é new HashMap<>((int) (esperado / 0.75f) + 1). Atenção: new HashMap<>(1000) não garante espaço para 1.000 elementos sem resize, porque o argumento é a capacidade, não o número de mapeamentos.

5. HashMap não é thread-safe

Vários threads escrevendo ao mesmo tempo podem perder dados ou corromper a estrutura (no Java 7, resizes concorrentes com inserção no início da lista chegavam a criar ciclos e loops infinitos). Para acesso concorrente, use ConcurrentHashMap.

Resumo

Quando você chama map.get(chave):

1. chave.hashCode() gera um int.
2. hash() mistura os bits altos com os baixos.
3. (n - 1) & hash aponta direto para um bucket do array.
4. No bucket, compara hash → referência → equals até achar a chave.
5. Se o bucket tiver virado árvore, faz uma busca O(log n).

Tudo isso sustentado por uma tabela que dobra de tamanho quando passa de 75% de ocupação. É uma combinação de matemática simples, truques de bits e decisões de engenharia pragmáticas, e é por isso que o HashMap é uma das estruturas mais usadas do Java há mais de 25 anos.

Referências

1. OpenJDK — código-fonte do HashMap (vale muito a leitura, inclusive os comentários de implementação): https://github.com/openjdk/jdk/blob/master/src/java.base/share/classes/java/util/HashMap.java
2. Oracle — Javadoc do HashMap (Java 21): https://docs.oracle.com/en/java/javase/21/docs/api/java.base/java/util/HashMap.html
3. Oracle — Javadoc de Object.hashCode() e Object.equals() (contrato entre os dois métodos): https://docs.oracle.com/en/java/javase/21/docs/api/java.base/java/lang/Object.html
4. JEP 180: Handle Frequent HashMap Collisions with Balanced Trees: https://openjdk.org/jeps/180
5. Oracle — Javadoc do ConcurrentHashMap: https://docs.oracle.com/en/java/javase/21/docs/api/java.base/java/util/concurrent/ConcurrentHashMap.html
6. CORMEN, T. H. et al. Algoritmos: Teoria e Prática. Capítulo "Tabelas de Espalhamento" (Hash Tables).
7. BLOCH, Joshua. Java Efetivo, 3ª ed. Item 11: "Sempre sobrescreva o hashCode ao sobrescrever o equals".
8. Baeldung — A Guide to Java HashMap: https://www.baeldung.com/java-hashmap