Java HashSet

Um conjunto (Set) é uma coleção que não aceita repetidos: cada elemento está lá uma vez, ou não está. É a ferramenta certa para perguntas como "quais cidades diferentes aparecem?", "esse e-mail já foi cadastrado?" ou "quem faz as duas matérias?". O HashSet é a implementação mais usada, e responde a "está aqui?" quase instantaneamente.

Você vai aprender
  • Criar um HashSet; por que o add devolve true ou false.
  • contains, remove, size, e por que não existe get(i).
  • Tirar os repetidos de uma lista numa linha.
  • Operações de conjunto: união (addAll), interseção (retainAll) e diferença (removeAll).
  • A ordem (real) de um HashSet, o LinkedHashSet e o Set.of.
  • Por que, com objetos seus, o conjunto precisa de equals e hashCode.

A ideia: um álbum de figurinhas

Quem já completou um álbum de figurinhas sabe: a figurinha 27 ou está colada, ou não está. Tirar outra 27 do pacote não muda nada no álbum: ela vai para o monte das repetidas. Um conjunto funciona igual:

  • Colocar um elemento que já está lá não faz nada.
  • A pergunta mais importante é "tem a 27?", e não "qual é a 5ª figurinha?". Conjuntos não têm posições.

O HashSet é, por dentro, um HashMap que só usa as chaves. Por isso ele herda as duas características do HashMap: é muito rápido para achar um elemento e não guarda ordem.

Criar, acrescentar e perguntar

import java.util.HashSet;
import java.util.Set;

public class Main {
    public static void main(String[] args) {
        Set<String> cidades = new HashSet<>();
        System.out.println("add Recife: " + cidades.add("Recife"));
        System.out.println("add Natal:  " + cidades.add("Natal"));
        System.out.println("add Recife: " + cidades.add("Recife"));
        System.out.println(cidades + " tamanho " + cidades.size());

        System.out.println("contains(\"Natal\"): " + cidades.contains("Natal"));
        System.out.println("contains(\"natal\"): " + cidades.contains("natal"));
        System.out.println("remove(\"Natal\"): " + cidades.remove("Natal"));
        System.out.println("remove(\"Olinda\"): " + cidades.remove("Olinda"));
        System.out.println(cidades);
    }
}
Set<String> cidades = new HashSet<>();
Variável do tipo da interface Set ("conjunto"), objeto HashSet.
cidades.add("Recife")
Tenta colocar. Devolve true se o elemento entrou e false se ele já estava lá (e então nada muda).
cidades.contains("Natal")
"Contém Natal?" Esta é a especialidade do HashSet: a resposta é rápida mesmo com milhões de elementos.
cidades.remove("Natal")
Tira e devolve true; se não estava lá, devolve false.
$ javac Main.java
$ java Main
add Recife: true
add Natal:  true
add Recife: false                « já estava: recusado, sem erro
[Recife, Natal] tamanho 2
contains("Natal"): true
contains("natal"): false         « maiúscula faz diferença
remove("Natal"): true
remove("Olinda"): false
[Recife]

O false do terceiro add não é um erro: é uma informação. Ele permite fazer, numa linha só, "coloque e me diga se era novo". Isso resolve um problema clássico: achar repetidos.

import java.util.HashSet;
import java.util.Set;

public class Main {
    public static void main(String[] args) {
        String[] emails = {"ana@escola.com", "bruno@escola.com", "ana@escola.com", "carla@escola.com"};
        Set<String> vistos = new HashSet<>();
        for (String e : emails) {
            if (!vistos.add(e)) {
                System.out.println("Repetido: " + e);
            }
        }
        System.out.println("E-mails diferentes: " + vistos.size());
    }
}

$ javac Main.java
$ java Main
Repetido: ana@escola.com
E-mails diferentes: 3

if (!vistos.add(e)) se lê: "se não conseguiu acrescentar (porque já tinha visto), avise". Um único método faz a pergunta e guarda o e-mail.

Missão: a Ana abriu um pacote de figurinhas. Usando um Set<Integer> e o resultado do add, mostre Repetido: N para cada figurinha repetida e, no fim, Figurinhas diferentes: 4.

import java.util.HashSet;
import java.util.Set;

public class Main {
    public static void main(String[] args) {
        int[] pacote = {27, 5, 13, 27, 42, 5};
        Set<Integer> album = new HashSet<>();

        // para cada figurinha do pacote...

        System.out.println("Figurinhas diferentes: " + album.size());
    }
}

import java.util.HashSet;
import java.util.Set;

public class Main {
    public static void main(String[] args) {
        int[] pacote = {27, 5, 13, 27, 42, 5};
        Set<Integer> album = new HashSet<>();

        for (int f : pacote) {
            if (!album.add(f)) {
                System.out.println("Repetido: " + f);
            }
        }

        System.out.println("Figurinhas diferentes: " + album.size());
    }
}

Tirar os repetidos de uma lista

Todo conjunto tem um construtor que recebe outra coleção. Os repetidos ficam pelo caminho. Veja com os três tipos de conjunto do Java, e repare na ordem de cada um:

import java.util.*;

public class Main {
    public static void main(String[] args) {
        List<String> inscricoes = List.of("Carla", "Ana", "Bruno", "Ana", "Duda", "Carla", "Ana");
        System.out.println("Inscrições: " + inscricoes);

        Set<String> hash = new HashSet<>(inscricoes);
        Set<String> linked = new LinkedHashSet<>(inscricoes);
        Set<String> tree = new TreeSet<>(inscricoes);
        System.out.println("HashSet:       " + hash);
        System.out.println("LinkedHashSet: " + linked);
        System.out.println("TreeSet:       " + tree);
        System.out.println("Pessoas diferentes: " + hash.size());
    }
}

$ javac Main.java
$ java Main
Inscrições: [Carla, Ana, Bruno, Ana, Duda, Carla, Ana]
HashSet:       [Bruno, Carla, Ana, Duda]          « sem repetidos, ordem das "gavetas"
LinkedHashSet: [Carla, Ana, Bruno, Duda]          « sem repetidos, ordem da 1ª aparição
TreeSet:       [Ana, Bruno, Carla, Duda]          « sem repetidos, em ordem alfabética
Pessoas diferentes: 4

Se depois você precisar de uma lista de novo (para usar get(i), por exemplo), é o caminho inverso: new ArrayList<>(conjunto).

A ordem de um HashSet

Como no HashMap, o HashSet espalha os elementos em "gavetas" pelo hash code de cada um, e os devolve na ordem das gavetas. As mesmas sete frutas, inseridas na mesma ordem:

        String[] frutas = {"uva", "banana", "maçã", "kiwi", "abacaxi", "laranja", "pera"};
        Set<String> hash = new HashSet<>();
        Set<String> linked = new LinkedHashSet<>();
        for (String f : frutas) {
            hash.add(f);
            linked.add(f);
        }
        System.out.println("HashSet:       " + hash);
        System.out.println("LinkedHashSet: " + linked);
        for (String f : hash) {
            System.out.print(f + " ");
        }
        System.out.println();

$ java Main
HashSet:       [banana, pera, uva, kiwi, maçã, abacaxi, laranja]
LinkedHashSet: [uva, banana, maçã, kiwi, abacaxi, laranja, pera]
banana pera uva kiwi maçã abacaxi laranja           « o for-each segue a mesma ordem embaralhada

A ordem do HashSet é a mesma do HashMap da aula anterior, com as mesmas frutas: os dois usam o mesmo mecanismo. E vale o mesmo aviso: nunca dependa dela. Quer a ordem de inserção? LinkedHashSet. Quer ordem alfabética? TreeSet (veja TreeMap e TreeSet).

Operações de conjunto

A Ana tem duas turmas de reforço: Matemática e Física. Ela quer saber quem está em pelo menos uma, quem está nas duas e quem está só em Matemática. Na escola isso se chama união, interseção e diferença de conjuntos, e cada uma é um método:

import java.util.Set;
import java.util.TreeSet;

public class Main {
    public static void main(String[] args) {
        Set<String> matematica = new TreeSet<>(Set.of("Ana", "Bruno", "Carla", "Duda"));
        Set<String> fisica = new TreeSet<>(Set.of("Bruno", "Carla", "Edu"));

        Set<String> uniao = new TreeSet<>(matematica);
        uniao.addAll(fisica);

        Set<String> intersecao = new TreeSet<>(matematica);
        intersecao.retainAll(fisica);

        Set<String> diferenca = new TreeSet<>(matematica);
        diferenca.removeAll(fisica);

        System.out.println("Matemática: " + matematica);
        System.out.println("Física:     " + fisica);
        System.out.println("Pelo menos uma (addAll):  " + uniao);
        System.out.println("As duas (retainAll):      " + intersecao);
        System.out.println("Só Matemática (removeAll): " + diferenca);
        System.out.println("Física dentro de Matemática? " + matematica.containsAll(fisica));
    }
}

$ javac Main.java
$ java Main
Matemática: [Ana, Bruno, Carla, Duda]
Física:     [Bruno, Carla, Edu]
Pelo menos uma (addAll):  [Ana, Bruno, Carla, Duda, Edu]
As duas (retainAll):      [Bruno, Carla]
Só Matemática (removeAll): [Ana, Duda]
Física dentro de Matemática? false             « o Edu não faz Matemática
OperaçãoMétodoEm palavrasResultado
União (A ∪ B)a.addAll(b)"Junte em A tudo o que está em B."quem faz pelo menos uma
Interseção (A ∩ B)a.retainAll(b)retain = reter. "Mantenha em A só o que também está em B."quem faz as duas
Diferença (A − B)a.removeAll(b)"Tire de A tudo o que está em B."quem faz só a primeira
Subconjunto (B ⊂ A)a.containsAll(b)"A tem todos os de B?"true/false
Esses métodos alteram o conjunto que os chama

matematica.retainAll(fisica) apagaria a Ana e a Duda da própria turma de Matemática. Por isso o programa faz uma cópia antes (new TreeSet<>(matematica)) e opera na cópia. Usamos TreeSet aqui só para a saída sair em ordem alfabética; com HashSet o resultado é o mesmo, em outra ordem. Esses métodos também existem em listas (são de Collection).

Conjuntos prontos: Set.of

Set.of(…) cria um conjunto imutável. Ele é rigoroso: elemento repetido na criação é erro.

import java.util.Set;

public class Main {
    public static void main(String[] args) {
        Set<String> vogais = Set.of("a", "e", "i", "o", "u");
        System.out.println(vogais.contains("e") + " " + vogais.size());
        Set<String> erro = Set.of("a", "e", "a");
    }
}

$ javac Main.java
$ java Main
true 5
Exception in thread "main" java.lang.IllegalArgumentException: duplicate element: a
	at java.base/java.util.ImmutableCollections$SetN.<init>(ImmutableCollections.java:1164)
	at java.base/java.util.Set.of(Set.java:505)
	at Main.main(Main.java:7)

Como no Map.of, a ordem de um Set.of é embaralhada e pode mudar a cada execução, e add/remove dão UnsupportedOperationException. Quer tirar repetidos de dados que podem ter repetição? Use new HashSet<>(List.of(…)), que aceita repetidos na entrada.

Conjuntos de objetos seus: equals e hashCode

Com String e Integer, o conjunto sabe que "Ana" e "Ana" são iguais. E com uma classe criada por você? A Ana cria a classe Aluno e põe o mesmo aluno duas vezes:

import java.util.HashSet;
import java.util.Set;

class Aluno {
    String nome;
    int matricula;

    Aluno(String nome, int matricula) {
        this.nome = nome;
        this.matricula = matricula;
    }

    public String toString() {
        return nome + "#" + matricula;
    }
}

public class Main {
    public static void main(String[] args) {
        Set<Aluno> turma = new HashSet<>();
        turma.add(new Aluno("Ana", 101));
        turma.add(new Aluno("Ana", 101));
        System.out.println(turma + " tamanho " + turma.size());
        System.out.println(turma.contains(new Aluno("Ana", 101)));
    }
}

$ javac Main.java
$ java Main
[Ana#101, Ana#101] tamanho 2       « a "mesma" aluna entrou duas vezes!
false                              « e o contains não a encontra

Para o Java, são dois objetos diferentes, criados por dois new, que por acaso têm os mesmos dados. Sem instrução sua, "igual" quer dizer "o mesmo objeto na memória". Para o conjunto entender que dois alunos com o mesmo nome e matrícula são iguais, a classe precisa de dois métodos herdados de Object:

  • equals: diz quando dois objetos são iguais.
  • hashCode: o número que escolhe a "gaveta". Objetos iguais precisam ter o mesmo hashCode, senão vão para gavetas diferentes e o conjunto nem chega a compará-los com equals.
import java.util.HashSet;
import java.util.Objects;
import java.util.Set;

class Aluno {
    String nome;
    int matricula;

    Aluno(String nome, int matricula) {
        this.nome = nome;
        this.matricula = matricula;
    }

    @Override
    public boolean equals(Object o) {
        if (!(o instanceof Aluno outro)) return false;
        return matricula == outro.matricula && nome.equals(outro.nome);
    }

    @Override
    public int hashCode() {
        return Objects.hash(nome, matricula);
    }

    public String toString() {
        return nome + "#" + matricula;
    }
}

$ javac Main.java
$ java Main
[Ana#101] tamanho 1
true

Agora funciona. A explicação completa de equals, hashCode e do contrato entre os dois está na aula A Classe Object. Um atalho: um record já vem com equals e hashCode prontos, baseados nos seus campos:

record Aluno(String nome, int matricula) { }

$ java Main
[Aluno[nome=Ana, matricula=101]] tamanho 1

Qual conjunto usar?

ConjuntoOrdemVelocidadeQuando usar
HashSetNenhuma garantidaA mais rápidaO padrão: "tem ou não tem?", tirar repetidos.
LinkedHashSetA de inserçãoQuase igualTirar repetidos mantendo a ordem original.
TreeSetCrescente (A→Z, 1→9)Um pouco mais lentaPrecisa dos elementos sempre ordenados.
Set.of(…)EmbaralhadaRápidaConjunto fixo, que não muda.

Quando dá errado

"cannot find symbol … method get(int)": conjunto não tem posição

Este código tem um erro de propósito.

import java.util.HashSet;
import java.util.Set;

public class Main {
    public static void main(String[] args) {
        Set<String> cidades = new HashSet<>();
        cidades.add("Recife");
        System.out.println(cidades.get(0));
    }
}

$ javac Main.java
Main.java:8: error: cannot find symbol
        System.out.println(cidades.get(0));
                                  ^
  symbol:   method get(int)
  location: variable cidades of type Set<String>
1 error

O que quer dizer: "não encontrei o método get(int) na variável cidades, do tipo Set<String>". Conjuntos não têm "primeiro", "segundo"…

Como consertar: percorra com for-each, pergunte com contains, ou, se precisa mesmo de posições, copie para uma lista: new ArrayList<>(cidades).get(0).

O mesmo objeto aparece duas vezes no conjunto

O que aconteceu: a sua classe não tem equals e hashCode (ou tem só um dos dois). Veja a seção sobre equals e hashCode e A Classe Object.

Como consertar: escreva os dois métodos, ou transforme a classe num record.

IllegalArgumentException: duplicate element

O que aconteceu: o Set.of recebeu o mesmo elemento duas vezes.

Como consertar: tire o repetido, ou use new HashSet<>(List.of(…)) se os dados podem ter repetição.

Referência

MétodoO que fazDevolve
add(x)Coloca, se ainda não estivertrue se entrou, false se já estava
contains(x)Está no conjunto?boolean
remove(x)Tiratrue se estava
size(), isEmpty(), clear()Quantidade, vazio?, apagar tudo—
addAll(c)Uniãotrue se mudou
retainAll(c)Interseçãotrue se mudou
removeAll(c)Diferençatrue se mudou
containsAll(c)Contém todos de c?boolean
new HashSet<>(colecao)Conjunto a partir de outra coleção (tira repetidos)—
Set.of(…)Conjunto pronto e imutável—

Exercícios

1. O que o add devolve

O conjunto já tem "Recife". O que cidades.add("Recife") devolve?

2. Sem repetidos, na ordem

Complete para criar um conjunto, sem repetidos e na ordem original, a partir da lista nomes:

Set<String> unicos = new ;

3. Quem está nas duas

Complete para deixar em a só os elementos que também estão em b:

a.;

4. new HashSet<>(List.of(3, 1, 3, 2, 1)).size() vale:

5. A classe Produto não tem equals nem hashCode. Num HashSet, dois new Produto("café")…

Missão final: descubra quem faz Matemática e Física, com retainAll, sem estragar a turma de Matemática (faça uma cópia). A saída deve ser Fazem as duas: [Bruno, Carla] e Matemática continua: [Ana, Bruno, Carla, Duda].

import java.util.Set;
import java.util.TreeSet;

public class Main {
    public static void main(String[] args) {
        Set<String> matematica = new TreeSet<>(Set.of("Ana", "Bruno", "Carla", "Duda"));
        Set<String> fisica = new TreeSet<>(Set.of("Bruno", "Carla", "Edu"));

        Set<String> asDuas = matematica;
        asDuas.retainAll(fisica);
        System.out.println("Fazem as duas: " + asDuas);
        System.out.println("Matemática continua: " + matematica);
    }
}

import java.util.Set;
import java.util.TreeSet;

public class Main {
    public static void main(String[] args) {
        Set<String> matematica = new TreeSet<>(Set.of("Ana", "Bruno", "Carla", "Duda"));
        Set<String> fisica = new TreeSet<>(Set.of("Bruno", "Carla", "Edu"));

        Set<String> asDuas = new TreeSet<>(matematica);
        asDuas.retainAll(fisica);
        System.out.println("Fazem as duas: " + asDuas);
        System.out.println("Matemática continua: " + matematica);
    }
}

Resumo

  • Um Set não tem repetidos nem posições. HashSet é o padrão.
  • add devolve false quando o elemento já estava: ótimo para achar repetidos.
  • contains é a especialidade do HashSet: muito rápido.
  • new HashSet<>(lista) tira os repetidos; LinkedHashSet mantém a ordem; TreeSet ordena.
  • União addAll, interseção retainAll, diferença removeAll: alteram quem chama, então trabalhe numa cópia.
  • A ordem de um HashSet não é garantida; Set.of embaralha e recusa repetidos.
  • Objetos seus num conjunto precisam de equals e hashCode (ou ser um record).

Próxima aula: TreeMap e TreeSet, as coleções que se mantêm sempre ordenadas.