.net - informatica - huella hash

¿Por qué un objeto System.String no almacena en caché su código hash?

Question

Un vistazo al código fuente de string.GetHashCode usando Reflector revela lo siguiente (para mscorlib.dll versión 4.0):

public override unsafe int GetHashCode()
{
    fixed (char* str = ((char*) this))
    {
        char* chPtr = str;
        int num = 0x15051505;
        int num2 = num;
        int* numPtr = (int*) chPtr;
        for (int i = this.Length; i > 0; i -= 4)
        {
            num = (((num << 5) + num) + (num >> 0x1b)) ^ numPtr[0];
            if (i <= 2)
            {
                break;
            }
            num2 = (((num2 << 5) + num2) + (num2 >> 0x1b)) ^ numPtr[1];
            numPtr += 2;
        }
        return (num + (num2 * 0x5d588b65));
    }
}

Ahora, me doy cuenta de que la implementación de GetHashCode no está especificada y depende de la implementación , por lo que la pregunta "¿está implementado GetHashCode en forma de X o Y?" no es realmente responsable. Solo tengo curiosidad por algunas cosas:

1. Si Reflector ha desensamblado la DLL correctamente y esta es la implementación de GetHashCode (en mi entorno), ¿tengo razón al interpretar este código para indicar que un objeto de string , basado en esta implementación particular, no almacenaría en caché su código hash?
2. Suponiendo que la respuesta es sí, ¿por qué sería esto? Me parece que el costo de la memoria sería mínimo (un entero más de 32 bits, una gota en el estanque en comparación con el tamaño de la cadena misma), mientras que los ahorros serían significativos, especialmente en los casos en que, por ejemplo, se utilizan cuerdas como claves en una colección basada en hashtable como un Dictionary<string, [...]> . Y dado que la clase de string es inmutable, no es como el valor devuelto por GetHashCode incluso cambiará.

¿Qué podría estar perdiendo?

ACTUALIZACIÓN : En respuesta a la observación final de Andras Zoltan:

También está el punto hecho en la respuesta de Tim (+1 allí). Si tiene razón, y creo que sí, entonces no hay garantía de que una cuerda sea inmutable después de la construcción, por lo tanto, almacenar en caché el resultado sería incorrecto.

Whoa, whoa allí! Este es un punto interesante para hacer (y sí, es muy cierto ), pero realmente dudo que esto se haya tenido en cuenta en la implementación de GetHashCode . La afirmación "por lo tanto, almacenar el resultado sería incorrecto" implica para mí que la actitud del marco con respecto a las cadenas es "Bueno, se supone que son inmutables, pero realmente si los desarrolladores quieren ser astuto son mutables, así que trataremos ellos como tales ". Esta definitivamente no es la forma en que el marco ve las cadenas . Se basa completamente en su inmutabilidad de muchas maneras (internación de literales de cadena, asignación de todas las cadenas de longitud cero a string.Empty , etc.) que, básicamente, si muta una cadena, está escribiendo código cuyo comportamiento es completamente indefinido e impredecible.

Supongo que mi punto es que los autores de esta implementación se preocupen, "¿Qué pasa si esta instancia de cadena se modifica entre las llamadas, a pesar de que la clase como está públicamente expuesta es inmutable?" sería como si alguien planificara una barbacoa informal al aire libre para pensar: "¿Y si alguien trae una bomba atómica a la fiesta?" Mira, si alguien trae una bomba atómica, la fiesta termina.

Answer 1

Cualquier valor int es un HashCode válido. Esto significa que no hay un valor int predeterminado como -1 o 0 que podamos usar para indicar que todavía no hemos calculado el HashCode. Entonces, si una cadena fuera a almacenar en caché su HashCode, necesitaría hacer una de las siguientes acciones:

• Tener un campo int para HashCode, más un campo bool para servir como indicador de si el HashCode ya se ha calculado, y luego solo computar el HashCode la primera vez que se solicita (evaluación diferida) o
• Tener un campo int para HashCode, y siempre calcular el HashCode cuando se construye la cadena.

Ambas opciones tienen un inconveniente; el primero requiere aún más memoria adicional, y el segundo tiene el costo de rendimiento de computación de HashCodes que quizás nunca se necesite.

Ahora considere el caso de Dictionary<TKey,TValue> . El código Hash utilizado por el diccionario depende del comparador que se utilice. El comparador predeterminado usará el método GetHashCode () normal del objeto. Pero podría crear un diccionario que utilice un comparador insensible a mayúsculas / minúsculas, por ejemplo, y el código Hash utilizado por el diccionario será producido por ese comparador, que probablemente produzca un String.GetHashCode() completamente diferente de String.GetHashCode() . Entonces, ¿qué HashCode hace la caché de cadenas? Una cadena puede estar en dos diccionarios, cada uno usando un comparador diferente, ninguno de los cuales usa la cadena normal GetHashCode. Así que la cadena podría estar guardando en caché un código Hash que ninguno de los diccionarios usó.

En el caso de Dictionary<TKey,TValue> , existe una razón aún más importante por la que las cadenas en caché de sus HashCodes probablemente no proporcionen ningún beneficio de rendimiento. La implementación interna de Dictionary hace lo siguiente cuando se agrega una nueva entrada:

• Calcula el HashCode de la clave utilizando el método GetHashCode () del comparador de igualdad proporcionado en la construcción, o el comparador predeterminado si no se especificó ninguno.
• Quita el signo de HashCode
• Almacena la nueva entrada, que consiste en el HashCode modificado desde arriba, la clave, el valor y el índice de la siguiente entrada en la lista de entradas que se asignan al mismo segmento.

Cuando el diccionario realiza una búsqueda clave, calcula el HashCode modificado (es decir, positivo) de la clave que se está buscando, obtiene el depósito al que se asigna HashCode y luego mira a través de la lista de entradas en ese segmento. Para verificar si una entrada es una coincidencia, primero comprueba si los HashCodes modificados coinciden (si las claves son iguales, los HashCodes también deben ser iguales), y si son iguales, verifica si las dos claves son iguales también. En el caso de las cadenas, este algoritmo logra dos cosas; primero, evita muchas comparaciones de cadenas al usar un entero simple para comparar primero para ver si vale la pena hacer una comparación de cadenas, y segundo, almacena en caché los HashCodes de cada tecla en el Diccionario. El Código Hash de cada clave en el Diccionario se calcula solo una vez, cuando el par clave / valor se agrega al Diccionario .

(Si se está preguntando por qué Dictionary elimina el bit de signo del HashCode, es porque utiliza un -1 como valor de marcador en el campo hashCode para espacios de entrada que están actualmente vacíos).

Answer 2

En primer lugar, no se sabe si el almacenamiento en caché de este resultado realmente mejoraría Dictionary<string, ...> et al porque no necesariamente usan String.GetHashCode, porque usa un IComparer para obtener el código de hash para una cadena.

Y si sigue la cadena probable de llamadas para la clase StringComparer, termina yendo a la clase System.Globalization.CompareInfo, que finalmente termina en este método:

[SecurityCritical, SuppressUnmanagedCodeSecurity, DllImport("QCall",
   CharSet=CharSet.Unicode)]
private static extern int InternalGetGlobalizedHashCode(IntPtr handle, string
   localeName, string source, int length, int dwFlags);

No se sabe si esa biblioteca, que parece ser un método nativo, no utiliza alguna forma de almacenamiento en caché interno basado en la estructura de datos de objetos .NET subyacente que no podemos obtener de inmediato dentro del tiempo de ejecución .Net.

Sin embargo, lo importante a tener en cuenta con esto es que una cadena puede tener muchos códigos hash diferentes en función de cómo elija interpretar los caracteres. De acuerdo, esta implementación es culturalmente precisa, por lo que no es adecuada para estos comparadores.

Entonces, aunque el almacenamiento de memoria adicional podría ser un factor, en realidad creo que es porque almacenar un código hash junto con una instancia de la cadena induce a la persona que llama, y ​​de hecho al equipo de desarrollo interno .Net (!), A pensar que la cadena solo tiene un código hash, cuando de hecho depende completamente de cómo va a interpretarlo, como una serie de bytes (que la mayoría de nosotros no), o como una serie de caracteres imprimibles.

Desde un punto de vista del rendimiento, entonces, si también aceptamos que estos comparadores utilizados por Dictionary<,> etc. no pueden usar la implementación interna, no almacenar en caché este resultado probablemente no tenga mucho impacto porque, francamente, cómo a menudo este método se llamará en el mundo real: la mayoría de las veces, un código de hash de una cadena probablemente se calcule a través de algún otro mecanismo.

EDITAR

También está el punto hecho en la respuesta de Tim (+1 allí). Si tiene razón, y creo que sí, entonces no hay garantía de que una cuerda sea inmutable después de la construcción, por lo tanto, almacenar en caché el resultado sería incorrecto.

UNA EDICION ADICIONAL (!)

Dan señala que las cadenas están destinadas a ser inmutables dentro de la esfera de red y, por lo tanto, esa cadena debería tener la libertad de almacenar en caché su propio código hash basado en esto. El problema aquí es que el framework .Net también proporciona una forma legítima de cambiar la cadena supuestamente inmutable que no involucra la reflexión privilegiada o cualquier otra cosa. Es un problema fundamental con las cadenas, es un puntero a un buffer que no puedes controlar. No importa en el mundo de C #, ¿qué pasa en C ++, donde el uso de vectores y la modificación de los búferes de memoria es un lugar común. El hecho de que idealmente no debería hacerlo no significa que el marco debe esperar que no lo haga.

.Net proporciona esta funcionalidad y, por lo tanto, si esta fue una decisión de diseño del equipo de .Net en respuesta al tipo de matiz binario sugerido por Tim, entonces fueron muy sabios de haberlo tenido en cuenta. Si lo hicieron, o si fue por casualidad, ¡es otra cosa completamente diferente! :)

Answer 3

Puede que haya llegado a una conclusión incorrecta aquí, pero ¿no es cierto que, aunque la cadena es inmutable en el contexto de un objeto .NET String, aún es posible cambiar el valor?

Por ejemplo, si estabas dispuesto a hacer esto ...

String example = "Hello World";

unsafe
{
    fixed (char* strPointer = myString) {
        strPointer[1] = ''a'';
    }
} 

... ¿No seguiría representando el example el mismo objeto String, pero ahora con un valor que computaría un valor diferente para GetHashCode() ? Puede que esté fuera de la base aquí, pero dado que podrías hacer esto fácilmente (si no es inútil), eso también causaría algunos problemas.

Answer 4

Respuesta potencial obvia: porque eso costará la memoria.

Aquí hay un análisis de costo / beneficio:

Costo : 4 bytes por cada cadena (y una prueba rápida en cada llamada a GetHashCode). También haga que el objeto cadena sea mutable, lo que obviamente significa que debe tener cuidado con la implementación, a menos que siempre calcule el código hash por adelantado, lo cual es un costo de calcularlo una vez por cada cadena, independientemente de si alguna vez hash en absoluto.

Ventaja : Evite volver a calcular el hash para valores de cadena hash más de una vez

Sugeriría que en muchos casos, hay muchos, muchos objetos de cadenas y muy pocos de ellos son hash más de una vez, lo que lleva a un costo neto. En algunos casos, obviamente ese no será el caso.

No creo que esté en una buena posición para juzgar cuál surge más a menudo ... Espero que MS haya instrumentado varias aplicaciones reales. (También espero que Sun haga lo mismo con Java, que almacena el hash en caché ...)

EDITAR: Acabo de hablar con Eric Lippert sobre esto (NDC es increíble :) y, básicamente, se trata del éxito de la memoria extra frente a los beneficios limitados.

Answer 5

Una razón más potencial para esto es que las cadenas internas (específicamente aquellas que se agregan como datos de solo lectura compartidos por el compilador) pueden tener exactamente el mismo formato que cualquier otra cadena. El hecho de que estas cadenas se carguen en la memoria de solo lectura significa que esas páginas de datos se pueden compartir fácilmente en todo el proceso, pero que tampoco sería posible tenerlas en caché como código hash.

Pero como otros han mencionado, la razón principal para no almacenar en caché el valor es que es probable que el uso de memoria adicional supere con creces los potenciales ahorros de almacenamiento en hashcode. El tiempo de ejecución de GetHashCode es O (N) en la longitud de la cadena, por lo que el peor de los escenarios de hashing repetido está bien delimitado.