LinkedHashSet.

Serie - Fundamentos de Estrutura de Dados Elementar com Java.

LinkedHashSet. Como funciona o Hash Table com Set e uma Linked List vinculada.

Inicialmente, uma ressalva.

  Aqui, evitarei entrar em minúcias sobre o LinkedHashSet, uma vez que, no próprio código-fonte Java, é explicitamente indicado que o LinkedHashMap é, de certa maneira, confuso quanto ao seu funcionamento. Se até os engenheiros do Java consideram isso, quem sou eu para discordar? Além disso, como o LinkedHashSet se baseia no LinkedHashMap, a explanação fica um tanto desafiadora. Portanto irei simplificar, mantendo as informações essenciais para uma compreensão clara.

A Estrutura

  O LinkedHashSet representa uma estrutura de dados fascinante, assemelhando-se ao HashSet na prevenção de duplicatas, mas com uma distinção crucial: aqui, a ordem de inserção é preservada, ao contrário do HashSet convencional. Mas como essa façanha é alcançada? O LinkedHashSet utiliza tanto a tabela de hash quanto uma lista encadeada, sendo esta última responsável por manter a ordem de inserção. Em relação aos atributos, a essência reside nos seguintes pontos:

• chave (key): similar ao HashSet, é gerada a partir do valor;
• valor (value): nossa informação central;
• próximo (next): gerenciamento de colisões de hash;
• depois (after): atributo crucial para a manutenção da ordem, apontando para o elemento subsequente;
• antes (before): outro atributo crucial para a ordem, apontando para o elemento anterior.

  Nota: O desempenho do LinkedHashSet é ligeiramente inferior ao do HashSet, devido ao custo adicional associado à manutenção da lista encadeada.

Exemplificando

  Vamos agora examinar o mesmo exemplo utilizado no HashSet, porém com a distinção de que nossos dados agora se apresentam ordenados. Vale notar que, dada a maturidade esperada dos leitores, apresentarei o exemplo já contemplando colisões de hash:

var names = new LinkedHashSet<String>();
names.add("John Carmack");
names.add("Ea");
names.add("Cormen");
names.add("FB");
System.out.println(names);

  Conforme observado, a ordem de inserção foi preservada. Pode ainda pairar alguma perplexidade quanto aos atributos after e before responsáveis por esse feito, mas sem preocupações; o diagrama oferece uma clara representação de como esses atributos desempenham esse papel.

  imagem mental:

Vantagens e Desvantagens

Vantagens

• 1 - Mantém a ordem de inserção dos elementos, além de fornecer acesso rápido.
• 2 - Implementação simples de uma tabela de hash com uma lista encadeada vinculada.

Desvantagens

• 1 - Ligeiramente menos eficiente do que HashSet em termos de velocidade.
• 2 - Ocupa ligeiramente mais espaço que HashSet devido à necessidade da lista encadeada vinculada

Uso comum

  Manutenção da ordem de inserção dos elementos em uma coleção semelhante ao HashSet.

  Cenário de uso: Em um sistema de registro de eventos, um LinkedHashSet pode ser utilizado para armazenar eventos na ordem em que ocorreram, facilitando a análise cronológica.