LinkedHashSet/LinkedHashMap

1. O que são LinkedHashSet e LinkedHashMap?

A biblioteca padrão do Java possui várias implementações de coleções Set e Map. As mais conhecidas são HashSet e HashMap. Essas estruturas fornecem acesso rápido aos elementos via hash, mas não garantem nenhuma ordem ao iterar sobre os elementos. Quando a ordem de iteração é importante, entram em cena LinkedHashSet e LinkedHashMap.

• LinkedHashSet é um Set que lembra a ordem de adição dos elementos.
• LinkedHashMap é um Map que lembra a ordem de inserção dos pares chave–valor (ou, opcionalmente, a ordem de acesso).

Elas são implementadas como HashSet/HashMap “comuns”, mas com um lista duplamente encadeada adicional para armazenar a ordem dos elementos.

2. Ordem de inserção e ordem de acesso

Ordem de inserção

Por padrão, LinkedHashSet e LinkedHashMap garantem que, ao iterar, os elementos são retornados na mesma ordem em que foram adicionados (for-each/iterador).

Set<String> set = new LinkedHashSet<>();
set.add("A");
set.add("B");
set.add("C");
for (String s : set) {
    System.out.println(s);
}
// Saída: A B C

Map<Integer, String> map = new LinkedHashMap<>();
map.put(1, "one");
map.put(2, "two");
map.put(3, "three");
for (Integer key : map.keySet()) {
    System.out.println(key + " -> " + map.get(key));
}
// Saída: 1 -> one, 2 -> two, 3 -> three

Ordem de acesso (apenas para LinkedHashMap)

O LinkedHashMap possui um modo de ordenação por último acesso (access order). Se, ao criar o mapa, você passar true como terceiro parâmetro do construtor, então, a cada acesso a um elemento (get/put), ele é movido para o fim da lista.

Map<Integer, String> lruMap = new LinkedHashMap<>(16, 0.75f, true);
lruMap.put(1, "one");
lruMap.put(2, "two");
lruMap.put(3, "three");

lruMap.get(2); // Acesso à chave 2

for (Integer key : lruMap.keySet()) {
    System.out.println(key);
}
// Saída: 1 3 2 (2 é o último porque foi acessado)

Cache LRU via removeEldestEntry

O principal diferencial do LinkedHashMap é a implementação simples de um cache LRU (Least Recently Used, “menos recentemente usado”). Basta sobrescrever o método removeEldestEntry(Map.Entry<K,V> eldest): se ele retornar true, o elemento mais “antigo” é removido ao adicionar um novo.

class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int maxSize;

    public LRUCache(int maxSize) {
        super(maxSize, 0.75f, true); // true — ordem por acesso
        this.maxSize = maxSize;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > maxSize;
    }
}

// Uso:
LRUCache<Integer, String> cache = new LRUCache<>(3);
cache.put(1, "one");
cache.put(2, "two");
cache.put(3, "three");
cache.get(1); // Tornamos 1 o mais 'recente'
cache.put(4, "four"); // 2 será removido (o mais antigo)
System.out.println(cache.keySet()); // [3, 1, 4]

3. Custo de memória e desempenho: LinkedHashSet/LinkedHashMap vs HashSet/HashMap

Como funciona

Por dentro, é quase como um HashSet/HashMap comum, mas cada elemento também é armazenado em uma lista duplamente encadeada. Essa estrutura adicional “lembra” a ordem de inserção/acesso.

Custo de memória

Devido às referências prev/next em cada nó, é necessária mais memória. Para milhões de elementos isso é perceptível; para casos típicos, é um preço justificável pela ordem determinística.

Custo de desempenho

As operações básicas de adicionar/buscar/remover continuam amortizadas em O(1). A iteração é um pouco mais lenta por causa do percurso da lista, mas na maioria dos casos a diferença é mínima. E o cenário “remover o mais antigo” (LRU) é implementado com muita eficiência, pois o elemento “mais velho” está sempre na cabeça da lista.

Resumo: se a ordem é importante — escolha LinkedHashSet/LinkedHashMap. Se você precisa economizar memória e a ordem não importa — HashSet/HashMap são suficientes.

4. Cache, saída determinística, testes estáveis

Cache (LRU)

O LinkedHashMap é a base ideal para caches com limite de tamanho e remoção automática dos elementos “antigos”. Aplica-se em bibliotecas/frameworks, no trabalho com arquivos, imagens e resultados de computações.

Saída determinística

Para relatórios, exportações e serialização, onde é crítico ter uma representação previsível dos dados, use LinkedHashSet/LinkedHashMap. Isso é especialmente importante para testes — a ordem não “oscila” de uma execução para outra.

Testes estáveis

Em testes unitários, é comum comparar coleções esperadas com as obtidas. Se a ordem não é garantida, os testes podem ficar “flaky”. Com as implementações “linked”, a determinística garante estabilidade.

Exemplo: comparação entre HashMap e LinkedHashMap

Map<Integer, String> hashMap = new HashMap<>();
Map<Integer, String> linkedMap = new LinkedHashMap<>();

for (int i = 1; i <= 5; i++) {
    hashMap.put(i, "val" + i);
    linkedMap.put(i, "val" + i);
}

System.out.println(hashMap.keySet());   // A ordem pode ser qualquer uma!
System.out.println(linkedMap.keySet()); // Sempre 1, 2, 3, 4, 5

5. LinkedList vs ArrayDeque para filas

LinkedList

• Implementa as interfaces List, Deque, Queue.
• Lista duplamente encadeada: inserções/remoções rápidas no início e no fim.
• Pode ser usada como fila (FIFO), pilha (LIFO) e fila dupla.

ArrayDeque

• Implementa Deque, Queue (mas não List).
• Baseada em array, expande-se automaticamente.
• Geralmente mais rápida que LinkedList para operações de fila/pilha; menor overhead.
• Não suporta elemento null.

Quando usar o quê?

• Filas e pilhas — quase sempre ArrayDeque.
• Muitas inserções/remoções no meio e você também precisa de lista — LinkedList.
• Set/Map com ordem — LinkedHashSet/LinkedHashMap.

Exemplo: fila de tarefas

Queue<String> queue = new ArrayDeque<>();
queue.add("task1");
queue.add("task2");
System.out.println(queue.poll()); // task1

Exemplo: pilha

Deque<String> stack = new ArrayDeque<>();
stack.push("first");
stack.push("second");
System.out.println(stack.pop()); // second

Conclusão:
— Para filas e pilhas — ArrayDeque.
— Para listas com muitas inserções no meio — LinkedList.
— Para Set/Map com ordem — LinkedHashSet/LinkedHashMap.

6. Erros comuns ao trabalhar com LinkedHashSet/LinkedHashMap

Erro nº 1: esperar que HashSet/HashMap preservem a ordem.
HashSet/HashMap não garantem ordem. Se ela for importante — use LinkedHashSet/LinkedHashMap.

Erro nº 2: usar LinkedHashMap para cache sem sobrescrever removeEldestEntry.
Para LRU é preciso sobrescrever removeEldestEntry, caso contrário o mapa crescerá sem limites.

Erro nº 3: usar LinkedList para filas/pilhas sem necessidade.
Na maioria dos casos, ArrayDeque é mais rápido e econômico.

Erro nº 4: esperar ordenação de LinkedHashMap.
LinkedHashMap preserva a ordem de inserção/acesso, mas não ordena por chave. Para ordenação — TreeMap.

Erro nº 5: adicionar null em ArrayDeque.
ArrayDeque não suporta elementos null — lançará NullPointerException.

Erro nº 6: comparar coleções sem considerar a ordem.
Ao comparar LinkedHashSet/LinkedHashMap com HashSet/HashMap comuns, leve em conta as diferenças na ordem dos elementos.