0Pricing
Java Academy · Aula

Transformação em árvore e desempenho

Como o Java 8+ trata colisões.

Transformação em árvore e desempenho é uma aula grátis de Java Academy no CoddyKit. Esta é a aula 4 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 problema das colisões

Antes do Java 8, um compartimento com muitas colisões se tornava uma longa lista encadeada. A consulta nesse compartimento se degradava para O(n).

Um invasor poderia explorar isso com chaves criadas especialmente para causar uma negação de serviço, todas produzindo hash para o mesmo compartimento.

public class Main {
    public static void main(String[] args) {
        // All these strings can be made to collide in one bucket
        System.out.println("FB".hashCode() == "Ea".hashCode());
    }
}

Transformação em árvore no Java 8

O Java 8 adicionou a transformação em árvore. Quando um único compartimento contém entradas demais, a lista encadeada é convertida em uma árvore rubro-negra balanceada.

A consulta nesse compartimento passa a ser O(log n), em vez de O(n).

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

public class Main {
    public static void main(String[] args) {
        Map<Integer, Integer> m = new HashMap<>();
        for (int i = 0; i < 1000; i++) m.put(i, i);
        System.out.println("Lookups stay fast: " + m.get(742));
    }
}

O limite: TREEIFY_THRESHOLD

A constante TREEIFY_THRESHOLD é 8. Um compartimento é convertido em árvore quando alcança 8 entradas.

Mas há uma segunda condição: a tabela também deve ter pelo menos o tamanho MIN_TREEIFY_CAPACITY (64); caso contrário, o mapa é redimensionado.

public class Main {
    public static void main(String[] args) {
        int TREEIFY_THRESHOLD = 8;
        int MIN_TREEIFY_CAPACITY = 64;
        System.out.println("Treeify when bucket size >= " + TREEIFY_THRESHOLD);
        System.out.println("...and table capacity >= " + MIN_TREEIFY_CAPACITY);
    }
}

Redimensione primeiro, transforme em árvore depois

Se um compartimento transbordar, mas a tabela ainda for pequena (com menos de 64 posições), HashMap redimensionará a tabela primeiro.

O redimensionamento geralmente redistribui as entradas e elimina o ponto de concentração, portanto a transformação em árvore é apenas o último recurso para distribuições de hash realmente ruins.

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

public class Main {
    public static void main(String[] args) {
        Map<Integer, Integer> m = new HashMap<>(16);
        for (int i = 0; i < 50; i++) m.put(i, i);
        // Many resizes happened before any treeify would
        System.out.println("size = " + m.size());
    }
}

Transformação de árvore em lista

As árvores não são permanentes. Se remoções reduzirem um compartimento abaixo de UNTREEIFY_THRESHOLD (6), a árvore volta a ser uma lista encadeada.

A diferença entre 8 (transformação em árvore) e 6 (transformação em lista) evita alternâncias repetidas no limite.

public class Main {
    public static void main(String[] args) {
        System.out.println("TREEIFY_THRESHOLD   = 8");
        System.out.println("UNTREEIFY_THRESHOLD = 6");
        System.out.println("Gap prevents flip-flopping at the edge");
    }
}

As árvores precisam de ordem comparável ou de identidade

Uma árvore rubro-negra precisa ordenar suas entradas. HashMap primeiro compara os códigos hash; em caso de empate, usa Comparable se as chaves o implementarem; caso contrário, usa um critério de desempate estável baseado nos nomes das classes e na identidade.

Chaves que são Comparable (como String ou Inteiro) fornecem a ordenação mais clara para a árvore.

public class Main {
    public static void main(String[] args) {
        System.out.println("String is Comparable: " + ("a" instanceof Comparable));
        System.out.println("Integer is Comparable: " + (Integer.valueOf(1) instanceof Comparable));
    }
}

Impacto prático

Na maioria dos programas reais com bons códigos hash, você nunca verá a transformação em árvore. Os compartimentos permanecem curtos.

A transformação em árvore é uma rede de segurança que limita a consulta no pior caso a O(log n), mesmo quando o hash é ruim ou maliciosamente preparado.

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("alpha", 1);
        m.put("beta", 2);
        m.put("gamma", 3);
        // Tiny buckets, plain linked lists, no trees needed
        System.out.println(m.get("beta"));
    }
}

Um hashCode constante força a criação de árvores

Se você retornar deliberadamente um hashCode constante, toda chave irá para um único compartimento. Com capacidade de 64 ou mais, esse compartimento será transformado em árvore.

Isso demonstra a rede de segurança, mas indica um problema de projeto. Em vez disso, corrija o hashCode.

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

public class Main {
    static class Bad implements Comparable<Bad> {
        final int v;
        Bad(int v) { this.v = v; }
        @Override public int hashCode() { return 1; } // forces collisions
        @Override public boolean equals(Object o) { return o instanceof Bad b && b.v == v; }
        @Override public int compareTo(Bad o) { return Integer.compare(v, o.v); }
    }
    public static void main(String[] args) {
        Map<Bad, Integer> m = new HashMap<>();
        for (int i = 0; i < 100; i++) m.put(new Bad(i), i);
        System.out.println("All in one bucket, still works: " + m.get(new Bad(50)));
    }
}

Custo de memória das árvores

Os nós de árvore são maiores que os nós comuns de uma lista encadeada, pois armazenam referências para pai, esquerda, direita e cor.

Esse é outro motivo para a transformação em árvore ser uma alternativa de último recurso, não o padrão: as árvores trocam memória por velocidade no pior caso.

public class Main {
    public static void main(String[] args) {
        System.out.println("Node: hash, key, value, next");
        System.out.println("TreeNode: + parent, left, right, prev, red flag");
        System.out.println("=> trees cost more memory per entry");
    }
}

Como evitar a transformação em árvore

Quase nunca é desejável depender da transformação em árvore. Evite-a:

  • Escrevendo um hashCode() bem distribuído.
  • Usando tipos integrados ou registros como chaves.
  • Pré-dimensionando o mapa para reduzir colisões.
import java.util.HashMap;
import java.util.Map;
import java.util.Objects;

public class Main {
    record Key(int a, int b) {}
    public static void main(String[] args) {
        Map<Key, Integer> m = new HashMap<>(256);
        for (int i = 0; i < 200; i++) m.put(new Key(i, i * 31), i);
        System.out.println("Even distribution, fast lookups: " + m.get(new Key(10, 310)));
    }
}

Resumo do desempenho

Custos das operações de HashMap:

  • Hash bom: O(1) em média.
  • Compartimento encadeado: O(n) por compartimento no pior caso.
  • Compartimento transformado em árvore: O(log n) por compartimento.

A transformação em árvore limita o pior caso, mas um hashCode bom mantém você no cenário O(1).

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

public class Main {
    public static void main(String[] args) {
        Map<Integer, Integer> m = new HashMap<>(1 << 14);
        for (int i = 0; i < 10000; i++) m.put(i, i);
        System.out.println("10k entries, O(1) get: " + m.get(9999));
    }
}

Verificação rápida

Teste seus conhecimentos sobre a transformação em árvore.

Recapitulação

Você aprendeu como o HashMap moderno trata colisões:

  • Os compartimentos são transformados em árvores com 8 entradas quando a capacidade é de pelo menos 64.
  • As árvores fornecem consultas no pior caso de O(log n).
  • Os compartimentos voltam a ser listas com menos de 6 entradas.
  • Um hashCode bom significa que você raramente acionará essa rede de segurança.

Você concluiu o curso sobre os componentes internos de HashMap.

public class Main {
    public static void main(String[] args) {
        System.out.println("Treeification course complete");
    }
}

Perguntas Frequentes

A aula “Transformação em árvore e desempenho” é grátis?

Sim — o texto completo de “Transformação em árvore e desempenho” é 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 “Transformação em árvore e desempenho”?

Como o Java 8+ trata 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 4 de 4.

Quanto tempo leva a aula “Transformação em árvore e desempenho”?

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

  1. Como HashMap funciona
  2. O contrato de equals/hashCode
  3. Implementando hashCode
  4. Transformação em árvore e desempenho
← Voltar para Java Academy