GetHashCode和Buckets

Question

我想更好地瞭解散列集的內部如何HashSet<T>做的工作，爲什麼他們表演。我發現了以下文章，用桶列表http://ericlippert.com/2011/02/28/guidelines-and-rules-for-gethashcode/實現了一個簡單的例子。據我瞭解這篇文章（我也認爲這種方式之前），桶列表本身分組在每個桶中的一定數量的元素。一個桶由散列碼錶示，即由元素上調用的GetHashCode表示。我認爲更好的表現是基於桶比元素少的事實。

現在我已經寫了以下幼稚的測試代碼：

public class CustomHashCode 
    { 
     public int Id { get; set; } 

     public override int GetHashCode() 
     { 
      //return Id.GetHashCode(); // Way better performance 
      return Id % 40; // Bad performance! But why? 
     } 


     public override bool Equals(object obj) 
     { 
      return ((CustomHashCode) obj).Id == Id; 
     } 

    } 

這裏探查：

public static void TestNoCustomHashCode(int iterations) 
    { 

     var hashSet = new HashSet<NoCustomHashCode>(); 
     for (int j = 0; j < iterations; j++) 
     { 
      hashSet.Add(new NoCustomHashCode() { Id = j }); 
     } 

     var chc = hashSet.First(); 
     var stopwatch = new Stopwatch(); 
     stopwatch.Start(); 
     for (int j = 0; j < iterations; j++) 
     { 
      hashSet.Contains(chc); 
     } 
     stopwatch.Stop(); 

     Console.WriteLine(string.Format("Elapsed time (ms): {0}", stopwatch.ElapsedMilliseconds)); 
    } 

我天真的想法是：讓我們降低桶的量（用一個簡單的模） ，這應該會提高性能。但它是可怕的（在我的系統上，需要4秒鐘，50000次迭代）。我還想過，如果我簡單地將Id作爲散列碼返回，性能應該很差，因爲我最終會得到50000個存儲桶。但情況正好相反，我想我只是簡單地產生了所謂的碰撞音，而不是改善任何事情。但是，再次，桶列表如何工作？

Answer 1

一個Contains檢查基本上是：

1. 獲取該項目的哈希碼。
2. 查找相應的存儲桶 - 這是基於項目哈希碼的直接數組查找。
3. 如果存在存儲桶，則嘗試查找存儲桶中的項目 - 這會迭代存儲桶中的所有項目。

通過限制存儲桶的數量，您增加了每個存儲桶中的項目數量，從而增加了hashset必須迭代的項目數量，檢查是否相等，以查看項目是否存在或不。因此，看看是否存在特定物品需要更長的時間。

您可能已經減少了哈希集的內存佔用量;你可能甚至減少了插入時間，雖然我懷疑它。你沒有減少存在檢查時間。

Answer 2

減少桶數不會增加性能。實際上，Int32的GetHashCode方法本身會返回整數值，這對於性能非常理想，因爲它將生成儘可能多的存儲桶。

提供哈希表性能的是從密鑰到哈希代碼的轉換，這意味着它可以快速消除集合中的大部分項目。唯一需要考慮的是同一個桶裏的東西。如果你沒有桶，這意味着它可以減少很多物品。

最壞的可能實現的GetHashCode將導致所有項目在同一個桶去：

public override int GetHashCode() { 
    return 0; 
} 

這仍然是一個有效的實現，但它意味着哈希表得到相同的性能，常規列表即它必須遍歷集合中的所有項目才能找到匹配項。

Answer 3

一個簡單的HashSet<T>可以這樣來實現（只是一個草圖，沒有編譯）

class HashSet<T> 
{ 
    struct Element 
    { 
     int Hash; 
     int Next; 
     T item; 
    } 

    int[] buckets=new int[Capacity]; 
    Element[] data=new Element[Capacity]; 

    bool Contains(T item) 
    { 
     int hash=item.GetHashCode(); 
     // Bucket lookup is a simple array lookup => cheap 
     int index=buckets[(uint)hash%Capacity]; 
     // Search for the actual item is linear in the number of items in the bucket 
     while(index>=0) 
     { 
      if((data[index].Hash==hash) && Equals(data[index].Item, item)) 
      return true; 
      index=data[index].Next;   
     } 
     return false; 
    } 
} 

如果你看看這個，在Contains搜索的成本是成正比的項目數桶。因此擁有更多的桶可以使搜索更便宜，但是一旦桶的數量超過了物品的數量，額外桶的收益就會迅速減少。

有不同的哈希碼也用於水桶內的比較對象，避免潛在的昂貴Equals電話早了。

總之GetHashCode應儘可能多樣化。它的HashSet<T>的工作向大空間減少到水桶適當數量，這大約是（在兩個因素通常）集合中的項目數量。