¿Cómo se implementa GetHashCode() de la cadena C#?

.net string

Question

Solo tengo curiosidad porque supongo que tendrá un impacto en el rendimiento. ¿Considera la cadena completa? Si es así, será lento en una cadena larga. Si solo considera parte de la cadena, tendrá un mal rendimiento (por ejemplo, si solo considera el comienzo de la cadena, tendrá un mal rendimiento si un HashSet contiene principalmente cadenas con la misma.

Answer 1

Al examinar el código fuente (cortesía de ILSpy ), podemos ver que itera sobre la longitud de la cadena.

// string
[ReliabilityContract(Consistency.WillNotCorruptState, Cer.MayFail), SecuritySafeCritical]
public unsafe override int GetHashCode()
{
    IntPtr arg_0F_0;
    IntPtr expr_06 = arg_0F_0 = this;
    if (expr_06 != 0)
    {
        arg_0F_0 = (IntPtr)((int)expr_06 + RuntimeHelpers.OffsetToStringData);
    }
    char* ptr = arg_0F_0;
    int num = 352654597;
    int num2 = num;
    int* ptr2 = (int*)ptr;
    for (int i = this.Length; i > 0; i -= 4)
    {
        num = ((num << 5) + num + (num >> 27) ^ *ptr2);
        if (i <= 2)
        {
            break;
        }
        num2 = ((num2 << 5) + num2 + (num2 >> 27) ^ ptr2[(IntPtr)4 / 4]);
        ptr2 += (IntPtr)8 / 4;
    }
    return num + num2 * 1566083941;
}

Answer 2

Asegúrese de obtener el código fuente de la Fuente de referencia cuando tenga preguntas como esta. Hay mucho más que lo que puedes ver en un descompilador. Elija el que coincida con su objetivo .NET preferido, el método ha cambiado mucho entre las versiones. Reproduciré la versión de .NET 4.5 aquí, recuperada de Source.NET 4.5 / 4.6.0.0 / net / clr / src / BCL / System / String.cs / 604718 / String.cs

        public override int GetHashCode() { 

#if FEATURE_RANDOMIZED_STRING_HASHING
            if(HashHelpers.s_UseRandomizedStringHashing)
            { 
                return InternalMarvin32HashString(this, this.Length, 0);
            } 
#endif // FEATURE_RANDOMIZED_STRING_HASHING 

            unsafe { 
                fixed (char *src = this) {
                    Contract.Assert(src[this.Length] == ''/0'', "src[this.Length] == ''//0''");
                    Contract.Assert( ((int)src)%4 == 0, "Managed string should start at 4 bytes boundary");

#if WIN32
                    int hash1 = (5381<<16) + 5381; 
#else 
                    int hash1 = 5381;
#endif 
                    int hash2 = hash1;

#if WIN32
                    // 32 bit machines. 
                    int* pint = (int *)src;
                    int len = this.Length; 
                    while (len > 2) 
                    {
                        hash1 = ((hash1 << 5) + hash1 + (hash1 >> 27)) ^ pint[0]; 
                        hash2 = ((hash2 << 5) + hash2 + (hash2 >> 27)) ^ pint[1];
                        pint += 2;
                        len  -= 4;
                    } 

                    if (len > 0) 
                    { 
                        hash1 = ((hash1 << 5) + hash1 + (hash1 >> 27)) ^ pint[0];
                    } 
#else
                    int     c;
                    char *s = src;
                    while ((c = s[0]) != 0) { 
                        hash1 = ((hash1 << 5) + hash1) ^ c;
                        c = s[1]; 
                        if (c == 0) 
                            break;
                        hash2 = ((hash2 << 5) + hash2) ^ c; 
                        s += 2;
                    }
#endif
#if DEBUG 
                    // 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; 
#endif
                    return hash1 + (hash2 * 1566083941);
                }
            } 
        }

Posiblemente sea más de lo que esperaba, anotaré un poco el código:

• Las directivas de compilación condicional #if adaptan este código a diferentes objetivos .NET. Los identificadores FEATURE_XX están definidos en otra parte y desactivan las características de toda la oferta a través del código fuente de .NET. WIN32 se define cuando el destino es la versión de 32 bits del marco, la versión de 64 bits de mscorlib.dll se crea por separado y se almacena en un subdirectorio diferente del GAC.
• La variable s_UseRandomizedStringString habilita una versión segura del algoritmo hash, diseñado para evitar que los programadores tengan problemas que hagan algo imprudente como usar GetHashCode () para generar hashes para cosas como contraseñas o cifrado. Está habilitado por una entrada en el archivo app.exe.config
• La instrucción fija mantiene la indexación barata de la cadena, evita la comprobación de límites realizada por el indexador habitual
• El primer Assert asegura que la cadena termina en cero como debería ser, requerida para permitir la optimización en el ciclo
• El segundo Assert asegura que la cadena está alineada con una dirección que es un múltiplo de 4 como debería ser, requerida para mantener el rendimiento del bucle
• El ciclo se desenrolla a mano, consumiendo 4 caracteres por ciclo para la versión de 32 bits. El lanzamiento a int * es un truco para almacenar 2 caracteres (2 x 16 bits) en un int (32 bits). Las instrucciones adicionales después del bucle tratan con una cadena cuya longitud no es un múltiplo de 4. Tenga en cuenta que el terminador cero puede o no estar incluido en el hash, no lo será si la longitud es par. Mira a todos los personajes de la cadena, respondiendo tu pregunta
• La versión de 64 bits del bucle se realiza de forma diferente, se desenrolla a mano por 2. Tenga en cuenta que termina temprano en un cero incrustado, por lo que no mira todos los caracteres. De lo contrario, muy poco común. Es bastante extraño, solo puedo adivinar que esto tiene algo que ver con que las cadenas sean potencialmente muy grandes. Pero no puedo pensar en un ejemplo práctico
• El código de depuración al final asegura que ningún código en el marco toma una dependencia en el código hash reproducible entre ejecuciones.
• El algoritmo hash es bastante estándar. El valor 1566083941 es un número mágico, un primo que es común en un tornado de Mersenne .