Come viene implementata GetHashCode() della stringa C#?

Question

Sono solo curioso perché suppongo che avrà un impatto sulle prestazioni. Considera la stringa completa? Se sì, sarà lento sulla corda lunga. Se considera solo parte della stringa, avrà delle cattive prestazioni (ad esempio se considererà solo l'inizio della stringa, avrà un rendimento negativo se un HashSet contiene principalmente stringhe con lo stesso

Answer 1

assicurarsi di ottenere il Reference Source source code quando si dispone di domande di questo tipo. C'è molto di più ad esso che quello che si può vedere da un decompilatore: scegli quello che corrisponde al tuo target .NET preferito, il metodo è cambiato molto tra le versioni, riprodurrò la versione .NET 4.5 qui, recuperato da 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); 
       } 
      } 
     } 

questo è forse più di quanto si aspettasse, io annotare il codice un po ':

• Le direttive di compilazione condizionale #if adattano questo codice a diversi obiettivi .NET. Gli identificativi FEATURE_XX sono definiti altrove e disattivano le funzionalità dell'intera vendita attraverso il codice sorgente .NET. WIN32 viene definito quando la destinazione è la versione a 32 bit del framework, la versione a 64 bit di mscorlib.dll viene creata separatamente e archiviata in una sottodirectory diversa del GAC.
• La variabile s_UseRandomizedStringHashing abilita una versione sicura dell'algoritmo di hash, progettata per tenere i programmatori fuori dai guai che fanno qualcosa di poco saggio come utilizzare GetHashCode() per generare hash per cose come password o crittografia. Si è attivato per an entry nel file App.exe.config
• Il fisso dichiarazione mantiene indicizzazione della stringa economico, evita i limiti checking fatta dal indicizzatore regolare
• La prima asserzione assicura che la stringa è zero-terminato come dovrebbe essere, richiesto per consentire l'ottimizzazione nel ciclo
• Il secondo Assert assicura che la stringa sia allineata a un indirizzo che è un multiplo di 4 come dovrebbe, richiesto per mantenere il loop performante
• Il ciclo è srotolato a mano, consumando 4 caratteri per loop per la versione a 32 bit. Il cast to int * è un trucco per memorizzare 2 caratteri (2 x 16 bit) in un int (32 bit). Le istruzioni extra dopo il ciclo trattano con una stringa la cui lunghezza non è un multiplo di 4. Si noti che il terminatore zero può o non può essere incluso nell'hash, non lo sarà se la lunghezza è pari. Guarda tutti i i caratteri nella stringa, rispondendo alla tua domanda
• La versione a 64 bit del ciclo viene eseguita in modo diverso, srotolata a mano da 2. Si noti che termina presto su uno zero incorporato, quindi non lo fa guarda tutti i personaggi Altrimenti molto insolito. È piuttosto strano, posso solo supporre che questo abbia qualcosa a che fare con le stringhe potenzialmente molto grandi. Ma non si può pensare ad un esempio pratico
• Il codice di debug alla fine assicura che nessun codice nel framework abbia mai una dipendenza dal codice hash riproducibile tra le esecuzioni.
• L'algoritmo di hash è piuttosto standard. Il valore 1566083941 è un numero magico, un numero primo comune in uno Mersenne twister.

Answer 2

Esaminando il codice sorgente (per gentile concessione di ILSpy), possiamo vedere che non iterare su tutta la lunghezza della stringa.

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