Definir: O que é um HashSet?

420

HashSet A estrutura de dados do C # HashSet foi introduzida no .NET Framework 3.5. Uma lista completa dos membros implementados pode ser encontrada na página HashSet MSDN .

  1. Onde é usado?
  2. Por que você gostaria de usá-lo?
c# hashset 001
fonte
4
en.wikipedia.org/wiki/Set_(computer_science)
Claus Jørgensen
3
possível duplicata de Quando devo usar o tipo HashSet <T>?
Nawfal 26/05
Ele usa uma hashtable internamente. se você tiver uma boa implementação de hashtable (por exemplo, Dictionary <T>), poderá implementar o HashSet facilmente.
Raz Megrelidze

Respostas:

614

    1. A HashSetcontém um conjunto de objetos, mas de uma maneira que permite determinar com facilidade e rapidez se um objeto já está no conjunto ou não. Isso é feito gerenciando internamente uma matriz e armazenando o objeto usando um índice calculado a partir do código hash do objeto. Dê uma olhada aqui

    2. HashSeté uma coleção não ordenada que contém elementos exclusivos. Possui as operações de coleta padrão Adicionar, Remover, Contém, mas, como usa uma implementação baseada em hash, essas operações são O (1). (Ao contrário de Lista, por exemplo, que é O (n) para Contém e Remover.) HashSetTambém fornece operações de conjunto padrão, como união , interseção e diferença simétrica . Dê uma olhada aqui

  2. Existem diferentes implementações de conjuntos. Alguns tornam as operações de inserção e pesquisa super rápidas, usando elementos de hash. No entanto, isso significa que a ordem na qual os elementos foram adicionados é perdida. Outras implementações preservam a ordem adicionada ao custo de tempos de execução mais lentos.

A HashSetclasse em C # segue a primeira abordagem, não preservando a ordem dos elementos. É muito mais rápido que o normal List. Alguns benchmarks básicos mostraram que o HashSet é decentemente mais rápido ao lidar com tipos primários (int, double, bool, etc.). É muito mais rápido ao trabalhar com objetos de classe. Portanto, esse ponto é que o HashSet é rápido.

O único problema HashSeté que não há acesso por índices. Para acessar elementos, você pode usar um enumerador ou a função interna para converter o arquivo HashSetem Liste iterar por meio dele. Dê uma olhada aqui

kamaci
fonte
13
Duas coisas, hashset e similares são do .NET, não do C #. O HashSet também não preserva a ordem. Experimente adicionar e remover itens de um conjunto de hash, você vai saber se você iterar mais tarde ..
Nawfal
13

A HashSetpossui uma estrutura interna (hash), na qual os itens podem ser pesquisados ​​e identificados rapidamente. A desvantagem é que a iteração através de um HashSet(ou a obtenção de um item pelo índice) é bastante lenta.

Então, por que alguém gostaria de saber se uma entrada já existe em um conjunto?

Uma situação em que a HashSeté útil é obter valores distintos de uma lista em que podem existir duplicatas. Depois que um item é adicionado HashSet, é rápido determinar se o item existe ( Containsoperador).

Outras vantagens do HashSetsão as operações Set: IntersectWith, IsSubsetOf, IsSupersetOf, Overlaps, SymmetricExceptWith, UnionWith.

Se você estiver familiarizado com a linguagem de restrição de objetos , identificará essas operações definidas. Você também verá que está um passo mais perto de uma implementação de UML executável.

k rey
fonte
20
Re: desvantagem. Não, a iteração através de um HashSet é perfeitamente rápida. Em segundo lugar, não é possível obter um item por índice. De fato, os elementos são armazenados sem ordem.
Nigel Toque
@Nigel Touch. A iteração é rápida se você não se importa com o índice (ordem em que foram adicionados). No entanto, se você estiver preocupado com o índice, o índice deverá ser armazenado com cada chave de hash e, portanto, poderá ser bastante lento, pois a lista deverá ser pesquisada exaustivamente para recuperar o item correto. Esse comportamento é muito diferente de uma lista na qual os itens são indexados pela ordem em que são adicionados.
Kdy
Faz sentido por que seria rápido, porque não há dois hash iguais. Permitir que a consulta tire proveito de uma abordagem de "curto-circuito", descartando rapidamente determinados critérios.
Chef_Code 17/02
8

Simplesmente dito e sem revelar os segredos da cozinha: um conjunto em geral é uma coleção que não contém elementos duplicados e cujos elementos não estão em uma ordem específica. Portanto, A HashSet<T>é semelhante a um genérico List<T>, mas é otimizado para pesquisas rápidas (via hashtables, como o nome indica) ao custo da perda de ordem.

Empilhados
fonte
1
Mas um HashSet <T> pode armazenar dois objetos que possuem os mesmos dados, como duas classes de produtos, cada uma com as mesmas propriedades e o mesmo conteúdo?
Johan Herstad 30/08/19
Eu acho que nós nunca saberemos
Denny
@JohanHerstad Supondo que o EqualityComparer para sua classe se preocupe com essas propriedades ou se você constrói o HashSet com um IEqualityComparer que se preocupa com essas propriedades, não vejo por que não. A documentação do HashSet deixa claro que ele depende de um ou de outro para determinar a exclusividade.
Bacon Bits
2

Do ponto de vista do aplicativo, se é necessário apenas evitar duplicatas, HashSeté o que você está procurando, já que as complexidades de Pesquisa, Inserir e Remover são O (1) - constantes . Isso significa que não importa quantos elementos HashSetpossuam, levará a mesma quantidade de tempo para verificar se existe ou não esse elemento. Além disso, como você está inserindo elementos em O (1), também é perfeito para esse tipo de coisa.

Matas Vaitkevicius
fonte