Mat*_*hew 2 .net c# string hash collision
我在.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的建议:
我应该使用字符串字段的串联作为哈希码吗？
这有效,但我不知道我的各种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或更新它也缺失.
编辑:由于持续存在,我的问题不是由散列函数问题引起的.我有一个难以捉摸的竞争条件,这就是为什么它在一些计算机上工作但不在其他计算机上工作,以及为什么一个"慢"的哈希方法使事情正常工作.我选择的答案最有用的是理解为什么我的问题不是字典中的哈希冲突.
你确定碰撞是谁导致问题吗？当你说
我终于发现了导致这个bug的原因
你的意思是你的代码有些缓慢或其他什么？如果不是我很好奇那是什么问题？因为任何散列函数(有限域上的"完美"散列函数除外)都会导致冲突.
我快速编写了一段代码来检查3个字母单词的冲突.此代码不会为它们报告单个冲突.你明白我的意思吗？看起来像buid-in哈希算法并不是那么糟糕.
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);
虽然你可以选择几乎任何一个众所周知的哈希函数(如大卫提到的那样),或者甚至选择一个"完美"哈希,因为看起来你的域名是有限的(比如最小完美哈希)......如果能够理解它是很好的问题的根源是真正的碰撞.
更新
我想说的是,字符串的.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;
这将是更好的方法 - 只是因为您不在堆上创建新对象.实际上,这是这种方法的要点之一 - 使用复杂的"密钥"获取对象的良好哈希码,而无需创建新对象.因此,如果您没有单个值键,那么这应该适合您.顺便说一句,这不是一个新的哈希函数,这只是一种结合现有哈希值而不影响哈希函数主要属性的方法.