如何从C#中的字节数组生成哈希码?

说我有一个对象,存储一个字节数组,我想能够有效地生成它的哈希码。 在过去,我使用了密码散列函数,因为它们很容易实现,但是它们做的工作要比单独使用密码方法要多得多,而且我不在乎(我只是在使用散列码作为散列表中的关键字)。

这是我今天的事情:

struct SomeData : IEquatable<SomeData> { private readonly byte[] data; public SomeData(byte[] data) { if (null == data || data.Length <= 0) { throw new ArgumentException("data"); } this.data = new byte[data.Length]; Array.Copy(data, this.data, data.Length); } public override bool Equals(object obj) { return obj is SomeData && Equals((SomeData)obj); } public bool Equals(SomeData other) { if (other.data.Length != data.Length) { return false; } for (int i = 0; i < data.Length; ++i) { if (data[i] != other.data[i]) { return false; } } return true; } public override int GetHashCode() { return BitConverter.ToInt32(new MD5CryptoServiceProvider().ComputeHash(data), 0); } } 

有什么想法吗?


dp:你是对的,我错过了Equals的支票,我已经更新了。 使用字节数组中现有的散列码将导致引用相等(或至less将相同的概念转换为散列码)。 例如:

 byte[] b1 = new byte[] { 1 }; byte[] b2 = new byte[] { 1 }; int h1 = b1.GetHashCode(); int h2 = b2.GetHashCode(); 

有了这些代码,尽pipe两个字节数组在内部具有相同的值,但它们指的是内存的不同部分,并且会导致(可能)不同的哈希码。 我需要相同内容的两个字节数组的哈希码相等。

对象的哈希码不需要是唯一的。

检查规则是:

  • 散列码是否相等? 然后调用完整(慢) Equals方法。
  • 散列码不相等吗? 那么这两个项目绝对不是平等的。

所有你想要的是一个GetHashCodealgorithm,它将你的集合分成几乎平均的组 – 它不应该形成关键,因为HashTableDictionary<>需要使用哈希来优化检索。

你期望数据有多久? 如何随机? 如果长度差别很大(比如说文件),那么就返回长度。 如果长度可能相似,则查看变化的字节的子集。

GetHashCode应该比Equals快很多,但并不需要是唯一的。

两个相同的东西不能有不同的哈希码。 两个不同的对象不应该具有相同的哈希码,但是可能会发生一些冲突(毕竟,比32位整数有更多的排列)。

不要使用哈希表的哈希表,这是荒谬的/矫枉过正。

在这里你去…修改FNV哈希在C#

http://bretm.home.comcast.net/hash/6.html

  public static int ComputeHash(params byte[] data) { unchecked { const int p = 16777619; int hash = (int)2166136261; for (int i = 0; i < data.Length; i++) hash = (hash ^ data[i]) * p; hash += hash << 13; hash ^= hash >> 7; hash += hash << 3; hash ^= hash >> 17; hash += hash << 5; return hash; } } 

从JetBrains软件生成的代码借用,我已经解决了这个function:

  public override int GetHashCode() { unchecked { var result = 0; foreach (byte b in _key) result = (result*31) ^ b; return result; } } 

只有XOring字节的问题是返回值的3/4(3字节)只有2个可能的值(全部closures或全部closures)。 这扩大了一点点。

在Equals中设置一个断点是一个很好的build议。 将约20万条数据添加到字典中,可以看到大约10个等号(或1 / 20,000)。

你有没有比较SHA1CryptoServiceProvider.ComputeHash方法? 它需要一个字节数组并返回一个SHA1哈希,我相信它已经很好的优化了。 我在一个Identicon Handler中使用它,在负载下performance相当好。

我发现有趣的结果:

我有class:

 public class MyHash : IEquatable<MyHash> { public byte[] Val { get; private set; } public MyHash(byte[] val) { Val = val; } /// <summary> /// Test if this Class is equal to another class /// </summary> /// <param name="other"></param> /// <returns></returns> public bool Equals(MyHash other) { if (other.Val.Length == this.Val.Length) { for (var i = 0; i < this.Val.Length; i++) { if (other.Val[i] != this.Val[i]) { return false; } } return true; } else { return false; } } public override int GetHashCode() { var str = Convert.ToBase64String(Val); return str.GetHashCode(); } } 

然后,我创build了一个MyHashtypes的键字典,以testing我可以插入多快,我也可以知道有多less碰撞。 我做了以下

  // dictionary we use to check for collisions Dictionary<MyHash, bool> checkForDuplicatesDic = new Dictionary<MyHash, bool>(); // used to generate random arrays Random rand = new Random(); var now = DateTime.Now; for (var j = 0; j < 100; j++) { for (var i = 0; i < 5000; i++) { // create new array and populate it with random bytes byte[] randBytes = new byte[byte.MaxValue]; rand.NextBytes(randBytes); MyHash h = new MyHash(randBytes); if (checkForDuplicatesDic.ContainsKey(h)) { Console.WriteLine("Duplicate"); } else { checkForDuplicatesDic[h] = true; } } Console.WriteLine(j); checkForDuplicatesDic.Clear(); // clear dictionary every 5000 iterations } var elapsed = DateTime.Now - now; Console.Read(); 

每次我向词典中插入一个新的项目时,词典都会计算这个对象的散列值。 所以你可以通过在方法中find几个答案来告诉哪种方法是最有效的public override int GetHashCode()这个方法是迄今为止最快,碰撞次数最less的是:

  public override int GetHashCode() { var str = Convert.ToBase64String(Val); return str.GetHashCode(); } 

花了2秒钟执行。 方法

  public override int GetHashCode() { // 7.1 seconds unchecked { const int p = 16777619; int hash = (int)2166136261; for (int i = 0; i < Val.Length; i++) hash = (hash ^ Val[i]) * p; hash += hash << 13; hash ^= hash >> 7; hash += hash << 3; hash ^= hash >> 17; hash += hash << 5; return hash; } } 

也没有碰撞,但它需要7秒钟执行!

是否使用字节数组字段中的现有哈希码不够好? 另外请注意,在Equals方法中,您应该在比较之前检查数组是否大小相同。

生成一个好的散列说起来容易做起来难。 记住,你基本上用m位信息表示n个字节的数据。 数据集越大,m越小,碰撞的可能性就越大。两个数据parsing为相同的散列值。

我学到的最简单的散列就是将所有的字节异或。 它比大多数复杂的散列algorithm更容易,速度更快,而对于小数据集来说,它是一个中等体积的通用散列algorithm。 这是真正的泡泡sortingalgorithm。 由于简单的实现会留下8位,这只是256哈希…不那么热。 你可以XOR块,而不是单个字节,但是然后algorithm变得更加复杂。

所以当然,密码algorithm可能会做一些你不需要的东西,但是它们也是通用哈希质量的一个巨大的进步。 你使用的MD5哈希值有128位,有数十亿和数十亿可能的哈希值。 唯一可能的方法是获取一些有代表性的数据样本,然后尝试使用各种algorithm来查看您获得的碰撞数量。

所以,直到我看到一些不使用jar头哈希algorithm(性能,也许?)的理由,我将不得不build议你坚持你有什么。

无论你想要一个完美的散列函数(对于每个对象的不同值,评估结果是相等的),还是相当不错的散列函数总是一个性能折衷,计算一个好的散列函数通常需要时间,如果你的数据集很小,你最好用一个快速的function。 最重要的(正如你的第二篇文章指出的)是正确的,并且实现你所需要的就是返回数组的长度。 取决于你的数据集,甚至可能是好的。 如果不是(比如说所有的数组都是同样长的),那么可以使用一些便宜的方法,比如查看第一个和最后一个值,并对它们的值进行异或运算,然后增加更复杂的数据。

查看hash函数对数据执行操作的一个快速方法是将所有数据添加到散列表中,并计算Equals函数被调用的次数,如果太频繁您需要做更多的工作。 如果你这样做,只要记住哈希表的大小需要设置大于你的数据集,否则你将重新刷新数据,这将触发重新插入和更多的等值评估(尽pipe可能更现实?)

对于一些对象(不是这个),一个快速的HashCode可以由ToString()。GetHashCode()生成,当然不是最优的,但是有用,因为人们倾向于从ToString()返回接近对象身份的东西, GetHashcode正在寻找什么

琐事:我见过的最糟糕的performance是,有人误从GetHashCode返回了一个常量,但很容易find一个debugging器,特别是如果你在你的哈希表中做了很多的查找

如果你正在寻找性能,我testing了一些哈希键,我推荐Bob Jenkin的哈希函数 。 计算速度非常快,并且与迄今为止使用的encryption散列一样,只会产生很less的冲突。

我根本不知道C#,我不知道它是否可以与C链接,但这里是它在C中的实现 。

 private int? hashCode; public override int GetHashCode() { if (!hashCode.HasValue) { var hash = 0; for (var i = 0; i < bytes.Length; i++) { hash = (hash << 4) + bytes[i]; } hashCode = hash; } return hashCode.Value; } 

RuntimeHelpers.GetHashCode可能有所帮助:

从Msdn:

用作特定types的散列函数,适用于散列algorithm和数据结构(如散列表)。