¿Cómo funciona el proceso de hash en Dictionary <TKey, TValue>

Question

¿Cómo funciona el proceso de hashing en Dictionary? Leí que usar diccionario proporciona una búsqueda más rápida. Pero no entendí cómo? ¿Cómo ocurre el hash y el mapeo de un índice? No se pudo encontrar ninguna buena referencia.

EDITAR: ¿Cómo se obtiene la ubicación real de la memoria donde se almacena el objeto a partir del resultado de la función hash?

Answer 1

El proceso de hash en un diccionario utiliza una técnica que se denomina encadenamiento. Con el encadenamiento, 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 un cubo. En caso de una colisión, el elemento que colisiona se antepone a la lista del cubo.

Consulte el artículo this en MSDN para obtener más información.

Answer 2

Al utilizar un concepto de informática denominado Hash Map. Esto funciona más rápido que buscar una lista. Esto funciona al evitar que la búsqueda itere a través de una lista hasta que encuentra una coincidencia. En cambio, la clave es "hashed" y se usa como índice en una lista. Esta función de hash es casi siempre más rápida que buscar en la lista (iterar con comparaciones múltiples).

Answer 3

Por lo general, tomando el valor de hash%% array size, que puede producir una colisión.

Answer 4

Diccionario utiliza claves hash para la búsqueda como traté de explicar en my answer to your other question. Entonces, si tiene un tipo de objeto personalizado como clave, todo depende de la implementación GetHashKey() de su objeto personalizado.

Answer 5

Una tabla o diccionario hash es una estructura de datos que almacena parejas clave-valor. La ventaja de la tabla hash es que, dado el hallazgo de una clave, el valor correspondiente es bastante rápido. Simplificado, el tiempo para encontrar un par clave-valor en la tabla hash no depende del tamaño de la tabla. Compare eso para almacenar los pares clave-valor en una lista o una matriz. Para encontrar un par clave-valor, debería buscar la lista desde el principio hasta encontrar una clave coincidente. Cuanto más larga sea la lista, más tiempo tomará encontrar el par clave-valor. Usando la notación de O grande, puede decir que buscar una clave en una tabla hash es de orden O (1) mientras busca una tecla en una lista usando la búsqueda lineal es de orden O (N) (simplificada).

Para insertar un par clave-valor en la tabla hash, primero tendrá que calcular el código hash de la clave. En .NET todos los objetos tienen un método llamado GetHashCode que devuelve un código hash (entero de 32 bits) para ese objeto en particular. Es importante que los objetos iguales devuelvan el mismo código hash, pero también es muy útil si los diferentes objetos devuelven diferentes códigos hash. Tenga cuidado con la idea errónea de que los diferentes objetos no pueden devolver el mismo código hash; pueden hacerlo, pero dará como resultado una colisión (consulte a continuación).

Como ejemplo, consideremos los códigos hash de dos cadenas:

 
"Boo" 0x598FD95A 
"Foo" 0x598FD8DE 

A pesar de que las cuerdas son muy similares que tienen diferentes códigos hash.

Aquí estoy simplificando un poco las cosas para centrarme en los aspectos importantes de una tabla hash, por lo que, por ahora, digamos que internamente Dictionary<TKey, TValue> almacena los pares clave-valor en una matriz. Para ubicar el índice en esta matriz donde se almacenará el par clave-valor, debe calcular el código hash del módulo de la clave del tamaño de la matriz.Suponga que el tamaño de la matriz es de 5:

 
Index("Boo") = 0x598FD95A % 5 = 4 
Index("Foo") = 0x598FD8DE % 5 = 0 

Esto conduce a esta matriz de tabla hash interna:

 
+---+---------+ 
| 0 | "Foo" | 
+---+---------+ 
| 1 | (empty) | 
+---+---------+ 
| 2 | (empty) | 
+---+---------+ 
| 3 | (empty) | 
+---+---------+ 
| 4 | "Boo" | 
+---+---------+ 

Mirando hacia arriba una entrada en la tabla hash es muy rápido. Simplemente tiene que calcular el código hash del módulo de la clave del tamaño de la matriz interna y recuperar la cadena en ese índice.

Consideremos ahora la tecla "Zoo":

 
Index("Zoo") = 0x598FDC62 % 5 = 0 

Tiene el mismo índice que la tecla "Boo". Esto da como resultado lo que se llama una colisión . Una implementación adecuada de una tabla hash tendrá que manejar las colisiones y hay different strategies for doing that. Además, a medida que la matriz interna se llena, habrá menos elementos vacíos en la matriz, lo que dará como resultado un número creciente de colisiones. El factor de carga es la relación entre los elementos usados ​​y los elementos totales en la matriz interna. En el ejemplo anterior, el factor de carga es 2/5 = 0.4. La mayoría de las implementaciones de tablas hash aumentarán el tamaño de la matriz interna cuando el factor de carga exceda un cierto umbral.

Si desea obtener más información sobre algunos de estos conceptos, deberá estudiar algunos de los recursos más completos vinculados en otras respuestas.