Calidad y estabilidad de hash de String.GetHashCode() en .NET?

Question

Me pregunto acerca de la calidad de hash y la estabilidad de hash producida por la implementación String.GetHashCode() en .NET?

En cuanto a la calidad, me estoy enfocando en los aspectos algorítmicos (por lo tanto, la calidad del hash ya que afecta las grandes tablas hash, no por cuestiones de seguridad).

Luego, con respecto a la estabilidad, me pregunto acerca de los posibles problemas de versión que pueden surgir de una versión de .NET a la siguiente.

Algunas luces en esos dos aspectos serían muy apreciadas.

Answer 1

No puedo darle ningún detalle sobre la calidad (aunque supongo que es bastante bueno, dado que la cadena es una de las principales clases del marco que es probable que se use como una clave hash).

Sin embargo, con respecto a la estabilidad, el código hash producido en diferentes versiones del marco no garantiza que sea el mismo, y ha cambiado en el pasado, por lo que no debe confiar en que el código hash sea estable entre versiones (see here for a reference that it changed between 1.1 and 2.0). De hecho, incluso difiere entre las versiones de 32 bits y 64 bits de la misma versión de marco; from the docs:

El valor devuelto por GetHashCode depende de la plataforma. Para un valor de cadena específico, difiere en las versiones de 32 bits y 64 bits de .NET Framework.

Answer 2

La calidad de los códigos hash es suficiente para su propósito previsto, es decir, no causan demasiadas colisiones cuando utiliza cadenas como clave en un diccionario. Sospecho que solo usará la cadena completa para calcular el código hash si la longitud de la cuerda es razonablemente corta, para cuerdas enormes usará la primera parte de manera amplia.

No hay garantía de estabilidad en todas las versiones. La documentación dice claramente que el algoritmo hashing puede cambiar de una versión a la siguiente, de modo que los códigos hash son para uso a corto plazo.

Answer 3

Acabo de encontrar un problema relacionado con esto. En una de mis computadoras (una de 64 bits) tuve un problema que rastreé hasta 2 objetos diferentes que eran idénticos excepto por el código hash (almacenado). Ese hashcode fue creado a partir de una cadena ... ¡la misma cadena!

m_storedhash = astring.GetHashCode();

No sé cómo estos dos objetos terminaron con diferentes códigos hash dados que eran de la misma cadena, sin embargo sospecho lo que pasó es que dentro de la misma exe .NET, uno de los proyectos de biblioteca de clase I Depende de se ha establecido en x86 y otro en ANYCPU y uno de estos objetos se creó en un método dentro de la lib de clase x86 y el otro objeto (mismos datos de entrada, el mismo todo) se creó en un método dentro de la biblioteca de clases ANYCPU.

Entonces, ¿suena plausible: dentro del mismo ejecutable en la memoria (no entre procesos) parte del código podría estar ejecutándose con la cadena del framework x86.GetHashCode() y otro código x64 Framework's string.GetHashCode()?

Answer 4

Sé que esto no incluye los significados de calidad y estabilidad que ha especificado, pero vale la pena tener en cuenta que las cadenas extremadamente grandes pueden producir una OutOfMemoryException.

https://connect.microsoft.com/VisualStudio/feedback/details/517457/stringcomparers-gethashcode-string-throws-outofmemoryexception-with-plenty-of-ram-available

Answer 5

Esta es una vieja pregunta, pero me gustaría contribuir mentionning this microsoft bug about hash quality.

Resumen: En 64b, la calidad del hash es muy baja cuando su cadena contiene '\ 0' bytes. Básicamente, solo el comienzo de la cadena será hash.

Si, como yo, tiene que usar cadenas .Net para representar datos binarios como clave para diccionarios de alto rendimiento, debe tener en cuenta este error.

Es una pena, es una WONTFIX ... Como comentario, no entiendo cómo se podría decir que la modificación del código hash ser un cambio importante, cuando el código incluye

// We want to ensure we can change our hash function daily. 
// This is perfectly fine as long as you don't persist the 
// value from GetHashCode to disk or count on String A 
// hashing before string B. Those are bugs in your code. 
hash1 ^= ThisAssembly.DailyBuildNumber; 

y el código hash es ya es diferente en x86/64b de todos modos.