Как реализуется GetHashCode() строки C#?


Мне просто любопытно, потому что я думаю, это будет иметь влияние на производительность. Учитывает ли он полную строку? Если да, то это будет медленно на длинной струне. Если он рассматривает только часть строки, он будет иметь плохую производительность (например, если он рассматривает только начало строки, он будет иметь плохую производительность, если хэш-Набор содержит в основном строки с тем же самым.

2   51   2013-03-02 16:29:04

2 ответа:

будьте уверены, чтобы получить источник ссылки исходный код когда у вас есть подобные вопросы. Там гораздо больше, чем то, что вы можете увидеть из декомпилятора. Выберите тот, который соответствует вашей предпочтительной цели .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] == '', "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() для создания хэшей для таких вещей, как пароли или шифрование. Он включен с помощью запись в приложение.исполняемый.конфигурационный файл
  • The основные оператор сохраняет индексирование строки дешево, избегает проверки границ, выполняемой обычным индексатором
  • первое утверждение гарантирует, что строка нулевое завершение, как и должно быть, требуется, чтобы разрешить оптимизацию в цикле
  • второе утверждение гарантирует, что строка выровнена по адресу, который кратен 4, как и должно быть, требуется, чтобы сохранить цикл performant
  • цикл разворачивается вручную, потребляя 4 символа на цикл для 32-разрядной версии. Приведение к int* - это трюк для хранения 2 символов (2 x 16 бит) в int (32-бит). Дополнительные операторы после цикла имеют дело со строкой, длина которой равна не кратно 4. Обратите внимание, что нулевой Терминатор может или не может быть включен в хэш, его не будет, если длина четная. Он смотрит на все символы в строке, отвечая на ваш вопрос
  • 64-разрядная версия цикла выполняется по-разному, вручную развернутая на 2. Обратите внимание, что он заканчивается рано на встроенном нуле, поэтому не смотрит на все символы. В остальном очень необычно. Это довольно странно, я могу только догадываться, что это как-то связано с строки потенциально очень большие. Но не могу придумать практического примера
  • код отладки в конце гарантирует, что ни один код в рамках никогда не принимает зависимость от хэш-кода, воспроизводимого между запусками.
  • хэш-алгоритм довольно стандартный. Значение 1566083941-это магическое число, простое число, которое является общим в Мерсенн твистер.

изучение исходного кода (любезно 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;
}