制作多个字符串哈希键的最快方法

Question

历史为什么很长，但问题很简单。有 3 个字符串，我需要缓存匹配值。为了获得快速缓存，我使用以下代码：

public int keygen(string a, string b, string c)
    {
        var x = a + "@@" + b + "@@" + c;
        var hash = x.GetHashCode();
        return hash;
    }

（注意字符串a、b、c不包含代码"@@"）它本身的缓存只是一个Dictionary<int, object>

我知道哈希键可能存在非唯一性的风险，但除此之外：

有谁知道制作 int 键的更快方法？（在 C# 中）此操作占用 ~15% 的总 CPU 时间，这是一个长时间运行的应用程序。

我已经尝试了几种实现，但未能找到更快的实现。

Answer 1

你应该使用Dictionary<Tuple<string,string,string>, object> .然后，您不必担心非唯一性，因为字典会为您处理它。

Answer 2

与其连接字符串（这会创建新字符串），不如使用XOR甚至更好的简单数学运算（归功于 J.Skeet）：

public int keygen(string a, string b, string c)
{
    unchecked // Overflow is fine, just wrap
    {
        int hash = 17;
        hash = hash * 23 + a == null ? 0 : a.GetHashCode();
        hash = hash * 23 + b == null ? 0 : b.GetHashCode();
        hash = hash * 23 + c == null ? 0 : c.GetHashCode();
        return hash;
    }
}

通常，没有必要生成唯一的哈希值。但是您应该尽量减少碰撞。

另一种（效率不高）方法是使用具有内置GetHashCode支持的匿名类型：

public int keygen(string a, string b, string c)
{
    return new { a, b, c }.GetHashCode();
}

请注意，名称、类型和顺序对于匿名类型的哈希码的计算很重要。

Answer 3

更快的方法是单独计算每个字符串的哈希值，然后使用哈希函数将它们组合在一起。这将消除可能需要时间的字符串连接。

例如

public int KeyGen(string a, string b, string c)
{
    var aHash = a.GetHashCode();
    var bHash = b.GetHashCode();
    var cHash = c.GetHashCode();
    var hash = 36469;
    unchecked
    {
        hash = hash * 17 + aHash;
        hash = hash * 17 + bHash;
        hash = hash * 17 + cHash;
    }
    return hash;
}

Answer 4

我知道存在哈希键可能非唯一的风险

哈希键不一定是唯一的 - 如果冲突最小化，它们会更好地工作。

也就是说，你花在计算字符串哈希代码上的 15% 的时间似乎非常高。 即使切换到string.Concat()（编译器无论如何都会为你做）或StringBuilder也不应该有太大区别。 我建议对你的测量进行三重检查。

Answer 5

我猜这个函数的大部分时间都花在构建连接的字符串上，只是为了调用GetHashCode。我会尝试类似的东西

public int keygen(string a, string b, string c)
{
    return a.GetHashCode() ^ b.GetHashCode() ^ c.GetHashCode();
}

或者可能使用比简单异或更复杂的东西。但是，请注意，GetHashCode不是加密哈希函数！它是一个用于哈希表的哈希函数，而不是用于密码学，您绝对不应该将其用于任何与安全相关的内容，例如密钥（如您的keygen名称提示）。