# 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`: ```java transient Node[] table; ``` Cada posição desse array é chamada de **bucket** (balde). E cada elemento é um `Node`: ```java static class Node implements Map.Entry { final int hash; final K key; V value; Node 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: ```java 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: ```java 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: ```plaintext 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): ```plaintext "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: ```plaintext 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: ```java final Node getNode(Object key) { Node[] tab; Node 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)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: ```java 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: ```java 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: ```java 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.** | Cenário | `get` / `put` | | --- | --- | | Hash bem distribuído (caso normal) | O(1) médio | | Muitas colisões, Java 7 ou anterior | O(n) | | Muitas colisões, Java 8+ (bucket em árvore) | O(log n) | | `put` que dispara `resize` | O(n) naquela chamada, O(1) amortizado | 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: ```java 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 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: ```java 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: ```java List chave = new ArrayList<>(List.of("a")); Map, 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**: ```java @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: ```java Map 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): 2. **Oracle — Javadoc do** `HashMap` **(Java 21)**: 3. **Oracle — Javadoc de** `Object.hashCode()` **e** `Object.equals()` (contrato entre os dois métodos): 4. **JEP 180: Handle Frequent HashMap Collisions with Balanced Trees**: 5. **Oracle — Javadoc do** `ConcurrentHashMap`: 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**: