Java LinkedHashMap

LinkedHashMap<K, V> é um HashMap<K, V> com uma lista duplamente encadeada percorrendo cada entrada. A tabela hash faz seu trabalho habitual — O(1) put, get, remove — e a lista encadeada fornece uma ordem de iteração garantida e previsível. Por padrão, essa ordem é a ordem de inserção; ative um flag no construtor e ela se torna ordem de acesso, o bloco de construção de um cache LRU (least-recently-used).

Dois ordenamentos, uma classe

Os construtores espelham os do HashMap, mais um adicional:

new LinkedHashMap<>();                              // insertion order
new LinkedHashMap<>(16, 0.75f, false);              // insertion order, explicit
new LinkedHashMap<>(16, 0.75f, true);               // ACCESS order

Esse terceiro boolean é o flag accessOrder. Com ele definido como false (o padrão), cada put de uma nova chave adiciona a entrada ao final da lista encadeada, e puts de uma chave existente deixam sua posição inalterada. Com ele definido como true, todo get, put ou getOrDefault que toca uma chave move essa entrada para o final da lista — a entrada acessada mais recentemente está sempre no final; a menos recentemente acessada está sempre no início.

Esse segundo modo é raro no código de aplicação, mas o único lugar onde você o vê é exatamente onde mais precisa: na implementação de um cache.

Iteração em ordem de inserção é o uso mais comum

Em 90% dos casos você usa LinkedHashMap porque quer uma saída estável. Exemplos:

• Retornar um Map<String, Object> de um endpoint de serialização JSON e querer que os campos apareçam na ordem em que foram inseridos.
• Registrar o conteúdo de um mapa em ordem determinística para diffs.
• Construir configurações onde a ordem importa (pense em: cadeia de middlewares, ordem de cabeçalhos, pipeline de validação).
• Retornar um Map de uma API pública sem que os chamadores dependam da ordem arbitrária do HashMap.

O custo em relação ao HashMap são duas referências extras por entrada (os ponteiros before e after). Para mapas do tamanho de uma configuração, isso não importa; para loops intensos sobre mapas muito grandes, pode ser preferível usar um HashMap se puder.

Iteração é proporcional ao tamanho

Um benefício adicional: iterar um LinkedHashMap percorre a lista encadeada, que contém exatamente size entradas. Iterar um HashMap percorre todos os slots de bucket — incluindo os vazios. Para um mapa com baixa ocupação, a diferença é significativa.

Construindo um cache LRU

O recurso mais poderoso do modo de acesso é o hook protegido removeEldestEntry. Ele é chamado após cada put e, se retornar true, o mapa remove sua primeira entrada (a mais antiga). Combinando os dois:

class LruCache<K, V> extends LinkedHashMap<K, V> {
  private final int max;
  LruCache(int max) { super(16, 0.75f, true); this.max = max; }
  @Override protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
    return size() > max;
  }
}

Doze linhas para um cache LRU sem segurança de thread, mas totalmente funcional. Cada get reposiciona a entrada para o final; cada put chama removeEldestEntry; quando o tamanho excede max, a entrada no início (a menos recentemente acessada) é removida.

Para LRU com segurança de thread, encapsule com Collections.synchronizedMap ou — melhor ainda — use uma biblioteca de cache real (Caffeine), pois as atualizações de ordem de acesso tornam cada get uma escrita internamente e o wrapper sincronizado simples serializa todas as leituras. Mas para código single-thread, este é o truque clássico e vale a pena conhecer.

Valores nulos e demais regras

Igual ao HashMap: uma chave null, qualquer número de valores null. Não é thread-safe. A igualdade é a igualdade estrutural definida por Map — um LinkedHashMap e um HashMap com as mesmas entradas são equals. A ordem de iteração não faz parte da igualdade; é apenas o que você obtém ao iterar.

Exemplo prático: ordem de inserção, ordem de acesso e um cache LRU

O programa abaixo constrói uma pequena cadeia de middlewares em ordem de inserção, contrasta a iteração de HashMap vs LinkedHashMap com os mesmos dados e, em seguida, implementa um pequeno cache LRU observando sua evicção.

O que observar na execução:

• O pipeline itera na ordem log → auth → rateLimit → handler — exatamente a ordem de inserção. Um HashMap simples ainda teria as quatro entradas, mas a ordem seria arbitrária.
• HashMap e LinkedHashMap com os mesmos dados imprimem em ordens diferentes; o LinkedHashMap corresponde a keys e o HashMap não.
• O cache LRU reordenou quando get("a") foi chamado — a foi para o final da lista, tornando b o mais antigo. O próximo put("d", "D") disparou a evicção de b, não de a. É a regra de ordem de acesso em ação.

O que vem a seguir

A terceira implementação padrão de Map oferece algo que nenhuma das baseadas em hash pode: iteração ordenada por chave e consultas de intervalo (subMap, headMap, tailMap, firstKey, lastKey). TreeMap é o próximo; a estrutura é idêntica à do TreeSet por baixo — literalmente o mesmo código de árvore rubro-negra.

Prática