.NET HashTable Vs Dictionary - ¿Puede el diccionario ser tan rápido?

276

Estoy tratando de averiguar cuándo y por qué usar un Diccionario o una HashTable. He hecho una pequeña búsqueda aquí y he encontrado personas que hablan sobre las ventajas genéricas del Diccionario con las que estoy totalmente de acuerdo, lo que lleva la ventaja del boxeo y el unboxing para un ligero aumento de rendimiento.

Pero también he leído que el Diccionario no siempre devolverá los objetos en el orden en que se insertan, cosa que está ordenada. Donde como una HashTable lo hará. Según tengo entendido, esto lleva a que HashTable sea mucho más rápido para algunas situaciones.

Mi pregunta es realmente, ¿cuáles podrían ser esas situaciones? ¿Estoy equivocado en mis supuestos anteriores? ¿Qué situaciones podría usar para elegir una por encima de la otra (sí, la última es un poco ambigua)?

Jon
fuente
55
Quiero votar en contra de esto, pero tu karma es 7.777 y no quiero ser el tipo que te arruina eso.
CaptainMarvel

Respuestas:

298

System.Collections.Generic.Dictionary<TKey, TValue>y las System.Collections.Hashtableclases mantienen internamente una estructura de datos de tabla hash. Ninguno de ellos garantiza preservar el orden de los artículos.

Dejando a un lado los problemas de boxeo / unboxing, la mayoría de las veces, deberían tener un rendimiento muy similar.

La principal diferencia estructural entre ellos es que se Dictionarybasa en el encadenamiento (mantener una lista de elementos para cada grupo de tablas hash) para resolver colisiones, mientras que Hashtableutiliza el cambio de color para la resolución de colisiones (cuando ocurre una colisión, prueba con otra función hash para asignar la clave a un cubo) .

Hay pocos beneficios al usar la Hashtableclase si está apuntando a .NET Framework 2.0+. Efectivamente se vuelve obsoleto por Dictionary<TKey, TValue>.

Mehrdad Afshari
fuente
21
@ Jon- El encadenamiento y la repetición se discuten en profundidad aquí- msdn.microsoft.com/en-us/library/ms379571(VS.80).aspx
RichardOD
Gracias a los dos. Acabo de encontrar esa página cuando Richard la publicó ... ¡Iba a preguntar sobre Chaining pero el sitio de MSDN es realmente útil!
Jon
66
@Mehrdad: lo que no me queda claro acerca de cómo se resuelven las colisiones es esto: si varias claves pueden dar como resultado el mismo hash, entonces, ¿cómo se asegura de obtener el valor correcto en las búsquedas, es decir, cómo sabe la función a qué elemento ¿regreso? En msdn.microsoft.com/en-us/library/ms379571%28VS.80%29.aspx dice: "En lugar de reprobar en caso de colisión, como se hace con la clase Hashtable, el diccionario simplemente encadena cualquier colisión en la lista del cubo ". ¿Significa esto que cuando se usa Diccionario, las colisiones no son algo de lo que el desarrollador tenga que preocuparse?
Howiecamp
66
@Howiecamp: Esto no es muy diferente de Hashtable. Las tablas hash almacenan 3 piezas de información en una entrada: hash de clave, clave en sí misma y el valor. Para los elementos con el mismo hash, tendrá que recorrer la lista para encontrar el elemento con la misma clave y devolver su valor. Esto es bastante cierto para Hashtabletambién. Como desarrollador que usa Dictionarynormalmente, no necesita preocuparse por eso.
Mehrdad Afshari
@Mehrdad Para ser claros, ¿tanto los objetos Hashtable como Dictionary almacenan la clave en sí, y ambos también ocultan colisiones del desarrollador?
Howiecamp
111

Supongo que no significa nada para ti ahora. Pero solo como referencia para las personas que pasan

Prueba de rendimiento - SortedList vs. SortedDictionary vs. Dictionary vs. Hashtable

Asignación de memoria:

Prueba de rendimiento de uso de memoria

Tiempo utilizado para insertar:

Tiempo utilizado para insertar

Tiempo para buscar un artículo:

Hora de buscar un artículo

Abdul Munim
fuente
Muy interesante que la lista ordenada tenga una búsqueda MÁS RÁPIDA que la tabla hash. Pensé que la tabla hash es O (1) frente a la lista ordenada O (logn). Aparentemente, la tabla hash apesta. Nunca lo usaré.
John Henckel
@ JohnHenckel no, la lista ordenada tiene una búsqueda más lenta. Mayor coeficiente de rendimiento significa mejor rendimiento y mejor uso de memoria. Por lo tanto, la lista ordenada tiene el mejor uso de memoria de acuerdo con los gráficos, pero apesta en otras áreas, como la inserción y la búsqueda.
C0DEF52
31

Diferencias entre Hashtable y Dictionary

Diccionario:

  • El diccionario devuelve un error si intentamos encontrar una clave que no existe.
  • Diccionario más rápido que un Hashtable porque no hay boxeo ni unboxing.
  • El diccionario es un tipo genérico, lo que significa que podemos usarlo con cualquier tipo de datos.

Tabla de picadillo:

  • Hashtable devuelve nulo si intentamos encontrar una clave que no existe.
  • Hashtable más lento que el diccionario porque requiere boxeo y unboxing.
  • Hashtable no es un tipo genérico,
usuario2771704
fuente
24

Otra diferencia importante es que el tipo Hashtable admite múltiples lectores sin bloqueo y un solo escritor al mismo tiempo, mientras que Dictionary no.

Steven
fuente
8
El Diccionario concurrente admitirá (.Net 4.0)
Tamilmaran
1
No estoy seguro si entiendo esta respuesta. Mirando aquí msdn.microsoft.com/en-us/library/… dice "Para admitir múltiples escritores, todas las operaciones en Hashtable deben realizarse a través del contenedor devuelto por el método Sincronizado, siempre que no haya hilos que lean el objeto Hashtable. " Eso parece hacer que la función de "lectores múltiples sin bloqueo" sea bastante inútil, por lo que volvemos a tener que bloquear todo el acceso a Hashtable, al igual que con Dictionary.
RenniePet
16

Artículo de MSDN: "La Dictionary<TKey, TValue>clase tiene la misma funcionalidad que la Hashtableclase. A Dictionary<TKey, TValue> de un tipo específico (que no sea Object) tiene un mejor rendimiento que un Hashtabletipo de valor porque los elementos de Hashtableson de tipo Objecty, por lo tanto, el boxeo y el desempaquetado ocurren típicamente si se almacena o recuperando un tipo de valor ".

Enlace: http://msdn.microsoft.com/en-us/library/4yh14awz(v=vs.90).aspx

Juan Camilo Caro J.
fuente
11

Ambos son efectivamente la misma clase (puede ver el desmontaje). HashTable se creó primero antes de que .Net tuviera genéricos. Diccionario, sin embargo, es una clase genérica y le brinda fuertes beneficios de escritura. Nunca usaría HashTable ya que Dictionary no te cuesta nada usar.

Adam Luter
fuente
8

Otra diferencia importante es que Hashtablees seguro para subprocesos. Hashtableha incorporado seguridad de subprocesos de lector múltiple / escritor único (MR / SW), lo que significa que Hashtablepermite UN escritor junto con múltiples lectores sin bloqueo. En el caso de que Dictionaryno haya seguridad de hilo, si necesita seguridad de hilo debe implementar su propia sincronización.

Para elaborar más a fondo:

Hashtable, proporciona cierta seguridad de subprocesos a través de la propiedad Sincronizada, que devuelve un contenedor seguro para subprocesos alrededor de la colección. El contenedor funciona bloqueando toda la colección en cada operación de agregar o quitar. Por lo tanto, cada subproceso que intente acceder a la colección debe esperar su turno para tomar el único bloqueo. Esto no es escalable y puede causar una degradación significativa del rendimiento para grandes colecciones. Además, el diseño no está completamente protegido de las condiciones de carrera.

Las clases de colección .NET Framework 2.0 como List<T>, Dictionary<TKey, TValue>, etc no proporcionan ninguna sincronización de hilos; el código de usuario debe proporcionar toda la sincronización cuando se agregan o eliminan elementos en varios subprocesos al mismo tiempo. Lectura adicional aquí.

Referencia nula
fuente
3

Los diccionarios tienen la ventaja de ser de tipo genérico, lo que lo hace seguro y un poco más rápido debido a la falta de necesidad de boxeo. La siguiente tabla de comparación (construida con las respuestas encontradas en una publicación similar de preguntas SO ) ilustra algunas de las otras razones que admiten diccionarios sobre tablas hash (o viceversa).

janeon
fuente
1

Si le interesa la lectura que siempre devolverá los objetos en el orden en que se insertan en un Diccionario, puede echar un vistazo a

OrderedDictionary : se puede acceder a los valores a través de un índice entero (por orden en que se agregaron los elementos) SortedDictionary : los elementos se ordenan automáticamente

Toxina
fuente
0

El diccionario es más rápido que la tabla hash, ya que el diccionario es un tipo fuerte genérico. Hashtable es más lento, ya que toma el objeto como tipo de datos, lo que conduce al boxeo y al desempaquetado.

jitendra mahaapatro
fuente
2
phase9studios.com/post/2008/01/08/DictionaryVSHashTable.aspx por favor lea los comentarios debajo del artículo
Arvand
44
@Arvand Link roto - dominio en venta.
RenniePet