Una función hash rápida para una cadena en C#

Question

Quiero cortar una cadena de longitud de hasta 30. Cuál será la mejor idea para hacer eso si el tiempo es mi problema. La función se llamará más de 100 millones de veces. Actualmente estoy usando el siguiente código,

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

Este es un hash Knuth. También puede usar Jenkins.

Answer 2

He jugado con implementaciones de Paul Hsieh, y parecen ser rápido con pequeñas colisiones (por mis escenarios de todos modos)

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

Answer 3

Para acelerar su implementación, la llamada (UInt64)Math.Pow(31, i) debe reemplazarse por una búsqueda: precalcular una tabla de las primeras 30 potencias de 31, y usarla en tiempo de ejecución. Dado que el límite de la longitud es de 30, lo que necesita sólo el 31 elemento:

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

Antes que nada, considere usar GetHashCode().

Una simple mejora en su aplicación existente:

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 el cálculo de coma flotante caro, y la sobrecarga de ElementAt.

Btw (UInt64)Math.Pow(31, i) no funciona bien para cadenas más largas. El redondeo de punto flotante conducirá a un multiplicador de 0 para caracteres más allá de 15 o más.