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

c# .net string hash gethashcode

29269 просмотра

2 ответа

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

Автор: Louis Rhys Источник Размещён: 12.11.2019 09:05

Ответы (2)


89 плюса

Решение

Обязательно получите исходный код Reference Source, когда у вас возникнут подобные вопросы. Это намного больше, чем то, что вы можете увидеть из декомпилятора. Выберите тот, который соответствует вашей предпочтительной цели .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
  • Оператор fixed держит индексацию строки дешево, избегает проверки границ, выполняемой обычным индексатором
  • Первый Assert гарантирует, что строка заканчивается нулем, как и должно быть, что необходимо для оптимизации в цикле
  • Второй Assert гарантирует, что строка выровнена по адресу, кратному 4, как и должно быть, что необходимо для поддержания цикла в рабочем состоянии.
  • Цикл развернут вручную, потребляя 4 символа на цикл для 32-разрядной версии. Приведение к int * - это прием для хранения 2 символов (2 x 16 бит) в int (32 бита). Дополнительные операторы после цикла имеют дело со строкой, длина которой не кратна 4. Обратите внимание, что нулевой терминатор может или не может быть включен в хеш, он не будет, если длина четна. Он смотрит на все символы в строке, отвечая на ваш вопрос
  • 64-битная версия цикла выполняется по-разному, вручную разворачивается на 2. Обратите внимание, что он рано заканчивается на встроенном нуле, поэтому не смотрит на все символы. В противном случае очень редко. Это довольно странно, я могу только догадываться, что это как-то связано со строками, которые могут быть очень большими. Но не могу придумать практический пример
  • Код отладки в конце гарантирует, что ни один код в платформе никогда не будет зависеть от хеш-кода, воспроизводимого между запусками.
  • Алгоритм хеширования довольно стандартный. Значение 1566083941 - это магическое число, простое число, которое часто встречается в твистере Мерсенна .
Автор: Hans Passant Размещён: 02.03.2013 04:10

6 плюса

Изучая исходный код (любезно предоставленный 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;
}
Автор: Ergwun Размещён: 02.03.2013 12:34
Вопросы из категории :
32x32