HashSet <T> versus Dictionary <K, V> wrt tiempo de búsqueda para encontrar si existe un elemento

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


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

¿ .ContainsQué método volverá más rápido?

Solo para aclarar, mi requisito es tener 10 millones de objetos (bueno, cadenas en realidad) que necesito verificar si existen en la estructura de datos. NUNCA iteraré.

Halivingston
fuente
1
Paso 1: Vea si ambos hacen lo mismo (en este caso, las dos colecciones son para propósitos diferentes) Paso 2: Consulte la documentación y vea si se siente bien con su complejidad asintótica. Paso 3: Si siente que necesita preocuparse más, mídase y luego haga la pregunta publicando el punto de referencia junto con él. En su caso, la pregunta se vuelve inútil en el primer paso.
nawfal

Respuestas:

153

Prueba de rendimiento HashSet vs List vs Dictionary, tomada de aquí .

Agregue 1000000 objetos (sin verificar los duplicados)

Contiene cheque por la mitad de los objetos de una colección de 10000

Elimina la mitad de los objetos de una colección de 10000

tenido
fuente
9
¡Gran análisis! Parece que .Contains for Dictionary es tan rápido que no hay ningún beneficio de usar HashSet en absoluto, en el caso del OP.
EtherDragon
2
sí, tenía la misma pregunta que el OP. Ya tengo un diccionario que estoy usando por otras razones y quería saber si me beneficia cambiar a un Hashset en lugar de usar ContainsKey. Parece que la respuesta es no, ya que ambos son muy rápidos.
FistOfFury
4
Al contrario de lo que parecen implicar los comentarios anteriores, sí, debería cambiar a HashSet porque le da lo que quiere: almacenar un conjunto de valores (en lugar de mantener algún tipo de mapeo). Esta respuesta indica que no habrá un impacto negativo en el rendimiento en comparación con el Diccionario.
Francois Beaussier
Esta respuesta NO le dice cómo se compara el rendimiento de HashSet y Dictionary ... todo lo que le dice es que ambos son más rápidos que una lista ... bueno ... ¡sí! ¡Obviamente! HashSet podría ser 3 veces más rápido y no lo sabría porque la prueba relevante ha colapsado a "son instantáneos ... en comparación con una lista ".
Brondahl
71

¿Supongo que te refieres Dictionary<TKey, TValue>al segundo caso? HashTablees una clase no genérica.

Debe elegir la colección adecuada para el trabajo según sus requisitos reales. ¿Realmente desea asignar cada clave a un valor? Si es así, utilice Dictionary<,>. Si solo te importa como conjunto, úsalo HashSet<>.

Yo esperaría que HashSet<T>.Containsy Dictionary<TKey, TValue>.ContainsKey(que son las operaciones comparables, asumiendo que está usando su diccionario con sensatez) para realizar básicamente lo mismo: están usando el mismo algoritmo, fundamentalmente. Supongo que con las entradas Dictionary<,>más grandes terminas con una mayor probabilidad de volar el caché con Dictionary<,>que con HashSet<>, pero esperaría que eso sea insignificante en comparación con el dolor de elegir el tipo de datos incorrecto simplemente en términos de lo que estás tratando de lograr.

Jon Skeet
fuente
Sí, me refiero al Diccionario <TKey, TValue>. Solo me preocupa buscar la existencia de un elemento en una estructura de datos, eso es todo .
halivingston
3
@halivingston En ese caso, use HashSet. Hace que sea obvio que eso es todo lo que necesita.
Jon Skeet
2
OK gracias. De hecho, tengo un HashSet <TKey> en este momento, y una copia duplicada del Dictionary <Tkey, TValue> también en la memoria. Primero. Contiene en el HashSet, luego recupero el valor en Dictionary <TKey, TValue>. Tengo una memoria infinita en este momento, pero temo que pronto mi memoria se verá limitada y nuestro equipo me pedirá que elimine este material duplicado en la memoria, momento en el que me veré obligado a usar Dictionary <TKey, TValue>.
halivingston
4
¿Sabes que Dictionary también tiene una función ContainsKey, verdad? ¿Por qué está duplicando datos?
Blindy
8
Si ya tiene los datos en el diccionario, entonces su primer comentario es claramente incorrecto; también debe asociar claves con valores. Quizás no para este fragmento de código en particular, pero eso es irrelevante. Si ya tiene un Dictionarypor otras razones, debería usarlo.
Jon Skeet
7

De la documentación de MSDN para Dictionary <TKey, TValue>

"Recuperar un valor usando su clave es muy rápido, cercano a O (1) , porque la clase Dictionary se implementa como una tabla hash " .

Con una nota:

"La velocidad de recuperación depende de la calidad del algoritmo de hash del tipo especificado para TKey"

Sé que su pregunta / publicación es antigua, pero mientras buscaba una respuesta a una pregunta similar me encontré con esto.

Espero que esto ayude. Desplácese hacia abajo hasta la sección Comentarios para obtener más detalles. https://msdn.microsoft.com/en-us/library/xfhwa508(v=vs.110).aspx

ripvlan
fuente
4

Estas son diferentes estructuras de datos. Además, no existe una versión genérica deHashTable .

HashSetcontiene valores de tipo T que HashTable(o Dictionary) contiene pares clave-valor. Por lo tanto, debe elegir la recopilación de los datos que necesita almacenar.

Andrew Bezzub
fuente
0

¡La respuesta aceptada a esta pregunta NO responde válidamente a la pregunta! Da la respuesta correcta, pero esa respuesta no se muestra en la evidencia que proporcionaron.

Lo que muestra esa respuesta es que las búsquedas clave en un Dictionaryo HashSetson mucho más rápidas que buscar en un List. Lo cual es cierto, pero no interesante, ni sorprendente, ni prueba de que tengan el mismo velocidad.

Ejecuté el siguiente código para comparar los tiempos de búsqueda y mi conclusión es que, de hecho, SON a la misma velocidad. (O al menos, si hay alguna diferencia, entonces la diferencia está dentro de la desviación estándar de esa velocidad)

Específicamente, 100.000.000 de búsquedas tardaron entre 10 y 11,5 segundos para ambos, para mí, en esta prueba.

Código de prueba:

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
fuente