HashSet <T> frente Diccionario <K, V> w.r.t tiempo de búsqueda para encontrar si existe un elemento

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


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

quién .Contains devolverá el método más rápido?HashSet <T> frente Diccionario <K, V> w.r.t tiempo de búsqueda para encontrar si existe un elemento

Solo para aclarar, mi requisito es que tengo 10 millones de objetos (bueno, realmente cadenas) que necesito verificar si existen en la estructura de datos. NUNCA voy a iterar.

Fuente

2010-04-28 halivingston

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

122

HashSet vs Lista vs prueba de rendimiento del diccionario, tomada de here.

Add 1000000 objetos (sin duplicados de cheques)

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

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

Fuente

2012-04-27 09:43:07 had

¡Gran análisis!Parece que .Contains for Dictionary es tan rápido que no ofrece ningún beneficio el uso de HashSet en absoluto, en el caso del OP. – EtherDragon

sí, tuve la misma pregunta que el OP. Ya tengo un diccionario que estoy usando por otros motivos, y quería saber si me beneficiaría cambiar a un Hashset en lugar de usar ContainsKey. Parece que la respuesta es no, ya que ambos son muy rápidos. – FistOfFury

Al contrario de lo que parecen implicar los comentarios anteriores, sí, debe cambiar a HashSet porque le proporciona lo que desea: almacenar un conjunto de valores (en lugar de mantener algún tipo de asignación). Esta respuesta indica que no habrá un impacto negativo en el rendimiento en comparación con el diccionario. –

Supongo que quiere decir Dictionary<TKey, TValue> en el segundo caso? HashTable es una clase no genérica.

Debe elegir la colección adecuada para el trabajo en función de sus necesidades reales. ¿De verdad quiere para asignar cada clave a un valor? Si es así, use Dictionary<,>. Si solo se preocupan por ello como un conjunto, use HashSet<>.

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

Fuente

2010-04-28 10:15:02

Sí, quise decir Dictionary . Solo me preocupa buscar la existencia del elemento en una estructura de datos, es decir * todo *. – halivingston

@halivingston En ese caso, use HashSet. Hace obvio que ese * es * todo lo que necesitas. –

Ok, gracias. Actualmente tengo un HashSet en este momento, y una copia duplicada de Dictionary también en la memoria. Primero .Contiene HashSet, luego recupero el valor en Dictionary . Tengo memoria infinita en este momento, pero pronto me temo que mi memoria se verá limitada y nuestro equipo me pedirá que elimine este duplicado en la memoria, y en ese momento me veré obligado a usar Dictionary . – halivingston

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

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

Fuente

2010-04-28 10:16:41

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

"Recuperación de un valor utilizando su clave es muy rápido, cerca de O (1), debido a que el diccionario la clase 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/post es viejo, pero mientras buscaba una respuesta a una pregunta similar me encontré con esto.

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

Fuente

2017-01-24 19:37:12 ripvlan

HashSet <T> frente Diccionario <K, V> w.r.t tiempo de búsqueda para encontrar si existe un elemento

Respuesta

Cuestiones relacionadas