A Classe HashSet

Entender HashSet, a implementação padrão de Set: elementos são armazenados em uma tabela hash, o que dá add/remove/contains em tempo médio constante ao custo de qualquer garantia de ordem de iteração.

• Teste rápido de pertencimento (contains) quando a ordem genuinamente não importa.
• Deduplicar uma coleção de valores rapidamente.
• Pré-dimensionar a tabela via o construtor de capacidade/fator de carga quando a quantidade final de elementos é aproximadamente conhecida, para evitar rehashing durante um grande lote de inserções.

HashSet estende AbstractSet

java
class HashSet<E>

HashSet implementa Set<E> e não define nenhum método adicional além do que AbstractSet/Set/Collection já fornecem — sua contribuição está inteiramente em como os elementos são armazenados, não em uma nova superfície de API. Quatro construtores:

java
HashSet<String> a = new HashSet<>();                        // default capacity 16, load factor 0.75
HashSet<String> b = new HashSet<>(List.of("x", "y"));        // initialized from a collection
HashSet<String> c = new HashSet<>(64);                       // initial capacity 64
HashSet<String> d = new HashSet<>(64, 0.5f);                  // capacity 64, load factor 0.5

O fator de carga (também chamado de load factor) controla o quão cheia a tabela pode ficar, como fração da capacidade, antes de ser redimensionada para cima — 0.75 por padrão, o que significa que a tabela aproximadamente dobra assim que fica três quartos cheia.

A busca depende de hashCode() e equals()

O hash code de um elemento determina em qual bucket ele cai; equals() então distingue elementos que compartilham um bucket. Ambos precisam estar corretos e consistentes entre si para que add/contains/remove se comportem corretamente — é o mesmo contrato de Object do qual toda estrutura baseada em hash no JDK depende.

Veja acontecendo: add() espalhando elementos pelos buckets

Cada add(element) calcula element.hashCode(), espalha seus bits e aplica uma máscara contra capacity - 1 para escolher um bucket — o mesmo mecanismo que HashMap usa, já que HashSet é um wrapper fino em torno de um:

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

java
HashSet<String> hs = new HashSet<>();
hs.add("Beta"); hs.add("Alpha"); hs.add("Eta");
hs.add("Gamma"); hs.add("Epsilon"); hs.add("Omega");
System.out.println(hs); // [Gamma, Eta, Alpha, Epsilon, Omega, Beta] — order is table-layout dependent, not insertion order

A ordem exata depende do hash code de cada elemento e da capacidade atual da tabela, não da ordem em que os elementos foram adicionados.

• Sem garantia de ordem de iteração, e ela pode mudar entre execuções ou após um resize — se uma ordem estável importa, use LinkedHashSet (ordem de inserção); se uma ordem ordenada importa, use TreeSet.

• Mutar um campo envolvido no hashCode() de um elemento depois que ele já está no set quebra buscas silenciosamente — o elemento continua no bucket para o qual seu hash antigo apontava, então contains()/remove() com um objeto aparentemente igual pode retornar false/não fazer nada em vez de encontrá-lo:

  java
  class Point { int x; /* hashCode() based on x */ }
  Point p = new Point(1);
  HashSet<Point> set = new HashSet<>();
  set.add(p);
  p.x = 2;              // mutated after insertion
  set.contains(p);      // may return false — p is now in the wrong bucket

• Operações O(1) em média assumem um hashCode() razoavelmente bem distribuído — uma função de hash ruim que colide muito degrada add/contains/remove até O(n), já que todo elemento colidente precisa ser checado com equals().

• HashSet não é sincronizado — mesma ressalva de ArrayList/LinkedList para modificação estrutural concorrente ou dentro de um loop.