Qual é a diferença entre HashSet e List ?

StackOverflow https://stackoverflow.com/questions/6391738

  •  29-10-2019
  •  | 
  •  

Pergunta

Você pode explicar qual é a diferença entre HashSet<T> e List<T> no .NET?

Talvez você possa explicar com um exemplo em que casos HashSet<T> deve ser preferido em relação a List<T>?

Foi útil?

Solução

Diferente de uma lista <> ...

  1. Um HashSet é uma lista sem membros duplicados.

  2. Como um HashSet é restrito a conter apenas entradas exclusivas, a estrutura interna é otimizada para pesquisa (em comparação com uma lista) - é consideravelmente mais rápida

  3. Adicionar a um HashSet retorna um booleano - falso se a adição falhar devido a já existir no conjunto

  4. Pode realizar operações matemáticas de conjunto em um Set: Union / Intersection / IsSubsetOf etc.

  5. HashSet não implementa IList apenas ICollection

  6. Você não pode usar índices com um HashSet, apenas enumeradores.

O principal motivo para usar um HashSet seria se você estiver interessado em realizar operações Set.

Dados 2 conjuntos: hashSet1 e hashSet2 

 //returns a list of distinct items in both sets
 HashSet set3 = set1.Union( set2 );

voa em comparação com uma operação equivalente usando LINQ.Também é mais legal de escrever!

Outras dicas

Um HashSet<T> é uma classe projetada para fornecer a você uma pesquisa de O(1) para contenção (ou seja, essa coleção contém um objeto específico e me diga a resposta rapidamente).

Um List<T> é uma classe projetada para fornecer uma coleção com O(1) acesso aleatório que pode crescer dinamicamente (pense em uma matriz dinâmica).Você pode testar a contenção em tempo O(n) (a menos que a lista seja classificada, então você pode fazer uma pesquisa binária em tempo O(log n)).

Talvez você possa explicar com um exemplo em que casos HashSet<T> deve ser preferido em relação ao List<T>

Quando você deseja testar a contenção em O(1).

Para ser mais preciso, vamos demonstrar com exemplos,

Você não pode usar o HashSet como no exemplo a seguir. 

HashSet<string> hashSet1 = new HashSet<string>(){"1","2","3"};
for (int i = 0; i < hashSet1.Count; i++)
    Console.WriteLine(hashSet1[i]);

hashSet1[i] produziria um erro:

Não é possível aplicar indexação com [] a uma expressão do tipo 'System.Collections.Generic.HashSet'

Você pode usar a instrução foreach: 

foreach (var item in hashSet1)
    Console.WriteLine(item);

Você não pode adicionar itens duplicados ao HashSet enquanto a lista permite que você faça isso e enquanto adiciona um item ao HashSet, você pode verificar se ele contém o item ou não. 

HashSet<string> hashSet1 = new HashSet<string>(){"1","2","3"};
if (hashSet1.Add("1"))
   Console.WriteLine("'1' is successfully added to hashSet1!");
else
   Console.WriteLine("'1' could not be added to hashSet1, because it contains '1'");

HashSet tem algumas funções úteis como IntersectWith, UnionWith, IsProperSubsetOf, ExceptWith, SymmetricExceptWith etc.

IsProperSubsetOf: 

HashSet<string> hashSet1 = new HashSet<string>() { "1", "2", "3", "4" };
HashSet<string> hashSet2 = new HashSet<string>() { "2", "4", "6", "8" };
HashSet<string> hashSet3 = new HashSet<string>() { "1", "2", "3", "4", "5" };
if (hashSet1.IsProperSubsetOf(hashSet3))
    Console.WriteLine("hashSet3 contains all elements of hashSet1.");
if (!hashSet1.IsProperSubsetOf(hashSet2))
    Console.WriteLine("hashSet2 does not contains all elements of hashSet1.");

UnionWith: 

HashSet<string> hashSet1 = new HashSet<string>() { "3", "4" };
HashSet<string> hashSet2 = new HashSet<string>() { "2", "4", "6", "8" };
hashSet1.UnionWith(hashSet2); //hashSet1 -> 3, 2, 4, 6, 8

IntersectWith: 

HashSet<string> hashSet1 = new HashSet<string>() { "3", "4", "8" };
HashSet<string> hashSet2 = new HashSet<string>() { "2", "4", "6", "8" }
hashSet1.IntersectWith(hashSet2);//hashSet1 -> 4, 8

ExceptWith: 

 HashSet<string> hashSet1 = new HashSet<string>() { "1", "2", "3", "5", "6" };
 HashSet<string> hashSet2 = new HashSet<string>() { "1", "2", "3", "4" };
 hashSet1.ExceptWith(hashSet2);//hashSet1 -> 5, 6

SymmetricExceptWith: 

 HashSet<string> hashSet1 = new HashSet<string>() { "1", "2", "3", "5", "6" };
 HashSet<string> hashSet2 = new HashSet<string>() { "1", "2", "3", "4" };
 hashSet1.SymmetricExceptWith(hashSet2);//hashSet1 -> 4, 5, 6

A propósito, a ordem não é preservada em HashSets. No exemplo, adicionamos o elemento "2" por último, mas ele está na segunda ordem: 

HashSet<string> hashSet1 = new HashSet<string>() { "3", "4", "8" };
hashSet1.Add("1");    // 3, 4, 8, 1
hashSet1.Remove("4"); // 3, 8, 1
hashSet1.Add("2");    // 3, 2 ,8, 1

Use um List<T> quando desejar:

  • Armazene uma coleção de itens em uma determinada ordem.

Se você souber o índice do item que deseja (em vez do valor do próprio item), a recuperação é O(1). Se você não souber o índice, encontrar o item leva mais tempo, O(n) para uma coleção não classificada.

Use um Hashset<T> quando desejar:

  • Descubra rapidamente se um determinado objeto está contido em uma coleção.

Se você souber o nome do que deseja encontrar, Lookup é O(1) (que é a parte 'Hash'). Ele não mantém uma ordem como o List<T> faz e você não pode armazenar duplicatas (adicionar uma duplicata não tem efeito, essa é a parte 'Definir').

Um exemplo de quando usar um Hashset<T> seria se você quisesse descobrir se uma palavra jogada em um jogo de Scrabble é uma palavra válida em inglês (ou outro idioma). Melhor ainda seria se você quisesse construir um serviço da web para ser usado por todas as instâncias de uma versão online desse jogo.

Um List<T> seria uma boa estrutura de dados para criar o placar para rastrear as pontuações dos jogadores.

Lista é uma lista ordenada.É

  • acessado por um índice inteiro
  • pode conter duplicatas
  • tem uma ordem previsível

HashSet é um conjunto.Ele:

  • Pode bloquear itens duplicados (consulte Adicionar (T) )
  • Não garante a ordem dos itens dentro do conjunto
  • Tem operações que você esperaria em um conjunto, por exemplo , IntersectWith, IsProperSubsetOf, UnionWith.

Listar é mais apropriado quando você deseja acessar sua coleção como se fosse um array ao qual você pode anexar, inserir e remover itens.HashSet é uma escolha melhor se você deseja tratar sua coleção como uma "bolsa" de itens em que a ordem não é importante ou quando você deseja compará-la com outros conjuntos usando operações como IntersectWith ou UnionWith.

A lista não é necessariamente única, enquanto o hashset é, por exemplo.

Uma lista é uma coleção ordenada de objetos do Tipo T que, ao contrário de uma matriz, você pode adicionar e remover entradas.

Você usaria uma lista na qual deseja fazer referência aos membros na ordem em que os armazenou e os acessa por uma posição em vez do próprio item.

Um HashSet é como um dicionário em que o item em si é a chave, assim como o valor, a ordem não é garantida.

Você usaria um HashSet onde deseja verificar se um objeto está na coleção

Se você decidir aplicar essas estruturas de dados ao uso real no desenvolvimento orientado a dados, um HashSet é MUITO útil para testar a replicação em fontes de adaptador de dados, para limpeza e migração de dados.

Além disso, ao usar a classe DataAnnotations, pode-se implementar a lógica Key nas propriedades da classe e controlar efetivamente um índice natural (agrupado ou não) com um HashSet, onde isso seria muito difícil em uma implementação de lista.

Uma opção forte para usar uma lista é implementar genéricos para várias mídias em um modelo de visualização, como o envio de uma lista de classes para uma visualização MVC para um auxiliar DropDownList e também para o envio como uma construção JSON via WebApi.A lista permite uma lógica de coleção de classe típica e mantém a flexibilidade para uma abordagem mais "Interface" para calcular um modelo de visualização única para diferentes meios.

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top