c# - 如何改进短字符串的散列以避免冲突？

Question

我在 .NET4 中使用短字符串时遇到哈希冲突问题。
编辑:我在 .NET 中使用内置字符串哈希函数。

我正在使用像这样存储转换方向的对象来实现缓存

public class MyClass
{
    private string _from;
    private string _to;

   // More code here....

    public MyClass(string from, string to)
    {
        this._from = from;
        this._to = to;
    }

    public override int GetHashCode()
    {
        return string.Concat(this._from, this._to).GetHashCode();
    }

    public bool Equals(MyClass other)
    {
        return this.To == other.To && this.From == other.From;
    }

    public override bool Equals(object obj)
    {
        if (obj == null) return false;
        if (this.GetType() != obj.GetType()) return false;
        return Equals(obj as MyClass);
    }
}

这是方向相关的，from 和 to 由短字符串表示，例如“AAB”和“ABA”。

我遇到了与这些小字符串的稀疏散列冲突，我尝试了一些简单的方法，比如添加盐(没有用)。

问题 是我的太多小字符串如“AABABA”与“ABAAAB”的反向哈希冲突(请注意，这些不是真实的例子，我不知道 AAB 和ABA 实际上会导致碰撞!)

我已经完成了重任务，比如实现 MD5(有效，但速度慢得多)

我在这里也实现了 Jon Skeet 的建议:
Should I use a concatenation of my string fields as a hash code? 这行得通，但我不知道它对我的各种 3 字符字符串有多可靠。

如何在不像 MD5 那样增加太多开销的情况下改进和稳定小字符串的散列？

编辑: 作为对发布的一些答案的回应...缓存是使用从 MyClass 键控的并发字典实现的，如上所示。如果我将上面代码中的 GetHashCode 替换为我发布的链接中的 @JonSkeet 代码之类的简单代码:

int hash = 17;
hash = hash * 23 + this._from.GetHashCode();
hash = hash * 23 + this._to.GetHashCode();        
return hash;

一切都按预期运行。 还值得注意的是，在此特定用例中，缓存未在多线程环境中使用，因此不存在竞争条件。

编辑:我还应该注意，这种不当行为取决于平台。它在我完全更新的 Win7x64 机器上按预期工作，但在未更新的 Win7x64 机器上运行不正常。我不知道缺少哪些更新的扩展，但我知道它没有 Win7 SP1...所以我假设可能还有一个框架 SP 或更新它也丢失了。

编辑:正如所暗示的那样，我的问题不是由散列函数问题引起的。我有一个难以捉摸的竞争条件，这就是为什么它在某些计算机上工作而不在其他计算机上工作的原因，也是为什么“较慢”的散列方法使事情正常进行的原因。我选择的答案最有助于理解为什么我的问题不是字典中的哈希冲突。

Answer 1

您确定是碰撞引起的问题吗？当你说

I finally discovered what was causing this bug

您的意思是您的代码运行缓慢或其他原因？如果不是，我很好奇那是什么问题？因为任何哈希函数(有限域上的“完美”哈希函数除外)都会导致冲突。

我放置了一段快速代码来检查 3 个字母的单词是否存在冲突。而且这段代码不会为他们报告一次碰撞。你明白我的意思吗？看起来内置的哈希算法还不错。

Dictionary<int, bool> set = new Dictionary<int, bool>();
char[] buffer = new char[3];
int count = 0;
for (int c1 = (int)'A'; c1 <= (int)'z'; c1++)
{
    buffer[0] = (char)c1;
    for (int c2 = (int)'A'; c2 <= (int)'z'; c2++)
    {
        buffer[1] = (char)c2;
        for (int c3 = (int)'A'; c3 <= (int)'z'; c3++)
        {
            buffer[2] = (char)c3;
            string str = new string(buffer);
            count++;
            int hash = str.GetHashCode();
            if (set.ContainsKey(hash))
            {
                Console.WriteLine("Collision for {0}", str);
            }
            set[hash] = false;
        }
    }
}

Console.WriteLine("Generated {0} of {1} hashes", set.Count, count);

虽然您可以选择几乎所有众所周知的哈希函数(如 David 提到的)，甚至可以选择“完美”哈希，因为看起来您的域是有限的(例如最小完美哈希)...了解问题的根源是否真的是碰撞。

更新

我想说的是，.NET 内置的字符串哈希函数还不错。它不会产生太多冲突，以至于您需要在常规场景中编写自己的算法。这不取决于字符串的长度。如果您有很多 6 个符号的字符串，这并不意味着您看到碰撞的机会比 1000 个符号的字符串高。这是哈希函数的基本属性之一。

再一次，另一个问题是您因碰撞而遇到什么样的问题？所有内置哈希表和字典都支持冲突解决。所以我想说你所能看到的只是......可能有些缓慢。这是你的问题吗？

至于你的代码

return string.Concat(this._from, this._to).GetHashCode(); 

这可能会导致问题。因为在每次哈希码计算中，您都会创建一个新字符串。也许这就是导致您出现问题的原因？

int hash = 17; 
hash = hash * 23 + this._from.GetHashCode(); 
hash = hash * 23 + this._to.GetHashCode();         
return hash; 

这会是更好的方法——只是因为您没有在堆上创建新对象。实际上，这是这种方法的要点之一——在不创建新对象的情况下获得具有复杂“键”的对象的良好哈希码。因此，如果您没有单值键，那么这应该适合您。顺便说一句，这不是新的哈希函数，这只是一种在不损害哈希函数主要属性的情况下组合现有哈希值的方法。