Как реализована функция GetHashCode() из строки С#?

Ответ 1

Обязательно получите Исходный код исходного кода, если у вас есть такие вопросы. Там гораздо больше, чем то, что вы можете видеть из декомпилятора. Выберите тот, который соответствует вашей предпочитаемой .NET-цели, этот метод сильно изменился между версиями. Я просто воспроизведу его версию .NET 4.5, извлеченную из 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);
                }
            } 
        }

Возможно, это больше, чем вы рассчитывали, я немного добавлю код:

• Директивы условной компиляции #if адаптируют этот код к различным объектам .NET. Идентификаторы FEATURE_XX определены в другом месте и полностью отключены от всей продажи в исходном коде .NET. WIN32 определяется, когда целью является 32-разрядная версия фреймворка, 64-разрядная версия mscorlib.dll создается отдельно и хранится в другом подкаталоге GAC.
• Переменная s_UseRandomizedStringHashing включает безопасную версию алгоритма хэширования, предназначенную для предотвращения ошибок программистов, которые делают что-то неразумно, как использование GetHashCode() для генерации хэшей для таких вещей, как пароли или шифрование. Включено запись в файле app.exe.config
• Фиксированный оператор продолжает индексировать строку дешево, избегает проверки границ, выполняемой обычным индексом
• Первое Assert гарантирует, что строка заканчивается нулем, как и должно быть, чтобы разрешить оптимизацию в цикле
• Второй Assert гарантирует, что строка будет выровнена с адресом, который должен быть кратным 4, как это должно быть, чтобы сохранить выполнение цикла
• Цикл разворачивается вручную, потребляя 4 символа за цикл для 32-разрядной версии. Приведение в int * - это трюк для хранения двух символов (2 x 16 бит) в int (32 бит). Дополнительные инструкции после цикла обрабатывают строку, длина которой не кратная 4. Обратите внимание, что нулевой терминатор может быть включен или не включен в хэш, он не будет, если длина четная. Он просматривает все символы в строке, отвечая на ваш вопрос.
• 64-битная версия цикла выполняется по-разному, ручная разворачивается на 2. Обратите внимание, что она заканчивается на ранней стадии встроенного нуля, поэтому не просматривается все символы. В противном случае очень необычно. Это довольно странно, я могу только догадываться, что это имеет какое-то отношение к строкам, которые могут быть очень большими. Но не может придумать практический пример.
• Код отладки в конце гарантирует, что никакой код в структуре никогда не будет зависеть от хеш-кода, воспроизводимого между прогонами.
• Хэш-алгоритм довольно стандартный. Значение 1566083941 - это магическое число, простое, которое распространено в Mersenne twister.

Ответ 2

Изучая исходный код (любезно предоставлен ILSpy), мы видим, что он выполняет итерацию по длине строки.

// 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;
}