如何从C＃中的字节数组生成哈希码？

Question

说我有一个对象，存储一个字节数组，我希望能够有效地为它生成一个哈希码。我过去使用过密码散列函数，因为它们很容易实现，但是它们做的工作要比单纯使用密码技术要多得多，我不在乎这一点（我只是在使用散列码作为散列表中的关键字）。

这里就是我今天有：

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中的支票，我已经更新了它。使用字节数组中现有的散列码将导致引用相等（或至少将相同的概念转换为散列码）。 例如：

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

与该代码，尽管有在其中相同的值的两个字节数组，它们指的是存储器的不同部分，并且将导致在（可能）不同的散列码。我需要相同内容的两个字节数组的哈希码相等。

Answer 1

如果您正在寻找性能，我测试了几个哈希键，并且我推荐。这是疯狂的快速 来计算，并会给你尽可能少的碰撞作为密码 哈希你使用到现在为止。

我根本不知道C＃，我不知道它是否可以与C链接，但是 这里是its implementation in C。

Answer 2

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

的检查规则是：

• 是哈希码等于？然后调用完整（慢）Equals方法。
• 散列码不相等吗？那么这两个项目绝对不是平等的。

所有你想要的是一个GetHashCode算法您的收藏分裂成大致相抵群体 - 它不应成为重点为HashTable或Dictionary<>需要使用哈希来优化检索。

你期望数据有多长？如何随机？如果长度差别很大（例如对于文件），那么只需返回长度。如果长度可能相似，则查看变化的字节子集。

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

两个相同的东西绝不能有不同的哈希码。两个不同的对象不应该有具有相同的散列码，但预计会发生一些冲突（毕竟，排列次数多于可能的32位整数）。

Answer 3

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

Answer 4

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

我学过的最简单的散列就是将所有字节异或。这很容易，比大多数复杂的散列算法更快，并且对于小数据集来说也是一个中等体积的通用散列算法。这是真正的泡泡排序算法。由于简单的实现会留下8位，这只是256哈希......不是太热。你可以XOR块而不是单个字节，但是然后算法变得更加复杂。

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

因此，直到我看到一些不使用罐头哈希算法的原因（性能，也许？），我将不得不建议你坚持你有什么。

Answer 5

与SHA1CryptoServiceProvider.ComputeHash方法比较过吗？它需要一个字节数组并返回一个SHA1哈希，我相信它已经很好的优化了。我在Identicon Handler中使用它，在负载下表现相当好。

Answer 6

RuntimeHelpers.GetHashCode可能有帮助：

从MSDN：

用作哈希函数。 特定类型的，适于用在 散列算法和数据结构 诸如哈希表。

Answer 7

无论你想要一个完美的散列函数（不同的计算结果等于每个对象的值），或只是一个相当不错的始终是一个性能权衡，一般需要时间来计算一个良好的散列函数，如果你的数据集是短小你更擅长使用快速功能。最重要的（正如你的第二篇文章所指出的）是正确的，并且实现你所需要的就是返回数组的长度。取决于你甚至可以确定的数据集。如果不是（说你的所有阵列都是同样长的话），你可以使用一些便宜的东西，比如查看第一个和最后一个值，并对它们的值进行异或，然后在你认为适合你的数据时增加更多的复杂性。

查看散列函数对数据的执行方式的一个快速方法是将所有数据添加到散列表并计算Equals函数被调用的次数，如果它太频繁您需要做更多工作功能。如果你这样做，只要记住哈希表的大小需要在启动时设置得比数据集大，否则你将重新哈希数据，这将触发重新插入和更多的等值评估（尽管可能更现实？）

对于某些对象（不是这个），可以通过ToString（）生成一个快速的HashCode。GetHashCode（）方法，肯定不是最佳的，但随着人们有用倾向于返回了接近从的ToString（对象的身份），而这正是GetHashCode的是寻找

花絮：我所见过的最糟糕的表现当有人错误地返回从GetHashCode的恒定，易与调试器，虽然发现，特别是如果你做大量的查找在由JetBrains公司软件生成的代码的哈希表

Answer 8

借款，我已经看中了这个功能：

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

只是XOring字节的问题是第3/4（3字节） e返回的值只有2个可能的值（全部关闭或全部关闭）。这扩大了一点点。

在Equals中设置断点是一个很好的建议。将大约200,000条数据添加到字典中，可以看到大约10个Equals调用（或1/20,000）。

Answer 9

不要使用哈希表的加密散列，这是荒谬的/矫枉过正。

这里亚去...修改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; 
     } 
    } 

Answer 10

我发现有趣的结果：

我有类：

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

然后我使用MyHash类型的键创建一个字典，以测试我可以多快我也可以知道有多少碰撞。我做了以下内容

 // 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(); 

每次我向词典插入一个新项目时，词典都会计算该对象的散列值。所以，你能告诉什么方法是最有效的通过将在这里找到的方法public override int GetHashCode()的方法，这是目前为止最快的几个答案，不得不碰撞数最少的是：

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秒钟执行！

Answer 11

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