Una funzione di hash veloce per la stringa in C#

Question

Voglio hash una stringa di lunghezza fino a 30. Quale sarà l'idea migliore per farlo se il tempo è la mia preoccupazione. La funzione verrà chiamata oltre 100 milioni di volte. Attualmente sto usando il seguente codice,

static UInt64 CalculateHash(string read, bool lowTolerance) 
{ 
    UInt64 hashedValue = 0; 
    int i = 0; 
    while (i < read.Length) 
    { 
     hashedValue += read.ElementAt(i) * (UInt64)Math.Pow(31, i); 
     if (lowTolerance) i += 2; 
     else i++; 
    } 
    return hashedValue; 
} 

Answer 1

static UInt64 CalculateHash(string read) 
{ 
    UInt64 hashedValue = 3074457345618258791ul; 
    for(int i=0; i<read.Length; i++) 
    { 
     hashedValue += read[i]; 
     hashedValue *= 3074457345618258799ul; 
    } 
    return hashedValue; 
} 

Questo è un hash Knuth. Puoi anche usare Jenkins.

Answer 2

Ho giocato con le implementazioni di Paul Hsieh, e sembrano essere veloce con piccole collisioni (per i miei scenari in ogni caso)

• http://www.azillionmonkeys.com/qed/hash.html

Answer 3

Per accelerare l'implementazione, la chiamata (UInt64)Math.Pow(31, i) deve essere sostituita da una ricerca: calcola una tabella delle prime 30 potenze di 31 e utilizzala in fase di runtime. Dal momento che il limite di lunghezza è di 30, è necessario solo 31 elementi:

private static unsigned long[] Pow31 = new unsigned long[31]; 

static HashCalc() { 
    Pow31[0] = 1; 
    for (int i = 1 ; i != Pow31.Length ; i++) { 
     Pow31[i] = 31*Pow31[i-1]; 
    } 
} 

// In your hash function... 
hashedValue += read.ElementAt(i) * Pow31[i]; 

Answer 4

Prima di tutto, considerare l'utilizzo di GetHashCode().

Un semplice miglioramento dell'implementazione esistente:

static UInt64 CalculateHash(string read, bool lowTolerance) 
{ 
    UInt64 hashedValue = 0; 
    int i = 0; 
    ulong multiplier = 1; 
    while (i < read.Length) 
    { 
     hashedValue += read[i] * multiplier; 
     multiplier *= 37; 
     if (lowTolerance) i += 2; 
     else i++; 
    } 
    return hashedValue; 
} 

Evita il costoso calcolo in virgola mobile, e l'overhead di ElementAt.

Btw (UInt64)Math.Pow(31, i) non funziona bene per stringhe più lunghe. L'arrotondamento a virgola mobile porterà a un moltiplicatore di 0 per i caratteri oltre i 15 circa.