Classe Java LinkedHashSet | W3Docs Learn Java

LinkedHashSet<E> é HashSet<E> com uma promessa extra: ao iterar, você obtém os elementos na ordem em que foram inseridos pela primeira vez. O mecanismo de tabela hash é idêntico — mesmos buckets, mesmo fator de carga, mesmo add, remove e contains em tempo quase constante — mas cada entrada carrega dois ponteiros extras (before, after) que encadeiam as entradas em uma lista duplamente ligada conforme são adicionadas. A iteração percorre essa lista, não o array de buckets.

Se você quer desempenho de conjunto hash e uma ordem de iteração determinística e previsível, LinkedHashSet é a resposta. É quase um upgrade gratuito para os casos em que a ordem não especificada do HashSet já causou problemas.

A regra "primeira inserção vence"

A ordem é fixada pela primeira vez que um elemento é inserido. Re-adicionar um elemento existente não o move:

Set<String> s = new LinkedHashSet<>();
s.add("a");
s.add("b");
s.add("c");
s.add("a");   // already present — returns false, order unchanged
System.out.println(s);   // [a, b, c]

Isso o torna a ferramenta certa para "lembrar a ordem em que as tags chegaram" ou "registrar eventos únicos em ordem cronológica." Se você remover um elemento e re-adicioná-lo, ele vai para o final da lista — a posição estava vinculada à inserção atual, e a nova é a única que resta.

O custo: ponteiros e mais ponteiros

O mecanismo de ordenação extra tem um custo. Cada entrada armazena não apenas (hash, key, next-in-bucket) como o HashSet, mas (hash, key, next-in-bucket, before, after). São duas referências extras por elemento — aproximadamente 16 bytes extras em uma JVM de 64 bits. Para um conjunto de 10 milhões de Longs, isso representa cerca de 160 MB extras. Para a maioria do código de aplicação isso não é nada; para estruturas de dados do tamanho de cache, faz diferença.

Em troca, você obtém O(1) em cada operação (igual ao HashSet) mais uma ordem de iteração estável que não depende do fator de carga, do rehash, da distribuição do hash ou da versão da JVM.

O custo de iteração é proporcional ao tamanho, não à capacidade

Há um bônus sutil sobre o HashSet: percorrer um LinkedHashSet segue a lista ligada, visitando exatamente size entradas. Iterar um HashSet percorre todos os buckets, visitando aproximadamente capacity slots — incluindo os vazios. Para um conjunto escassamente populado, isso pode ser uma diferença significativa. Se você construir um conjunto, expandi-lo bem além dos elementos que vai manter e depois iterar com frequência, o LinkedHashSet pode na verdade iterar mais rápido.

Quando escolhê-lo

O fluxo de decisão:

A ordem não importa, você só precisa de verificação rápida de pertencimento → HashSet. Menor e mais simples.
Você quer que a ordem de inserção seja lembrada → LinkedHashSet. Mesma velocidade para add/contains, iteração previsível.
Você quer ordem classificada → TreeSet. Algoritmo diferente, operações em tempo logarítmico.

O motivo mais comum para escolher LinkedHashSet é defensivo: você está construindo uma API pública que retorna um Set, e não quer que os chamadores dependam da ordem arbitrária do HashSet. Um LinkedHashSet é a coisa mais gentil que você pode retornar — tem o mesmo contrato que um Set, mas a iteração é reproduzível entre execuções e JVMs, o que torna a saída visível ao usuário estável e os testes mais fáceis de escrever.

Um exemplo prático: tags únicas em ordem de chegada

O programa abaixo constrói dois conjuntos a partir do mesmo fluxo de entradas de tags: um com HashSet, outro com LinkedHashSet. A ordem de iteração do HashSet depende da JVM (é estável mas arbitrária para uma determinada JVM); a ordem do LinkedHashSet é exatamente a ordem em que os elementos únicos apareceram pela primeira vez. Em seguida, mostra a regra de "remover e re-adicionar" e, por fim, constrói um deduplicador que preserva a ordem em apenas duas linhas.

java— editable, runs on the server

import java.util.*;
import java.util.stream.*;

public class LinkedHashSetShowcase {
  public static void main(String[] args) {
    String[] events = { "login", "view", "purchase", "view", "logout", "login", "view" };

Set<String> hashed = new HashSet<>();
    Set<String> linked = new LinkedHashSet<>();
    for (String e : events) { hashed.add(e); linked.add(e); }

System.out.println("input:    " + Arrays.toString(events));
    System.out.println("HashSet:        " + hashed + "   (order may be anything)");
    System.out.println("LinkedHashSet:  " + linked + "   (first-insertion order)");

// --- The 'first-insertion wins' rule ---
    Set<String> demo = new LinkedHashSet<>();
    demo.add("a"); demo.add("b"); demo.add("c");
    demo.add("a");                 // already there — order unchanged
    System.out.println("\nre-add 'a':       " + demo);
    demo.remove("a"); demo.add("a"); // gone then back — moves to end
    System.out.println("remove+re-add 'a': " + demo);

// --- Order-preserving deduplicator in two lines ---
    List<Integer> noisy = List.of(3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5);
    List<Integer> deduped = noisy.stream()
        .collect(Collectors.toCollection(LinkedHashSet::new))
        .stream().toList();
    System.out.println("\nnoisy:    " + noisy);
    System.out.println("deduped:  " + deduped + "   (order preserved)");

// --- Iteration cost: LinkedHashSet visits size entries, not capacity slots ---
    Set<Integer> big = new LinkedHashSet<>(2_000_000); // huge capacity, few elements
    for (int i = 0; i < 10; i++) big.add(i);
    long t0 = System.nanoTime();
    int sum = 0;
    for (int x : big) sum += x;
    long t1 = System.nanoTime();
    System.out.println("\nsum of " + big.size() + " elements in a " + 2_000_000
        + "-bucket set: " + sum + "  in " + (t1 - t0) + " ns");
  }
}

O que observar na execução:

O LinkedHashSet imprimiu os eventos únicos na ordem em que apareceram pela primeira vez. O HashSet os imprimiu em uma outra ordem qualquer — o que quer que o layout de buckets determinasse.
Re-adicionar "a" não alterou a ordem em nada. Removê-lo e re-adicioná-lo o moveu para o final. A primeira inserção é a que ancora a posição.
O deduplicador que preserva a ordem é uma linha quando você conhece o truque: colete em um LinkedHashSet, depois volte para uma lista.
A varredura de 10 elementos em um LinkedHashSet de 2 000 000 buckets percorreu exatamente 10 entradas; um HashSet com a mesma estrutura teria varrido todos os buckets vazios entre eles.

O que vem a seguir

A terceira implementação padrão de Set oferece algo que nem o HashSet nem o LinkedHashSet podem: iteração classificada e a capacidade de fazer consultas de intervalo como "todas as tags entre a e m." O TreeSet é o próximo.

Prática

O que o `LinkedHashSet` oferece que o `HashSet` comum não oferece?

Iteração na ordem em que os elementos foram inseridos pela primeira vez, ao custo de duas referências extras por entradaIteração classificada pela ordenação natural dos elementosOperações thread-safe usando bloqueios internosBusca em O(log n) em vez de O(1), com ordem estável como efeito colateral