Quando devo usar o tipo HashSet <T>?

Estou explorando o HashSet<T>tipo, mas não entendo onde ele está nas coleções.

Pode-se usá-lo para substituir um List<T>? Imagino que o desempenho de HashSet<T>a seja melhor, mas não pude ver o acesso individual a seus elementos.

É apenas para enumeração?

O importante HashSet<T>é o nome: é um conjunto . As únicas coisas que você pode fazer com um único conjunto é estabelecer quais são seus membros e verificar se um item é um membro.

Perguntar se você pode recuperar um único elemento (por exemplo set[45]) está entendendo mal o conceito do conjunto. Não existe o 45º elemento de um conjunto. Os itens de um conjunto não têm pedidos. Os conjuntos {1, 2, 3} e {2, 3, 1} são idênticos em todos os aspectos porque têm a mesma associação, e a associação é tudo o que importa.

É um pouco perigoso iterar sobre um, HashSet<T>porque isso impõe uma ordem aos itens do conjunto. Essa ordem não é realmente uma propriedade do conjunto. Você não deve confiar nisso. Se a ordem dos itens em uma coleção é importante para você, essa coleção não é um conjunto.

Os conjuntos são realmente limitados e com membros únicos. Por outro lado, eles são realmente rápidos.

Aqui está um exemplo real de onde eu uso um HashSet<string>:

Parte do meu marcador de sintaxe para arquivos UnrealScript é um novo recurso que destaca os comentários no estilo Doxygen . Eu preciso saber se um comando @ou \é válido para determinar se ele será exibido em cinza (válido) ou vermelho (inválido). Eu tenho um HashSet<string>de todos os comandos válidos; portanto, sempre que clico em um @xxxtoken no lexer, uso validCommands.Contains(tokenText)como verificação de validade O (1). Realmente não me importo com nada, exceto a existência do comando no conjunto de comandos válidos. Vamos olhar para as alternativas que eu enfrentei:

• Dictionary<string, ?>: Que tipo eu uso para o valor? O valor não tem sentido, já que vou usar ContainsKey. Nota: Antes do .NET 3.0, essa era a única opção para pesquisas O (1) - HashSet<T>foi adicionada para 3.0 e estendida para implementação ISet<T>para 4.0.
• List<string>: Se eu mantiver a lista classificada, posso usar BinarySearch, que é O (log n) (não vi esse fato mencionado acima). No entanto, como minha lista de comandos válidos é uma lista fixa que nunca muda, isso nunca será mais apropriado do que simplesmente ...
• string[]: Novamente, Array.BinarySearchfornece desempenho O (log n). Se a lista for curta, essa pode ser a opção com melhor desempenho. Sempre tem menos sobrecarga espaço do que HashSet, Dictionaryou List. Mesmo com BinarySearch, não é mais rápido para conjuntos grandes, mas para conjuntos pequenos vale a pena experimentar. A mina tem várias centenas de itens, então eu passei isso.

A HashSet<T>implementa a ICollection<T>interface:

public interface ICollection<T> : IEnumerable<T>, IEnumerable
{
    // Methods
    void Add(T item);
    void Clear();
    bool Contains(T item);
    void CopyTo(T[] array, int arrayIndex);
    bool Remove(T item);

    // Properties
   int Count { get; }
   bool IsReadOnly { get; }
}

Um List<T>implementa IList<T>, que estende oICollection<T>

public interface IList<T> : ICollection<T>
{
    // Methods
    int IndexOf(T item);
    void Insert(int index, T item);
    void RemoveAt(int index);

    // Properties
    T this[int index] { get; set; }
}

Um HashSet definiu semântica, implementada através de uma hashtable internamente:

Um conjunto é uma coleção que não contém elementos duplicados e cujos elementos não estão em uma ordem específica.

O que o HashSet ganha se perder o comportamento do índice / posição / lista?

Adicionar e recuperar itens do HashSet é sempre do próprio objeto, não por meio de um indexador e próximo a uma operação O (1) (Lista é O (1) add, O (1) recupera por índice, O (n) encontra /remover).

O comportamento de um HashSet pode ser comparado ao uso de um Dictionary<TKey,TValue>adicionando / removendo apenas chaves como valores e ignorando os próprios valores do dicionário. Você esperaria que as chaves de um dicionário não tivessem valores duplicados, e esse é o ponto da parte "Definir".

O desempenho seria um mau motivo para escolher o HashSet em vez de Lista. Em vez disso, o que melhor captura sua intenção? Se a ordem for importante, Set (ou HashSet) está fora. Se duplicatas são permitidas, da mesma forma. Mas há muitas circunstâncias em que não nos importamos com a ordem e preferimos não ter duplicatas - e é aí que você deseja um Conjunto.

HashSet é um conjunto implementado por hash. Um conjunto é uma coleção de valores que não contêm elementos duplicados. Os valores em um conjunto também geralmente não são ordenados. Portanto, não, um conjunto não pode ser usado para substituir uma lista (a menos que você deva usar um conjunto em primeiro lugar).

Se você está se perguntando para que serve um conjunto: em qualquer lugar que você queira se livrar das duplicatas, obviamente. Como um exemplo um pouco artificial, digamos que você tenha uma lista de 10.000 revisões de um projeto de software e queira descobrir quantas pessoas contribuíram para esse projeto. Você pode usar Set<string>ae iterar sobre a lista de revisões e adicionar o autor de cada revisão ao conjunto. Depois de concluir a iteração, o tamanho do conjunto é a resposta que você estava procurando.

HashSet seria usado para remover elementos duplicados em uma coleção IEnumerable. Por exemplo,

List<string> duplicatedEnumrableStrings = new List<string> {"abc", "ghjr", "abc", "abc", "yre", "obm", "ghir", "qwrt", "abc", "vyeu"};
HashSet<string> uniqueStrings = new HashSet(duplicatedEnumrableStrings);

depois que esses códigos são executados, uniqueStrings mantém {"abc", "ghjr", "yre", "obm", "qwrt", "vyeu"};

Provavelmente, o uso mais comum para hashsets é verificar se eles contêm um determinado elemento, que é próximo a uma operação O (1) para eles (assumindo uma função de hash suficientemente forte), em oposição a listas cuja verificação para inclusão é O ( n) (e conjuntos classificados para os quais é O (log n)). Portanto, se você fizer muitas verificações, se um item está contido em alguma lista, os hahssets podem ser uma melhoria de desempenho. Se você apenas iterar sobre eles, não haverá muita diferença (a iteração em todo o conjunto é O (n), o mesmo que nas listas e hashsets que possuem um pouco mais de sobrecarga ao adicionar itens.

E não, você não pode indexar um conjunto, o que não faria sentido, porque os conjuntos não são ordenados. Se você adicionar alguns itens, o conjunto não lembrará qual foi o primeiro, o segundo, etc.

HashSet<T>é uma estrutura de dados na estrutura .NET capaz de representar um conjunto matemático como um objeto. Nesse caso, ele usa códigos de hash (o GetHashCoderesultado de cada item) para comparar a igualdade dos elementos do conjunto.

Um conjunto difere de uma lista, pois permite apenas uma ocorrência do mesmo elemento contido nele. HashSet<T>retornará apenas falsese você tentar adicionar um segundo elemento idêntico. De fato, a pesquisa de elementos é muito rápida ( O(1)tempo), pois a estrutura de dados interna é simplesmente uma hashtable.

Se você está se perguntando qual usar, observe que o uso de um List<T>where HashSet<T>não é o maior erro, embora possa potencialmente permitir problemas nos quais você tem itens duplicados indesejáveis ​​em sua coleção. Além disso, a pesquisa (recuperação de itens) é muito mais eficiente - idealmente O(1)(para um balde perfeito) em vez de O(n)tempo - o que é bastante importante em muitos cenários.

List<T>é usado para armazenar conjuntos de informações solicitados. Se você souber a ordem relativa dos elementos da lista, poderá acessá-los em tempo constante. No entanto, para determinar onde um elemento está na lista ou para verificar se ele existe na lista, o tempo de pesquisa é linear. Por outro lado, HashedSet<T>não garante a ordem dos dados armazenados e, consequentemente, fornece tempo de acesso constante para seus elementos.

Como o nome indica, HashedSet<T>é uma estrutura de dados que implementa a semântica de conjuntos . A estrutura de dados é otimizada para implementar operações de conjunto (ou seja, União, Diferença, Interseção), o que não pode ser feito com a mesma eficiência da implementação tradicional da Lista.

Portanto, escolher qual tipo de dados usar realmente depende do que você está tentando fazer com seu aplicativo. Se você não se importa com o modo como seus elementos são ordenados em uma coleção e deseja apenas exumar ou verificar a existência, use HashSet<T>. Caso contrário, considere usar List<T>ou outra estrutura de dados adequada.

Em resumo - sempre que você estiver tentado a usar um Dicionário (ou um Dicionário onde S é uma propriedade de T), considere um HashSet (ou HashSet + implementando IEquatable em T que equivale a S)

No cenário pretendido básico, HashSet<T>deve ser usado quando você deseja operações de conjunto mais específicas em duas coleções do que o LINQ fornece. Métodos LINQ como Distinct, Union, Intersecte Exceptsão suficientes na maioria das situações, mas às vezes você pode precisar de mais operações de grão fino, e HashSet<T>fornece:

• UnionWith
• IntersectWith
• ExceptWith
• SymmetricExceptWith
• Overlaps
• IsSubsetOf
• IsProperSubsetOf
• IsSupersetOf
• IsProperSubsetOf
• SetEquals

Outra diferença entre os HashSet<T>métodos LINQ e "sobreposição" é que o LINQ sempre retorna um novo IEnumerable<T>e os HashSet<T>métodos modificam a coleção de origem.