¿Por qué se prefiere Dictionary a Hashtable?

En la mayoría de los lenguajes de progtwigción, los diccionarios son preferibles a los hashtables. ¿Cuáles son las razones detrás de eso?

Por lo que vale, un Diccionario es (conceptualmente) una tabla hash.

Si quería decir “¿por qué usamos la clase Dictionary lugar de la clase Hashtable ?”, Entonces es una respuesta fácil: Dictionary es un tipo genérico, Hashtable no. Eso significa que obtienes seguridad de tipo con Dictionary , porque no puedes insertar ningún objeto aleatorio en él, y no tienes que convertir los valores que sacas.

Curiosamente, la implementación de Dictionary en .NET Framework se basa en Hashtable , como puede deducirse de este comentario en su código fuente:

El diccionario genérico fue copiado de la fuente de Hashtable

Fuente

Dictionary < << >>> Diferencias de Hashtable :

  • Genérico < << >>> No genérico
  • Necesita sincronización de hilo propio < << >>> Ofrece versión segura para hilo a través del método Synchronized()
  • Artículo KeyValuePair : KeyValuePair < << >>> Artículo KeyValuePair : DictionaryEntry
  • Más nuevo (> .NET 2.0 ) < << >>> Más antiguo (desde .NET 1.0 )
  • está en System.Collections.Generic < << >>> está en System.Collections
  • Petición de excepción de lanzamiento de clave no existente < << >>> Petición de clave no existente devuelve nulo
  • potencialmente un poco más rápido para tipos de valor < << >>> poco más lento (necesita boxeo / unboxing) para tipos de valor

Hashtable Dictionary / Hashtable :

  • Ambas son tablas internas == acceso rápido a datos de muchos elementos según la clave
  • Ambos necesitan claves inmutables y únicas
  • Las claves de ambos necesitan su propio método GetHashCode()

Colecciones .NET similares (candidatos para usar en lugar de Dictionary y Hashtable):

  • ConcurrentDictionarythread safe (se puede acceder de forma segura desde varios subprocesos al mismo tiempo)
  • HybridDictionary : rendimiento optimizado (para pocos artículos y también para muchos artículos)
  • OrderedDictionary : se puede acceder a los valores a través del índice int (por orden en que se agregaron los ítems)
  • SortedDictionary : elementos ordenados automáticamente
  • StringDictionary : fuertemente tipado y optimizado para cadenas

Porque Dictionary es una clase genérica ( Dictionary ), por lo que el acceso a su contenido es seguro para el tipo (es decir, no es necesario enviar desde Object , como lo hace con una Hashtable ).

Comparar

 var customers = new Dictionary(); ... Customer customer = customers["Ali G"]; 

a

 var customers = new Hashtable(); ... Customer customer = customers["Ali G"] as Customer; 

Sin embargo, Dictionary se implementa como Hashtable dentro, por lo que técnicamente funciona de la misma manera.

FYI: en .NET, Hashtable es seguro para subprocesos para ser utilizado por varios subprocesos de lector y un solo hilo de escritura, mientras que en el Dictionary los miembros estáticos públicos son seguros para subprocesos, pero no se garantiza que ningún miembro de instancia sea seguro para subprocesos.

Tuvimos que cambiar todos nuestros diccionarios de nuevo a Hashtable debido a esto.

En .NET, la diferencia entre Dictionary< ,> y HashTable es principalmente que el primero es un tipo genérico, por lo que obtienes todos los beneficios de los generics en términos de comprobación de tipos estáticos (y reducción del boxeo, pero esto no es tan grande como la gente tiende a pensar en términos de rendimiento, aunque hay un costo definido de memoria para el boxeo).

La gente dice que un diccionario es lo mismo que una tabla hash.

Esto no es necesariamente cierto. Una tabla hash es una implementación de un diccionario. Uno típico en eso, y puede ser el predeterminado en .NET, pero no es por definición el único.

También podría implementar un diccionario con una lista vinculada o un árbol de búsqueda, simplemente no sería tan eficiente (para algunos indicadores de eficiencia).

Collections y los Generics son útiles para manejar grupos de objetos. En .NET, todos los objetos de colecciones vienen bajo la interfaz IEnumerable , que a su vez tiene ArrayList(Index-Value)) & HashTable(Key-Value) . Después de .NET framework 2.0, ArrayList y HashTable fueron reemplazados por List & Dictionary . Ahora, el Arraylist & HashTable ya no se usan en los proyectos actuales.

Llegando a la diferencia entre HashTable y Dictionary , el Dictionary es genérico donde Hastable no es genérico. Podemos agregar cualquier tipo de objeto a HashTable , pero al recuperarlo debemos convertirlo al tipo requerido. Entonces, no es seguro. Pero para el dictionary , mientras se declara a sí mismo, podemos especificar el tipo de clave y valor, por lo que no es necesario lanzar mientras se recupera.

Veamos un ejemplo:

Tabla de picadillo

 class HashTableProgram { static void Main(string[] args) { Hashtable ht = new Hashtable(); ht.Add(1, "One"); ht.Add(2, "Two"); ht.Add(3, "Three"); foreach (DictionaryEntry de in ht) { int Key = (int)de.Key; //Casting string value = de.Value.ToString(); //Casting Console.WriteLine(Key + " " + value); } } } 

Diccionario,

 class DictionaryProgram { static void Main(string[] args) { Dictionary dt = new Dictionary(); dt.Add(1, "One"); dt.Add(2, "Two"); dt.Add(3, "Three"); foreach (KeyValuePair kv in dt) { Console.WriteLine(kv.Key + " " + kv.Value); } } } 

Diccionario:

  • Devuelve / arroja Excepción si tratamos de encontrar una clave que no existe.

  • Es más rápido que un Hashtable porque no hay boxeo y unboxing.

  • Solo los miembros estáticos públicos son seguros para subprocesos.

  • El diccionario es un tipo genérico que significa que podemos usarlo con cualquier tipo de datos (al crear, debe especificar los tipos de datos para las claves y los valores).

    Ejemplo: Dictionary = new Dictionary();

  • Dictionay es una implementación segura de tipos de Hashtable, las Keys y los Values están fuertemente tipados.

Tabla de picadillo:

  • Devuelve nulo si tratamos de encontrar una clave que no existe.

  • Es más lento que el diccionario porque requiere boxeo y unboxing.

  • Todos los miembros en una Hashtable son seguros para subprocesos

  • Hashtable no es un tipo genérico,

  • Hashtable es una estructura de datos sin tipeo, podemos agregar claves y valores de cualquier tipo.

Desde .NET Framework 3.5 también hay un HashSet que proporciona todas las ventajas del Dictionary si solo necesita las claves y no tiene valores.

Entonces, si usa un Dictionary y siempre establece el valor en null para simular el tipo de tabla hash segura, tal vez deba considerar cambiar al HashSet .

El extenso examen de las estructuras de datos El uso del artículo de C # en MSDN indica que también existe una diferencia en la estrategia de resolución de colisiones :

La clase Hashtable utiliza una técnica denominada refrito .

El reinicio funciona de la siguiente manera: hay un conjunto de diferentes funciones hash, H 1 … H n , y al insertar o recuperar un elemento de la tabla hash, inicialmente se utiliza la función H 1 hash. Si esto lleva a una colisión, se intenta H 2 en su lugar, y en adelante hasta H n si es necesario.

El diccionario usa una técnica conocida como encadenamiento .

Con el reajuste, en el caso de una colisión se vuelve a calcular el hash y se prueba la nueva ranura correspondiente a un hash. Con el encadenamiento, sin embargo, se utiliza una estructura de datos secundaria para contener cualquier colisión . Específicamente, cada ranura en el Diccionario tiene una matriz de elementos que se asignan a ese cubo. En caso de una colisión, el elemento que colisiona se antepone a la lista del cubo.

El Hashtable es una estructura de datos de tipo suelto, por lo que puede agregar claves y valores de cualquier tipo a Hashtable . La clase Dictionary es una implementación Hashtable tipo seguro, y las claves y valores están fuertemente tipados. Al crear una instancia de Dictionary , debe especificar los tipos de datos para la clave y el valor.

Observe que MSDN dice: “La clase Dictionary < (Of <(TKey, TValue>)>) se implementa como una tabla hash “, no “la clase Dictionary < (Of <(TKey, TValue>)>) se implementa como una HashTable

El diccionario NO está implementado como HashTable, pero se implementa siguiendo el concepto de una tabla hash. La implementación no está relacionada con la clase HashTable debido al uso de Generics, aunque internamente Microsoft podría haber utilizado el mismo código y haber reemplazado los símbolos de tipo Object con TKey y TValue.

En .NET 1.0 Generics no existía; aquí es donde originalmente comenzó HashTable y ArrayList.

Un objeto Hashtable consiste en cubos que contienen los elementos de la colección. Un depósito es un subgrupo virtual de elementos dentro de Hashtable, lo que hace que la búsqueda y recuperación sea más fácil y más rápida que en la mayoría de las colecciones .

La clase Dictionary tiene la misma funcionalidad que la clase Hashtable. Un diccionario de un tipo específico (distinto de Object) tiene un mejor rendimiento que un Hashtable para tipos de valor porque los elementos de Hashtable son de tipo Object y, por lo tanto, el boxeo y el unboxing normalmente ocurren si se almacena o recupera un tipo de valor.

Para una lectura adicional: tipos de colección Hashtable y Diccionario

Tabla de picadillo:

La clave / valor se convertirá en un tipo de objeto (boxeo) mientras se almacena en el montón.

La clave / valor debe convertirse en el tipo deseado mientras se lee desde el montón.

Estas operaciones son muy costosas. Necesitamos evitar el boxeo / unboxing tanto como sea posible.

Diccionario: variante genérica de HashTable.

Sin boxeo / unboxing. No se requieren conversiones

Una diferencia más que puedo descubrir es:

No podemos usar Dictionary (generics) con servicios web. La razón es que ningún estándar de servicio web admite el estándar de generics.

Dictionary<> es un tipo genérico y es seguro.

Puede insertar cualquier tipo de valor en HashTable y esto a veces arroja una excepción. Pero Dictionary solo aceptará valores enteros y, de forma similar, Dictionary solo aceptará cadenas.

Por lo tanto, es mejor usar Dictionary<> lugar de HashTable .

Otra diferencia importante es que Hashtable es seguro para subprocesos. Hashtable tiene seguridad incorporada de hilos múltiples para lector / solo escritor (MR / SW) lo que significa que Hashtable permite UN escritor junto con varios lectores sin locking.

En el caso de Dictionary no hay seguridad de hilos; si necesita seguridad de hilos, debe implementar su propia sincronización.

Para elaborar más:

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

Las clases de colección de .NET Framework 2.0 como List, Dictionary , etc. no proporcionan ninguna sincronización de subprocesos; el código de usuario debe proporcionar toda la sincronización cuando los elementos se agregan o eliminan en múltiples hilos de manera concurrente

Si necesita seguridad de tipo y seguridad de subprocesos, use clases de colecciones concurrentes en .NET Framework. Lectura adicional aquí .

Una diferencia adicional es que cuando agregamos las múltiples entradas en el Diccionario, se mantiene el orden en que se agregan las entradas. Cuando recuperemos los elementos del Diccionario, obtendremos los registros en el mismo orden en que los insertamos. Mientras que Hashtable no conserva el orden de inserción.

De acuerdo con lo que veo al usar .NET Reflector :

 [Serializable, ComVisible(true)] public abstract class DictionaryBase : IDictionary, ICollection, IEnumerable { // Fields private Hashtable hashtable; // Methods protected DictionaryBase(); public void Clear(); . . . } Take note of these lines // Fields private Hashtable hashtable; 

Así que podemos estar seguros de que DictionaryBase utiliza una HashTable internamente.