¿Qué tan bien resuelve el diccionario .NET las colisiones?

Question

Tengo un problema con un objeto personalizado que debe estar codificado para una tabla. Necesito generar una clave numérica única. Tengo problemas de colisión y me pregunto si puedo aprovechar un diccionario para ayudarme. Supongamos que tengo un objeto como este:

class Thingy 
{ 
    public string Foo; 
    public string Bar; 
    public string Others; 
} 

y así sucesivamente con más campos. Digamos que Foo y Bar son mis campos clave: si son iguales entre dos Thingys, entonces los dos objetos se deben considerar iguales (uno puede representar una actualización para el otro, con los campos Otros actualizados). Tengo estos:

public override bool Equals(object obj) 
{ 
    Thingy thing = (Thingy)obj; // yes I do type check first 
    return (this.Foo == thing.Foo && this.Bar == thing.Bar); 
} 

public override int GetHashCode() 
{ 
    return (this.Foo + this.Bar).GetHashCode(); // using default string impl 
} 

por lo que esto funciona en su mayor parte, pero hay raras ocasiones en que dos Thingys que son realmente diferentes tienen el mismo código hash.

Mi pregunta es esta: ¿podría usar un Diccionario <Thingy, int> donde puse mi Thingys, y usar un valor secuencial que sale del diccionario como mi clave real? Me pregunto si el diccionario, al detectar una rara colisión de código hash, llamará a mi método Equals, determinará que los objetos son realmente diferentes y los almacenará de manera diferente. Imaginé luego, al buscarlo, vería un cubo para ese hash y buscaría el Thingy correcto, nuevamente usando Equals para comparar.

¿Es este el caso del diccionario, o solo resuelve colisiones donde el código hash es diferente, pero (hash% size) es el mismo? Si esto no funciona, ¿qué podría ser?

Answer 1

Las colisiones hash solo afectan el rendimiento, no la integridad.

Una prueba simple sería cambiar GetHashCode() para simplemente devolver 1 ;. Notará que el diccionario aún se comporta correctamente, pero con cualquier conjunto de datos razonable, funcionará terriblemente.

Answer 2

Las colisiones hash afectarán principalmente al rendimiento - no es correcto. Siempre que Equals() se comporte correctamente.

Dictionary usa el código hash como una forma de organizar los elementos en "cubos" separados. Si demasiados elementos comparten el mismo código hash, puede encontrarse con problemas de rendimiento. Sin embargo, siempre que Equals() distinga correctamente entre instancias, debe obtener resultados correctos.

Donde los códigos hash pueden ocasionar problemas es con objetos mutables. Si su clase Thingy permite Foo o Bar cambiar para un artículo en el diccionario, puede que no lo encuentre en un intento de acceso posterior. Esto se debe a que el código hash producido ahora difiere del usado para almacenar el valor en el diccionario.

Answer 3

GetHashCode está diseñado para usar en tablas hash, donde las colisiones deben minimizarse pero no eliminarse. Si necesita generar una clave realmente única, GetHashCode es un punto de partida razonable (y no tan largo como un guid), pero necesitará almacenar la clave como parte del objeto y mantener una lista de claves usadas por separado.

Si bien es posible que pueda recuperar algo que parece utilizable desde el interior del Diccionario, probablemente no funcione de manera confiable; por ejemplo, si agrega más elementos de los que el diccionario inicialmente asignó, la estructura de datos subyacente obtener reconstruido y los elementos individuales pueden terminar en una parte completamente diferente del diccionario.