Como é GetHashCode () de C # string implementada?

Estou apenas curioso porque acho que isso terá impacto no desempenho. Considera a corda cheia? Se sim, será lento em uma longa string. Se considerar apenas parte da string, ela terá um desempenho ruim (por exemplo, se considerar apenas o início da string, ela terá um desempenho ruim se um HashSet contiver principalmente strings com o mesmo.

Certifique-se de obter o código-fonte da Origem de Referência quando tiver perguntas como essa. Há muito mais do que você pode ver de um descompilador. Escolha o que corresponde ao seu destino .NET preferido, o método mudou muito entre as versões. Vou apenas reproduzir a versão do .NET 4.5 aqui, recuperada do 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); } } } 

Isso é possivelmente mais do que você esperava, vou anotar o código um pouco:

  • As directivas de compilation condicional #if adaptam este código a diferentes alvos .NET. Os identificadores FEATURE_XX são definidos em outro lugar e desativam resources em todo o código-fonte .NET. O WIN32 é definido quando o destino é a versão de 32 bits da estrutura, a versão de 64 bits do mscorlib.dll é criada separadamente e armazenada em um subdiretório diferente do GAC.
  • A variável s_UseRandomizedStringHashing habilita uma versão segura do algoritmo hash, projetado para manter os programadores longe de problemas que fazem algo imprudente como usar GetHashCode () para gerar hashes para coisas como senhas ou criptografia. É ativado por uma input no arquivo app.exe.config
  • A instrução fixa mantém a indexação da string barata, evita a verificação de limites feita pelo indexador regular
  • A primeira Assert garante que a string seja terminada em zero como deveria, necessária para permitir a otimização no loop
  • A segunda Assert garante que a string esteja alinhada a um endereço que seja múltiplo de 4, como deveria ser, necessário para manter o desempenho do loop
  • O loop é desenrolado manualmente, consumindo 4 caracteres por loop para a versão de 32 bits. O cast para int * é um truque para armazenar 2 caracteres (2 x 16 bits) em um int (32 bits). As instruções extras após o loop lidam com uma string cujo comprimento não é múltiplo de 4. Note que o terminador zero pode ou não ser incluído no hash, não será se o comprimento for par. Ele olha para todos os caracteres da string, respondendo sua pergunta
  • A versão de 64 bits do loop é feita de forma diferente, desenrolada à mão por 2. Observe que ela termina no início de um zero incorporado, portanto, não examina todos os caracteres. Caso contrário, muito incomum. Isso é muito estranho, eu só posso imaginar que isso tem algo a ver com seqüências de caracteres potencialmente muito grandes. Mas não consigo pensar em um exemplo prático
  • O código de debugging no final garante que nenhum código na estrutura dependa do código hash ser reproduzível entre as execuções.
  • O algoritmo de hash é bastante normal. O valor 1566083941 é um número mágico, um primo que é comum em um twister Mersenne .

Examinando o código fonte (cortesia do ILSpy ), podemos ver que ele faz iteração ao longo do comprimento da string.

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