Java Academy · Aula

Como HashMap funciona

Buckets, hashing e colisões.

Como HashMap funciona é uma aula grátis de Java Academy no CoddyKit. Esta é a aula 1 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de Java Academy, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Java Academy inclui 4 aulas no total.

O que HashMap armazena

Um HashMap armazena pares de chave e valor e oferece acesso, inserção e remoção médios em O(1).

Internamente, ele mantém um vetor chamado tabela. Cada posição desse vetor é chamada de compartimento.

A chave determina em qual compartimento uma entrada será armazenada.
O valor é o que você obtém ao consultar a chave.

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> ages = new HashMap<>();
        ages.put("Alice", 30);
        ages.put("Bob", 25);
        System.out.println(ages.get("Alice"));
    }
}

Calculando o hash da chave

Quando você chama put(key, value), o mapa chama key.hashCode() para obter um int.

Em seguida, HashMap distribui esses bits com uma função interna, para que até códigos hash ruins se distribuam pelos compartimentos.

O número final é reduzido com hash & (table.length - 1) para obter um índice de compartimento.
O comprimento da tabela é sempre uma potência de dois, portanto a máscara funciona.

public class Main {
    public static void main(String[] args) {
        String key = "Alice";
        int h = key.hashCode();
        int spread = h ^ (h >>> 16);
        int index = spread & (16 - 1);
        System.out.println("hashCode: " + h);
        System.out.println("bucket index: " + index);
    }
}

Compartimentos em ação

Cada compartimento pode conter mais de uma entrada. Quando duas chaves são mapeadas para o mesmo compartimento, isso é uma colisão.

Colisões são normais e esperadas. HashMap lida com elas encadeando as entradas dentro do compartimento.

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<Integer, String> m = new HashMap<>();
        for (int i = 0; i < 5; i++) {
            m.put(i, "v" + i);
        }
        System.out.println(m.size() + " entries stored");
    }
}

Colisões e encadeamento

Antes do Java 8, todas as entradas em colisão ficavam em uma lista simplesmente encadeada dentro do compartimento.

A consulta percorre a lista chamando equals() até encontrar a chave correspondente.

Poucas colisões: continua, na prática, em O(1).
Muitas colisões em um compartimento: degrada para O(n) nesse compartimento.

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> m = new HashMap<>();
        m.put("FB", 1);
        m.put("Ea", 2);
        System.out.println("FB hash: " + "FB".hashCode());
        System.out.println("Ea hash: " + "Ea".hashCode());
        System.out.println(m.get("FB") + ", " + m.get("Ea"));
    }
}

Por que FB e Ea colidem

As cadeias de caracteres "FB" e "Ea" têm o mesmo hashCode() em Java. Este é um exemplo clássico de colisão.

Mesmo com códigos hash idênticos, o mapa ainda as mantém separadas porque equals() as distingue dentro do compartimento.

public class Main {
    public static void main(String[] args) {
        System.out.println("FB".hashCode() == "Ea".hashCode());
        System.out.println("FB".equals("Ea"));
    }
}

Fator de carga

O fator de carga controla o quão cheia a tabela fica antes de crescer. O padrão é 0.75.

Uma capacidade de 16 e um fator de carga de 0.75 significam que o redimensionamento será acionado com 12 entradas.
Um fator de carga menor desperdiça memória, mas reduz as colisões.
Um fator de carga maior economiza memória, mas aumenta as colisões.

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<Integer, Integer> m = new HashMap<>(16, 0.75f);
        for (int i = 0; i < 12; i++) m.put(i, i);
        System.out.println("Stored " + m.size() + " entries");
    }
}

Redimensionando a tabela

Quando a quantidade de entradas ultrapassa capacity * loadFactor, o tamanho da tabela dobra.

Cada entrada existente tem seu hash recalculado na tabela nova e maior. Essa é uma operação custosa, portanto definir o tamanho previamente é importante para mapas grandes.

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        // Pre-size to avoid repeated resizes
        Map<Integer, Integer> m = new HashMap<>(1024);
        for (int i = 0; i < 800; i++) m.put(i, i * 2);
        System.out.println("size = " + m.size());
    }
}

Definindo o tamanho previamente para obter desempenho

Se você souber aproximadamente quantas entradas armazenará, forneça uma capacidade inicial para evitar redimensionamentos sucessivos.

Regra prática: capacidade inicial = expectedSize / 0.75 + 1.

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        int expected = 1000;
        int capacity = (int) (expected / 0.75) + 1;
        Map<Integer, String> m = new HashMap<>(capacity);
        System.out.println("Initial capacity hint: " + capacity);
        m.put(1, "ok");
        System.out.println(m.get(1));
    }
}

Chaves e valores nulos

HashMap permite uma chave null e vários valores null.

A chave null sempre vai para o compartimento 0 (seu hash é tratado como 0).
Use getOrDefault para evitar a ambiguidade entre uma chave ausente e um valor null.

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<String, String> m = new HashMap<>();
        m.put(null, "nullKeyValue");
        m.put("a", null);
        System.out.println(m.get(null));
        System.out.println(m.getOrDefault("missing", "default"));
    }
}

A ordem de iteração não é garantida

HashMap não faz nenhuma promessa sobre a ordem de iteração. A ordem depende dos códigos hash e da disposição dos compartimentos.

Se precisar de uma ordem previsível, use LinkedHashMap (ordem de inserção) ou TreeMap (ordem classificada).

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> m = new HashMap<>();
        m.put("one", 1);
        m.put("two", 2);
        m.put("three", 3);
        for (Map.Entry<String, Integer> e : m.entrySet()) {
            System.out.println(e.getKey() + "=" + e.getValue());
        }
    }
}

Resumo do caminho de get()

Uma consulta segue estas etapas:

Calcule hashCode() e distribua os bits.
Aplique uma máscara para encontrar o índice do compartimento.
Percorra o compartimento comparando as chaves com equals().
Retorne o valor correspondente ou nulo.

Um hashCode() bom e um equals() correto mantêm cada etapa rápida.

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> stock = new HashMap<>();
        stock.put("apple", 50);
        stock.put("pear", 20);
        String key = "apple";
        Integer qty = stock.get(key);
        System.out.println(key + " -> " + qty);
    }
}

Verificação rápida

Teste sua compreensão de como HashMap encontra um compartimento.

Recapitulação

Você aprendeu como HashMap funciona internamente:

As chaves são transformadas em hashes e associadas a compartimentos.
As colisões são tratadas encadeando entradas em um compartimento.
O fator de carga (0.75) dispara o dobro do tamanho e a transformação dos hashes.
Pré-dimensionar evita redimensionamentos custosos, e a ordem de iteração não é garantida.

A seguir, veremos por que hashCode sozinho não é suficiente sem um equals correto.

import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Map<String, Integer> m = new HashMap<>(64);
        m.put("recap", 1);
        System.out.println("HashMap basics complete: " + m.get("recap"));
    }
}

Perguntas Frequentes

A aula “Como HashMap funciona” é grátis?

Sim — o texto completo de “Como HashMap funciona” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de Java Academy, atualize para CoddyKit PRO. O curso de Java Academy inclui 4 aulas no total.

O que vou aprender em “Como HashMap funciona”?

Buckets, hashing e colisões. Você pratica Java Academy com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.

Preciso ter experiência prévia para começar Java Academy?

Nenhuma experiência prévia é necessária. Java Academy no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 1 de 4.

Quanto tempo leva a aula “Como HashMap funciona”?

A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.

Posso escrever e executar código nesta aula de Java Academy?

Sim. Cada aula de Java Academy inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.

Todas as aulas deste curso

← Voltar para Java Academy