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
:
Synchronized()
KeyValuePair
: KeyValuePair
< << >>> Artículo KeyValuePair
: DictionaryEntry
Hashtable
Dictionary
/ Hashtable
:
GetHashCode()
Colecciones .NET similares (candidatos para usar en lugar de Dictionary y Hashtable):
ConcurrentDictionary
– thread 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
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
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
, 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, Dictionary
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.