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

我想要将长度为60的字符串哈希。如果时间紧迫，那么最好的做法是什么。 该function将被调用超过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 

这是一个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。

Answer 3

为了加快实现速度，应该用查找替换(UInt64)Math.Pow(31, i)调用：预先计算31的前30个幂的表，并在运行时使用它。 由于长度限制为30，因此您只需要31个元素：

 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

我玩过Paul Hsieh的实现，并且看起来很快就会发生很少的碰撞（无论如何我的场景）

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