¿Cómo hace un diccionario una búsqueda rápida

Question

Estoy buscando en la fuente Item[TKey] de Dictionary<TKey,TValue> tratando de comprender el mecanismo de almacenamiento/recuperación en un diccionario, y por qué es más rápido que simplemente verificando cada entrada una por una.

Donde me confundo es en el usuario de los números primos en el campo buckets y la interacción con Entry<TKey,TValue>.next.

¿Puede alguien explicarme la lógica, o señalar una referencia donde puedo entenderlo?

Gracias.

Answer 1

Ver Hash Tables y posiblemente this article about using prime numbers in hash table implementations.

Answer 2

Mira en hashcodes, permiten el diccionario para 'cubo' las claves:

http://msdn.microsoft.com/en-us/library/4yh14awz%28VS.80%29.aspx

Colin E.

Answer 3

vistazo a este artículo de Wikipedia: Hashtable

Un diccionario es simplemente un tipo fuerte d implementación de una tabla hash. Tiene una serie de "cubos" donde coloca los artículos con sus llaves.

Cuando agrega un elemento a la tabla hash, utiliza el código hash de la clave para decidir en qué depósito va a ubicarlo (normalmente es una operación muy rápida, simplemente llame al GetHashCode y aplique un módulo a la misma). Una vez que tiene el segmento (que es un tipo de lista), comprueba si el contenedor ya contiene un elemento con la misma clave y lo agrega si no es el caso. Esto también es bastante rápido, porque cada segmento contiene solo un pequeño subconjunto de todos los elementos en la tabla hash.

Cuando desea recuperar un elemento en función de su clave, determina el depósito en función del código hash de la clave y busca un elemento con esta clave en el depósito.

Por supuesto, esta es una descripción muy simplista ... mira el artículo de Wikipedia para más detalles.