Preguntas de la entrevista relacionadas con Hashtable y el diccionario

Question

Recientemente me han entrenado en un par de entrevistas sobre Hashtables y cuándo es necesario anular el GetHashCode(). La discusión siguió profundizándose hasta que tiré la toalla.

Ahora estoy haciendo una investigación para cubrir todo para estar listo para la próxima vez.

He encontrado este excelente artículo que me gustaría compartir: http://msdn.microsoft.com/en-us/library/ms379571(VS.80).aspx#datastructures20_2_topic5

1) Algo que no me siento muy cómodo con * son el hecho de que los diccionarios se basan Hash, pero las listas no son aparentemente . ¿Eso solo significa que la búsqueda en una lista <> y matriz [] es lineal, mientras que la búsqueda en un diccionario o hashtable es constante y, por lo tanto, mucho más rápida? ¿Esto es todo?

2) Si utilizo una clase como clave en un diccionario, debo anular GetHashcode() en esa clase en función de los campos de identificación necesarios para que las instancias sean únicas. Sin embargo, todavía podría suceder que ambos campos ID sean iguales y se genere el mismo código hash. Si este es el caso, ¿qué sucede durante una colisión de las dos instancias con el mismo código hash?

3) ¿Cómo se puede resolver la colisión? Leí en el artículo sobre la metodología de reajuste en caso de colisión para Hashtable y encadenamiento para el diccionario. Pero todavía no estoy seguro de cómo funciona exactamente, ya que no soy un genio de las matemáticas. : - \ ¿Alguien puede explicar mejor cómo funciona?

Muchas gracias, Kave

Answer 1

1) En general, sí, un Dictionary<T> o HashSet<T> tiene acceso de tiempo constante. La ubicación de un elemento en un List<T> no ordenado o matriz se debe hacer de forma lineal. Las colecciones ordenadas le permiten realizar búsquedas binarias, otorgando a O (log n) el tiempo de acceso.

2) Si anula GetHashCode en .NET, también debe anular el método Equals. En .NET Dictionary y HashSet, no puede insertar elementos que sean iguales. Las colisiones hash son inevitables en el caso general (a menos que haya calculado un hash perfecto). Hay varias formas de resolver colisiones.

3) Para obtener más información sobre la resolución de colisiones, consulte http://en.wikipedia.org/wiki/Hash_table.

Answer 2

Una tabla hash es una estructura de datos. Se puede encontrar más información en when looking for more general information.

1) Una búsqueda predeterminada en las listas es lineal (todos los elementos deben atravesarse). El hashing perfecto (sin colisiones) permite búsquedas de tiempo constante en el peor de los casos. Más colisiones resultan en una búsqueda más lenta.

2) Las colisiones hash son prácticamente inevitables cuando se crea un subconjunto aleatorio de un gran conjunto de claves posibles. Por lo tanto, la mayoría de las implementaciones de tablas hash tienen alguna estrategia de resolución de colisiones para manejar dichos eventos. La implementación Hashtable de .NET parece usar double hashing.

3) Esto es algo que no debes preocuparte, siempre y cuando proporciones los códigos hash adecuados. Cuando esté interesado, lea el artículo de la wiki sobre tablas hash, que explica varias técnicas.

ACTUALIZACIÓN: Hay a difference en la implementación de Hashtable y diccionarios en el manejo de colisiones. Aparentemente, Hashtable es obsoleto y se prefiere Dictionary o HashSet.

Como Jim Mischel menciona, debe anular GetHashCode y Equals. No es posible insertar elementos que son iguales, pero los elementos con el mismo código hash son manejados por el tipo de colección que elijas.