.net - HashSet<T> versus Dictionary<K, V> wrt tiempo de búsqueda para encontrar si un artículo existe

performance

Question

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


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

¿ .Contains quién .Contains método .Contains regresará más rápido?

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

Answer 1

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

"Recuperar un valor usando su clave es muy rápido, cerca de 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 hash del tipo especificado para TKey"

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

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

Answer 2

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

HashSet contiene 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.

Answer 3

HashSet vs List versus Dictionary performance test, tomado de here .

Agregue 1000000 objetos (sin verificar duplicados)

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

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

Answer 4

Supongo que te refieres a Dictionary<TKey, TValue> en el segundo caso. HashTable es una clase no genérica.

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

Esperaría que HashSet<T>.Contains y Dictionary<TKey, TValue>.ContainsKey (que son las operaciones comparables, suponiendo que usas tu diccionario con sensatez) básicamente hagan lo mismo: están usando el mismo algoritmo, fundamentalmente. Supongo que con las entradas en Dictionary<,> es 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 lo que estás tratando de lograr.