HashSet <T> versus Dicionário <K, V> antes do tempo de pesquisa para descobrir se um item existe

103
HashSet<T> t = new HashSet<T>();
// add 10 million items


Dictionary<K, V> t = new Dictionary<K, V>();
// add 10 million items.

.ContainsMétodo de quem retornará mais rápido?

Só para esclarecer, meu requisito é que tenho 10 milhões de objetos (bem, strings, na verdade) que preciso verificar se eles existem na estrutura de dados. Eu NUNCA vou repetir.

Halivingston
fonte
1
Etapa 1: Veja se ambos fazem a mesma coisa (neste caso, as duas coleções são para finalidades diferentes) Etapa 2: Consulte a documentação e veja se você se sente bem com sua complexidade assintótica. Passo 3: Se você sentir que precisa se preocupar mais, avalie a si mesmo e faça a pergunta postando o benchmark junto com ele. No seu caso, a pergunta torna-se inútil na primeira etapa.
nawfal

Respostas:

153

Teste de desempenho HashSet vs Lista vs Dicionário, obtido a partir daqui .

Adicione 1.000.000 de objetos (sem verificar duplicatas)

Contém cheque para metade dos objetos de uma coleção de 10.000

Remova metade dos objetos de uma coleção de 10.000

teve
fonte
9
Ótima análise! Parece que o .Contains for Dictionary é tão rápido que não há benefício algum em usar o HashSet, no caso do OP.
EtherDragon
2
sim, eu tinha a mesma pergunta que o OP. Já tenho um dicionário que estou usando por outros motivos e gostaria de saber se me beneficio de mudar para um Hashset em vez de usar ContainsKey. Parece que a resposta é não, pois os dois são muito rápidos.
FistOfFury
4
Ao contrário do que os comentários anteriores parecem sugerir, sim, você deve mudar para o HashSet porque ele oferece o que você deseja: armazenar um conjunto de valores (em vez de manter algum tipo de mapeamento). Essa resposta indica que não haverá impacto negativo no desempenho em comparação com o Dicionário.
François Beaussier,
Esta resposta NÃO diz como o desempenho do HashSet e do Dicionário se comparam ... tudo o que ela diz é que ambos são mais rápidos do que uma Lista ... bem ... sim! Obviamente! O HashSet poderia ser 3 vezes mais rápido e você não saberia porque o teste relevante reduziu ambos para "eles são instantâneos ... em comparação com uma lista ".
Brondahl
71

Suponho que você quer dizer Dictionary<TKey, TValue>no segundo caso? HashTableé uma classe não genérica.

Você deve escolher a coleção certa para o trabalho com base em suas necessidades reais. Você realmente deseja mapear cada chave para um valor? Se sim, use Dictionary<,>. Se você só se preocupa com ele como um conjunto, use HashSet<>.

Eu esperaria HashSet<T>.Containse Dictionary<TKey, TValue>.ContainsKey(que são as operações comparáveis, supondo que você está usando seu dicionário de maneira sensata), basicamente executar o mesmo - eles estão usando o mesmo algoritmo, fundamentalmente. Eu acho que com as entradas Dictionary<,>sendo maiores, você acaba com uma probabilidade maior de expandir o cache do Dictionary<,>que com HashSet<>, mas eu esperava que isso fosse insignificante em comparação com a dor de escolher o tipo de dados errado simplesmente em termos do que você está tentando alcançar.

Jon Skeet
fonte
Sim, eu quis dizer Dicionário <TKey, TValue>. Eu só estou preocupado com a procura para a existência do item em uma estrutura de dados, isto é tudo .
Halivingston
3
@halivingston Nesse caso, use HashSet. Torna óbvio que isso é tudo de que você precisa.
Jon Skeet
2
Ok, obrigado. Na verdade, tenho um HashSet <TKey> agora e uma cópia duplicada do Dicionário <Tkey, TValue> também na memória. Eu primeiro .Contém no HashSet e, em seguida, recupero o valor no Dicionário <TKey, TValue>. Eu tenho memória infinita agora, mas logo temo que minha memória ficará restrita e nossa equipe me pedirá para remover esse material duplicado na memória, ponto em que serei forçado a usar o Dicionário <TKey, TValue>.
Halivingston
4
Você sabe que o Dicionário também tem uma função ContainsKey, certo? Por que você está duplicando dados?
Blindy
8
Se você já tem os dados no dicionário, seu primeiro comentário está claramente incorreto - você também precisa associar as chaves aos valores. Talvez não para este trecho de código em particular, mas isso é irrelevante. Se você já tem um Dictionarypor outros motivos, deve usá-lo.
Jon Skeet
7

Da documentação do MSDN para Dictionary <TKey, TValue>

"Recuperar um valor usando sua chave é muito rápido, próximo a O (1) , porque a classe Dictionary é implementada como uma tabela hash. "

Com uma nota:

"A velocidade de recuperação depende da qualidade do algoritmo de hash do tipo especificado para TKey"

Sei que sua pergunta / postagem é antiga - mas enquanto procurava uma resposta para uma pergunta semelhante, me deparei com isso.

Espero que isto ajude. Role para baixo até a seção Comentários para obter mais detalhes. https://msdn.microsoft.com/en-us/library/xfhwa508(v=vs.110).aspx

ripvlan
fonte
4

Essas são estruturas de dados diferentes. Também não existe uma versão genérica do HashTable.

HashSetcontém valores do tipo T que HashTable(ou Dictionary) contém pares de valores-chave. Portanto, você deve escolher a coleta de dados que deseja armazenar.

Andrew Bezzub
fonte
0

A resposta aceita para esta pergunta NÃO responde validamente à pergunta! Acontece que dá a resposta correta, mas essa resposta não é mostrada pelas evidências que eles forneceram.

O que essa resposta mostra é que as pesquisas de chave em a Dictionaryou HashSetsão muito mais rápidas do que pesquisar em a List. O que é verdade, mas não é interessante, nem surpreendente, nem prova de que eles têm a mesma velocidade.

Executei o código abaixo para comparar os tempos de pesquisa e minha conclusão é que eles SÃO, de fato, a mesma velocidade. (Ou pelo menos, se houver alguma diferença, então a diferença está bem dentro do Desvio Padrão dessa velocidade)

Especificamente, 100 milhões de pesquisas estavam levando entre 10 e 11,5 segundos para ambos, para mim, neste teste.

Código de teste:

private const int TestReps = 100_000_000;
[Test]
public void CompareHashSetContainsVersusDictionaryContainsKey()
{
    for (int j = 0; j < 10; j++)
    {
        var rand = new Random();
        var dict = new Dictionary<int, int>();
        var hash = new HashSet<int>();

        for (int i = 0; i < TestReps; i++)
        {
            var key = rand.Next();
            var value = rand.Next();
            hash.Add(key);
            dict.TryAdd(key, value);
        }

        var testPoints = Enumerable.Repeat(1, TestReps).Select(_ => rand.Next()).ToArray();
        var timer = new Stopwatch();
        var total = 0;
        
        timer.Restart();
            for (int i = 0; i < TestReps; i++)
            {
                var newKey = testPoints[i];
                if (hash.Contains(newKey))
                {
                    total++;
                }
            }
        Console.WriteLine(timer.Elapsed);
        
        var target = total;
        Assert.That(total == target);
        

        timer.Restart();
            for (int i = 0; i < TestReps; i++)
            {
                var newKey = testPoints[i];
                if (dict.ContainsKey(newKey))
                {
                    total++;
                }
            }
        Console.WriteLine(timer.Elapsed);

        Assert.That(total == target * 2);
        Console.WriteLine("Set");
    }
}
Brondahl
fonte