Como sabemos, hay 2 estrategias clásicas para la resolución de colisiones: encadenamiento independiente y direccionamiento abierto.¿Qué tipo de resolución de colisión se elige para la implementación de HashTable/Dictionary en .net?
Me pregunto cuál fue el elegido para HashTable/Dictionary en .net.
¿O se utilizaron alguna otra estrategia?
Todo se describe en este documento en el MSDN: An Extensive Examination of Data Structures Using C# 2.0
... colisión resolución técnica llamada rehasing, que es la técnica utilizada por clase Hashtable de .NET Framework. En la sección final , veremos la clase de diccionario, que utiliza una técnica de resolución de colisiones conocida como encadenamiento. ....
... Rehasing funciona de la siguiente manera: hay un conjunto de hash de diferentes funciones, H1 ... Hn, y al insertar o recuperar un elemento de la tabla hash, en un principio el hash H1 la función se usa. Si esto lleva al a una colisión, se intenta H2 y en su lugar hasta Hn si es necesario. La sección anterior mostraba solo una función hash, que es la función hash inicial (H1). Las otras funciones hash son muy similares a esta función, solo diferenciando por un factor multiplicativo. En general, la función hash Hk se define como:
Hk(key) = [GetHash(key) + k * (1 + (((GetHash(key) >> 5) + 1) % (hashsize – 1)))] % hashsize
La clase Dictionary difiere de la clase Hashtable en más de un . Además de estar fuertemente tipado, el Diccionario también emplea una estrategia de resolución de colisión diferente que la clase Hashtable , utilizando una técnica denominada encadenamiento. Recuerde que con el sondeo , en caso de una colisión, se prueba otra ranura en la lista de cubos . (Con el reajuste, el hash se vuelve a calcular y se intenta con la nueva ranura ). Sin embargo, 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 ese segmento. En el evento de una colisión, el elemento que colisiona se antepone a la lista del segmento .
Recuerde que sólo la primera frase es mía :-)
Un 'Diccionario' no tiene una estructura de datos secundaria para contener colisiones. Al menos en C# 4 no. – Gabe
@Gabe: ¿Podría proporcionar otra explicación o enlace, tal vez? – Seb
@Gabe: ¿Podrías dar más detalles? Parece una descripción bastante precisa del 'Diccionario
que en realidad es una pregunta muy interesante; Acabo de hacer un blog post sobre cómo se implementa Dictionary entre bastidores. Puedo cubrir Hashtable en una posterior.
Buena pregunta. Probablemente nunca hubiera buscado ese documento si no hubiera publicado esta pregunta. –