C#中字符串的快速哈希函数

Question

我想要将长度最多为30的字符串哈希.如果时间紧迫,那么最好的做法是什么.该功能将被调用超过1亿次.目前我使用以下代码,

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

这是一个Knuth哈希.你也可以使用Jenkins.

Answer 2

首先,考虑使用GetHashCode().

对现有实施的简单改进:

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

它避免了昂贵的浮点计算和开销ElementAt.

顺便说一下(UInt64)Math.Pow(31, i),对于较长的琴弦不适用.对于超过15左右的字符,浮点舍入将导致乘数为0.