Java HashSet

HashSet<E> é a implementação que você escolhe primeiro quando quer um conjunto. Ela é baseada em uma tabela hash — internamente, é um HashMap com um valor fictício — então add, remove e contains têm O(1) esperado: o custo é um hash do elemento mais uma ou duas verificações de igualdade, independentemente de quantos elementos já estão no conjunto. Essa é a propriedade que torna os hash sets a resposta certa para perguntas do tipo "já vi isso antes?", passagens de deduplicação e qualquer verificação de pertencimento que seria quadrática com uma List.

O que "tempo quase constante" realmente significa

Tempo constante não é gratuito; é amortizado. Cada operação faz aproximadamente o seguinte:

1. Calcula e.hashCode(). Mistura os bits altos e baixos para que um hash como 0x...0000 não colapse no bucket 0.
2. Consulta o bucket em bucketIndex = hash & (table.length - 1).
3. Percorre a cadeia encadeada do bucket (ou, desde o Java 8, uma pequena árvore balanceada se a cadeia ficou longa) chamando equals até encontrar o elemento ou chegar ao fim.

O passo 3 é onde o custo fica ruim se seu hashCode for inadequado. Com um hash sensato, a cadeia tem um ou dois elementos; com um hash constante, ela tem todos os elementos que você já inseriu. Essa é a diferença entre O(1) e O(n) por operação.

Capacidade, fator de carga e o rehash

Um HashSet tem um array de buckets subjacente. Dois parâmetros do construtor o controlam:

• Capacidade inicial — o número inicial de buckets. Padrão é 16. Arredondado para uma potência de dois.
• Fator de carga — a razão entre elementos e buckets na qual a tabela dobra de tamanho. Padrão é 0,75.

Quando size / capacity excede o fator de carga, o conjunto executa rehash: aloca um novo array com o dobro do tamanho e redistribui todos os elementos. Um rehash é O(n) — esse é o custo amortizado entre os inserts O(1) anteriores a ele. Pré-dimensionar um conjunto que você sabe que terá ~1 000 000 de elementos economiza vinte duplicações:

Set<Long> ids = new HashSet<>(1_500_000); // skip the doublings up to ~1M

Fatores de carga menores (ex.: 0,5) desperdiçam memória, mas reduzem colisões; fatores maiores (ex.: 0,9) empacotam mais, mas alongam as cadeias. O padrão 0,75 é um equilíbrio calibrado pela Sun há décadas e ainda funciona bem — não o altere sem um benchmark.

Null, ordenação, segurança de threads

Três regras:

1. Um elemento null é permitido. O HashSet o armazena no bucket 0 com um hash especial de 0. Isso é uma conveniência deliberada — Map.of/Set.of e TreeSet proíbem null.
2. Nenhuma ordem de iteração é garantida. A ordem muda quando a tabela executa rehash e não é consistente entre diferentes JVMs. Se precisar de ordem de inserção, use LinkedHashSet; se precisar de ordem classificada, use TreeSet.
3. Não é thread-safe. Mutação concorrente corromperá a estrutura. Para código multi-thread, use ConcurrentHashMap.newKeySet() (uma visão Set de um mapa concorrente) ou envolva com Collections.synchronizedSet.

hashCode é sua responsabilidade

Colocar sua própria classe em um HashSet só funciona se você sobrescrever hashCode e equals de forma consistente. O contrato de Object:

• Se a.equals(b), então a.hashCode() == b.hashCode().
• Se a.hashCode() == b.hashCode(), a.equals(b) ainda pode ser false (uma colisão).

Quebrar a primeira parte do contrato é a fonte mais comum de bugs do tipo "adicionei, mas contains retorna false". IDEs modernas e a palavra-chave record geram ambos os métodos para você — use-os.

record Tag(String name) {}            // hashCode/equals auto-generated
Set<Tag> tags = new HashSet<>();
tags.add(new Tag("java"));
System.out.println(tags.contains(new Tag("java"))); // true

A armadilha do elemento mutável

Um bug mais sutil: armazenar um objeto cujo hashCode depende de campos mutáveis e depois mutá-lo após a inserção. O hash que decidiu em qual bucket o elemento vive foi calculado no momento da inserção; depois que você altera um campo do qual o hash depende, o objeto está no bucket "errado" e contains percorre uma cadeia que não o inclui — mesmo sendo exatamente a mesma referência.

class Box {
    int n;
    Box(int n) { this.n = n; }
    @Override public boolean equals(Object o) {
        return o instanceof Box b && b.n == n;
    }
    @Override public int hashCode() { return Integer.hashCode(n); }
}

Box box = new Box(1);
Set<Box> set = new HashSet<>();
set.add(box);
box.n = 2;                  // mutate a field hashCode depends on
System.out.println(set.contains(box)); // false — element is now in the wrong bucket

Note que isso só é problemático quando hashCode lê estado mutável. StringBuilder, por exemplo, usa hashing de identidade, então mutá-lo nunca o move entre buckets — mas depender disso é frágil. A solução não é ser esperto; é colocar elementos imutáveis em hash sets. String, Integer, seus próprios records, DTOs recém-criados como snapshots. Se precisar de um conjunto com chave baseada em algum estado mutável, use uma projeção imutável dele como chave.

Um exemplo prático: dedup, pertencimento e capacidade

O programa abaixo demonstra os quatro motivos pelos quais você escolhe um HashSet: deduplicação, testes de pertencimento rápidos, álgebra de conjuntos e o custo de um hashCode ruim.

O que levar em conta:

• O loop de deduplicação é O(n) — cada add é de tempo constante, e o unique.size() final é o número de entradas distintas.
• Um contains em um conjunto de 1 000 000 de elementos retornou em microssegundos. Essa é a propriedade que torna o HashSet a ferramenta de teste de pertencimento do JDK.
• O record Tag obtém equals/hashCode gratuitamente, então dois objetos Tag("java") colapsam em um único elemento.
• O exemplo com Box é a armadilha: o mesmo objeto, mutado após a inserção de forma que seu hashCode mudou, agora reporta contains(box) == false. Coloque elementos imutáveis em hash sets.

O que vem a seguir

O HashSet não garante nenhuma ordem de iteração. Se você precisa lembrar a ordem em que inseriu os elementos — por exemplo, está construindo uma lista de tags e o usuário espera ver as tags na ordem em que foram adicionadas — a ferramenta certa é LinkedHashSet. Esse é o próximo capítulo.

Prática