一个适用于C#字符串的快速哈希函数

Question

我想对一个长度最多为30的字符串进行哈希计算。如果时间是我的主要考虑因素，应该采取什么样的最佳方案？该函数将被调用100多万次。目前我正在使用以下代码：

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

- P basak

---

Object.GetHashCode() 方法为什么不能使用？你好像要重新实现同样的概念。 - Ken Wayne VanderLinde

不使用浮点数运算的任何内容都会更快。 - David Schwartz

@Pbasak 然后将其转换为 uint 或使用 0x7FFFFF 进行掩码处理。 - CodesInChaos

运行分析器，它会告诉你哪一部分运行缓慢。然后修复这个慢的部分。 - Eric Lippert

该主题的分析非常出色：http://programmers.stackexchange.com/questions/49550/which-hashing-algorithm-is-best-for-uniqueness-and-speed - tozevv

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。

- David Schwartz

---

根据我的测试，这个函数没有达到雪崩效应。你的结果可能会有所不同。 - Fantius

更糟糕了。但我应该量化一下我的原始陈述。在使用您提供的常数时，切换输入中的一个比特会导致约49.40％的输出比特切换，这比基于Bernstein的函数要好得多。这对于大多数用途可能已经足够了。但是，例如，SuperFastHash（http://landman-code.blogspot.com/2009/02/c-superfasthash-and-murmurhash2.html）给我50.02％。而同一页上的Murmur2则给我50.04％。 - Fantius

这并不适用于你关心的应用场景，只是旨在用于在哈希表中分发字符串。 - David Schwartz

请问您能提供该算法的引用吗？我在《计算机程序设计艺术》卷3中搜索，但找不到您提到的这些常数。 - Shital Shah

@ShitalShah 我相当确定这是TAOCP中的内容，但我不确定是哪一卷。 - David Schwartz

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。

- CodesInChaos

---

乘数必须从大于256的质数值开始，否则如果第一个字节很小，这将会严重破坏程序。 - David Schwartz

@DavidSchwartz 更大的质数当然更好，但是彻底崩溃有点言过其实。 - CodesInChaos

如果一个64位哈希函数有许多2字节输入发生碰撞，我认为它会出现严重问题。（但考虑到OP最初使用的函数有多么糟糕，也许我的标准太高了。） - David Schwartz

即使素数 >256 但 <65536，仍会出现两个字符冲突。C# 使用 UTF-16 代码点而不是单字节字符。 - CodesInChaos

提醒所有使用.NET Core的人：在.NET Core中，GetHashCode在应用程序重新启动时是随机的！这意味着每次应用程序重新启动/回收时，您都会得到相同字符串的不同哈希值。 - Alex from Jitbit

Answer 3

为了加快实现速度，应该用查找替换(UInt64)Math.Pow(31, i)调用：预先计算出前30个31的幂的表格，并在运行时使用它。由于长度限制为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];

- Sergey Kalinichenko

---

我并不确定查表比整数乘法更快。 - CodesInChaos

@CodeInChaos 这肯定比 Math.Pow(31, i) 更快。而且当 i 在条件中增加2时，我需要进行额外的乘法，所以我会先尝试查找。 - Sergey Kalinichenko