如何從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; 
}