c# - item - ¿Por qué es el diccionario preferido sobre Hashtable?

hashtable item c#

Question

En la mayoría de los lenguajes de programación, los diccionarios se prefieren a las tablas hash. ¿Cuáles son las razones detrás de eso?

Answer 1

Debido a que Dictionary es una clase genérica ( Dictionary<TKey, TValue> ), el acceso a su contenido es de tipo seguro (es decir, no es necesario realizar la conversión desde Object , como hace con un Hashtable ).

Comparar

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

a

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

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

Answer 2

Desde .NET Framework 3.5, también hay un HashSet<T> que proporciona todas las ventajas del Dictionary<TKey, TValue> si solo necesita las claves y ningún valor.

Entonces, si usa un Dictionary<MyType, object> y siempre establece el valor en null para simular el tipo de tabla hash segura, debería considerar cambiar al HashSet<T> .

Answer 3

El extenso examen de estructuras de datos usando el artículo de C # en MSDN indica que también hay una diferencia en la estrategia de resolución de colisiones :

La clase Hashtable utiliza una técnica llamada rehashing .

El restablecimiento funciona de la siguiente manera: hay un conjunto de funciones hash diferentes, H ₁ ... H _n , y al insertar o recuperar un elemento de la tabla hash, inicialmente se utiliza la función hash H1. Si esto conduce a una colisión, se prueba H _{2 en} su lugar, y en adelante hasta H _n si es necesario.

El Diccionario utiliza una técnica conocida como encadenamiento .

Con rehashing, en el caso de una colisión, se recalcula el hash y se prueba la nueva ranura correspondiente al hash. Sin embargo, con el encadenamiento, se utiliza una estructura de datos secundaria para mantener cualquier colisión . Específicamente, cada ranura en el Diccionario tiene una matriz de elementos que se asignan a ese cubo. En el caso de una colisión, el elemento de colisión se añade a la lista del grupo.

Answer 4

El Hashtable es una estructura de datos de tipo débil, por lo que puede agregar claves y valores de cualquier tipo al Hashtable . La clase de Dictionary es una implementación Hashtable segura para el tipo, y las claves y los valores se escriben con fuerza. Al crear una instancia de Dictionary , debe especificar los tipos de datos tanto para la clave como para el valor.

Answer 5

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

Answer 6

FYI: En .NET, Hashtable es seguro para subprocesos para el uso de varios subprocesos de lectura y un único subproceso 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 la instancia lo sea.

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

Answer 7

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

Esto no necesariamente es cierto. Una tabla hash es una implementación de un diccionario. Una típica en eso, y puede ser la predeterminada en .NET, pero no es la única por definición.

También podría implementar un diccionario con una lista enlazada o un árbol de búsqueda, simplemente no sería tan eficiente (por alguna métrica de eficiente).

Answer 8

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 HashTable "

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

En .NET 1.0 los genéricos no existían; aquí es donde originalmente empezaron HashTable y ArrayList.

Answer 9

Otra diferencia importante es que Hashtable es seguro para subprocesos. Hashtable ha incorporado la seguridad de subprocesos de lector único / escritor único (MR / SW), lo que significa que Hashtable permite UN escritor junto con varios lectores sin bloqueo.

En el caso del Diccionario no hay hilo de seguridad; Si necesita seguridad de subprocesos, debe implementar su propia sincronización.

Para seguir elaborando:

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. La envoltura funciona al bloquear toda la colección 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 bloqueo. 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 la carrera.

Las clases de colección de .NET Framework 2.0 como List<T>, Dictionary<TKey, TValue> , 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 varios subprocesos simultáneamente

Si necesita seguridad de tipos y seguridad de subprocesos, use clases de colecciones concurrentes en .NET Framework. Lectura adicional here .

Una diferencia adicional es que cuando agregamos las entradas múltiples 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.

Answer 10

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

Si quiso decir "¿por qué usamos la clase Dictionary<TKey, TValue> lugar de la clase Hashtable ?", Entonces es una respuesta fácil: Dictionary<TKey, TValue> es un tipo genérico, Hashtable no lo es. Eso significa que obtiene seguridad de tipo con Dictionary<TKey, TValue> , porque no puede insertar ningún objeto aleatorio en él, y no tiene que emitir los valores que saque.

Curiosamente, la implementación del Dictionary<TKey, TValue> en .NET Framework se basa en el Hashtable , como se puede ver en este comentario en su código fuente:

El Diccionario genérico fue copiado de la fuente de Hashtable.

Source

Answer 11

Según lo que veo usando .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;

Por lo tanto, podemos estar seguros de que DictionaryBase usa una HashTable internamente.

Answer 12

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

La clase Diccionario tiene la misma funcionalidad que la clase Hashtable. Un Diccionario de un tipo específico (distinto de Objeto) tiene mejor rendimiento que un Hashtable para tipos de valor porque los elementos de Hashtable son de tipo Objeto y, por lo tanto, el boxeo y el desempaquetado suelen ocurrir al almacenar o recuperar un tipo de valor.

Para leer más: Hashtable y Tipos de colecciones de diccionarios.

Answer 13

Una diferencia más que puedo entender es:

No podemos utilizar Dictionary <KT, VT> (genéricos) con servicios web. La razón es que ningún estándar de servicio web admite el estándar de genéricos.

Answer 14

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

Al llegar a la diferencia entre HashTable y Dictionary , Dictionary es genérico, mientras que Hastable no es Genérico. Podemos agregar cualquier tipo de objeto a HashTable , pero al recuperar, debemos convertirlo al tipo requerido. Por lo tanto, no es de tipo seguro. Pero al dictionary , mientras nos declaramos a nosotros mismos podemos especificar el tipo de clave y valor, por lo que no hay necesidad de realizar conversiones 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<int, string> dt = new Dictionary<int, string>();
dt.Add(1, "One");
dt.Add(2, "Two");
dt.Add(3, "Three");
foreach (KeyValuePair<int, String> kv in dt)
{
Console.WriteLine(kv.Key + " " + kv.Value);
}
}
}

Answer 15

Dictionary<> es un tipo genérico y por lo tanto es de tipo seguro.

Puede insertar cualquier tipo de valor en HashTable y esto a veces puede generar una excepción. Pero Dictionary<int> solo aceptará valores enteros y, de manera similar, Dictionary<string> solo aceptará cadenas.

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

Answer 16

Dictionary <<< >>> Diferencias Hashtable :

• Genérico <<< >>> No genérico
• Necesita su propia sincronización de subprocesos <<< >>> Ofrece una versión segura de subprocesos mediante el método Synchronized()
• Artículo KeyValuePair : KeyValuePair <<< >>> Artículo KeyValuePair : DictionaryEntry
• Más reciente (> .NET 2.0 ) <<< >>> Anterior (desde .NET 1.0 )
• está en System.Collections.Generic <<< >>> está en System.Collections
• La solicitud de una clave no existente lanza la excepción <<< >>> La solicitud de una clave no existente devuelve null
• potencialmente un poco más rápido para los tipos de valor <<< >>> bit más lento (necesita boxeo / desempaquetado) para los tipos de valor

Dictionary / similitudes Hashtable :

• Ambas son tablas hash internas == acceso rápido a datos de muchos artículos según la clave
• Ambos necesitan llaves inmutables y únicas.
• Las claves de ambos necesitan el propio método GetHashCode()

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

• ConcurrentDictionary - hilo seguro (se puede acceder de forma segura desde varios hilos 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 el orden en que se agregaron los artículos)
• SortedDictionary - artículos ordenados automáticamente
• StringDictionary - fuertemente tipado y optimizado para cadenas

Answer 17

Diccionario:

• Devuelve / lanza Excepción si intentamos encontrar una clave que no existe.

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

• Sólo los miembros estáticos públicos son seguros para subprocesos.

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

  Ejemplo: Dictionary<string, string> <NameOfDictionaryVar> = new Dictionary<string, string>();

• 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 intentamos encontrar una clave que no existe.

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

• Todos los miembros en un Hashtable son seguros para hilos,

• Hashtable no es un tipo genérico,

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

Answer 18

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 al tipo deseado mientras se lee desde el montón.

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

Diccionario: Variante genérica de HashTable.

No boxeo / unboxing. No se requieren conversiones.