Qual é a diferença entre HashSet <T> e List <T>?

156

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

Talvez você possa explicar com um exemplo em quais casos HashSet<T>devem ser preferidos List<T>?

pencilCake
fonte
22
Algumas leituras sobre o tema: C # / NET Fundamentals:. Escolhendo o Class Collection direito
Fredrik Mörk
Sugiro que você consulte os artigos da Wikipedia em en.wikipedia.org/wiki/Hash_table e en.wikipedia.org/wiki/Dynamic_array .
Mqp
Para desempenho relacionado, consulte hashset-vs-list-performance
nawfal

Respostas:

213

Ao contrário 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ápido

  3. Adicionar a um HashSet retorna um valor booleano - false se a adição falhar devido a já existir em Set

  4. Pode executar operações matemáticas de conjuntos em relação a um conjunto: união / interseção / 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 executar 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 é melhor escrever!

BonyT
fonte
IDK, tive problemas com o Unionmétodo. Eu tinha usado em seu UnionWithlugar.
usuário
2
+1 em "O principal motivo para usar um HashedSet seria se você estiver interessado em executar operações de configuração".
LCJ
12
Na verdade, prefiro a resposta que aponta que os HashSets são adequados nos casos em que você pode tratar sua coleção como "itens de bolsa". As operações do conjunto não são tão frequentes quanto as verificações de contenção. Em qualquer momento em que você tenha um conjunto de itens exclusivos (por exemplo, códigos) e precise verificar a contenção, um HashSet é útil.
ThunderGr
Boa resposta. Estou tentado a adicionar algumas diferenças de características de desempenho também.
Nawfal 28/05
1
Pergunta: o principal motivo é não ter certeza de não ter itens duplicados?
Andrea Scarafoni
54

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 a 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 fazer isso e enquanto estiver adicionando um item ao HashSet, é possível 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, SymmetricExceptWithetc.

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, o pedido não é preservado no HashSets. No exemplo, adicionamos o elemento "2" por último, mas 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
GorkemHalulu
fonte
51

A HashSet<T>é uma classe projetada para O(1)procurar pesquisas de contenção (ou seja, essa coleção contém um objeto específico e me responde rapidamente).

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

Talvez você possa explicar com um exemplo em quais casos HashSet<T>devem ser preferidosList<T>

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

Jason
fonte
Exceto é O (log n) se a lista estiver classificada; afinal, é mais rápido que a pesquisa em uma lista não classificada.
Andrei
20

Use a List<T>quando desejar:

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

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

Use a Hashset<T>quando desejar:

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

Se você souber o nome da coisa que deseja encontrar, a Pesquisa é O(1)(essa é a parte 'Hash'). Ele não mantém um pedido como o List<T>faz e você não pode armazenar duplicados (adicionar um duplicado não tem efeito, essa é a parte 'Definir').

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

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

Waylon Flinn
fonte
15

Lista é uma lista ordenada. Isto é

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

HashSet é um conjunto. Isto:

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

A lista é mais apropriada quando você deseja acessar sua coleção como se fosse uma matriz à qual você pudesse anexar, inserir e remover itens. O HashSet é uma opção 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 as operações como IntersectWith ou UnionWith.

dgvid
fonte
3

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

therealmitchconnors
fonte
3

Uma Lista é uma coleção ordenada de objetos do Tipo T que, diferente de uma matriz, você pode adicionar e remover entradas.

Você usaria uma lista na qual deseja referenciar os membros na ordem em que os armazenou e os está acessando por uma posição e não pelo item em si.

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

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

Bob Vale
fonte
1
Para esclarecer, no caso de alguém ler isso errado à primeira vista - Listmantém uma ordem (ou seja, quando as coisas foram adicionadas), mas não classifica automaticamente os itens. Você teria que ligar .Sortou usar a SortedList.
Drzaus 23/05
1

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

Além disso, se você usar a Classe DataAnnotations, poderá implementar a lógica Key nas propriedades da classe e controlar efetivamente um Índice Natural (clusterizado ou não) com um HashSet, onde isso seria muito difícil na implementação da Lista.

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

Nathan Teague
fonte