在字典中使用IEqualityComparer的效率vs HashCode和Equals（）

Question

標題非常清晰，我認爲。

我想知道在中使用IEqualityComparer時是否存在一定的效率開銷，提供一個時它是如何工作的？

感謝

Answer 1

它更快嗎？

從gamedev角度的到來，如果你的關鍵是值類型（結構，原始，枚舉等）提供自己的EqualityComparer<T>顯著更快 - 由於該EqualityComparer<T>.Default框中的值。

作爲一個真實的例子，Managed DirectX廣告牌樣本用於以C++版本速度的〜30％運行;其他所有樣本均以〜90％的比例運行。原因在於廣告牌正在使用默認比較器進行排序（因此被裝箱），因爲這導致每幀4MB的數據被複制。

它是如何工作的？

Dictionary<K,V>將通過默認的構造函數爲自己提供EqualityComparer<T>.Default。什麼是默認的相等比較確實是（基本上，注意多少拳時）：

public void GetHashCode(T value) 
{ 
    return ((object)value).GetHashCode(); 
} 

public void Equals(T first, T second) 
{ 
    return ((object)first).Equals((object)second); 
} 

爲什麼我會永遠使用它？

這是我們經常見到這樣的代碼（想有不區分大小寫鍵時）：

var dict = new Dictionary<string, int>(); 
dict.Add(myParam.ToUpperInvariant(), fooParam); 
// ... 
var val = dict[myParam.ToUpperInvariant()]; 

這真是浪費，最好是隻使用一個StringComparer在構造函數：

var dict = new Dictionary<string, int>(StringComparer.OrdinalIgnoreCase); 

它是否更快（減少）？

在這個特定的場景中，速度要快很多，因爲序號字符串比較是可以做的最快的字符串比較類型。快速基準：

static void Main(string[] args) 
{ 
    var d1 = new Dictionary<string, int>(); 
    var d2 = new Dictionary<string, int>(StringComparer.OrdinalIgnoreCase); 

    d1.Add("FOO", 1); 
    d2.Add("FOO", 1); 

    Stopwatch s = new Stopwatch(); 
    s.Start(); 
    RunTest1(d1, "foo"); 
    s.Stop(); 
    Console.WriteLine("ToUpperInvariant: {0}", s.Elapsed); 

    s.Reset(); 
    s.Start(); 
    RunTest2(d2, "foo"); 
    s.Stop(); 
    Console.WriteLine("OrdinalIgnoreCase: {0}", s.Elapsed); 

    Console.ReadLine(); 
} 

static void RunTest1(Dictionary<string, int> values, string val) 
{ 
    for (var i = 0; i < 10000000; i++) 
    { 
     values[val.ToUpperInvariant()] = values[val.ToUpperInvariant()]; 
    } 
} 

static void RunTest2(Dictionary<string, int> values, string val) 
{ 
    for (var i = 0; i < 10000000; i++) 
    { 
     values[val] = values[val]; 
    } 
} 

// ToUpperInvariant: 00:00:04.5084119 
// OrdinalIgnoreCase: 00:00:02.1211549 
// 2x faster. 

預訂

有可能通過在結構實現接口（如IEquatable<T>），以消除拳擊開銷。但是，在這種情況下出現拳擊時有很多令人驚訝的規則，所以我會建議使用配對的界面（例如在這種情況下爲IEqualityComparer<T>），如果可能的話。

Answer 2

Dictionary<,>總是採用了IEqualityComparer<TKey> - 如果你沒有通過一個，它採用EqualityComparer<T>.Default。所以效率將取決於您的執行效率與EqualityComparer<T>.Default（它們只是代表Equals和GetHashCode）的比較效率。

Answer 3

喬納森有great answer指向如何，使用正確相等比較提高了性能和喬恩在his great answer澄清Dictionary<K, V>始終使用的IEqualityComparer<T>除非你指定另一個是EqualityComparer<T>.Default。

當您使用默認的相等比較器時，我想要介紹的是IEquatable<T>接口的作用。

當你調用EqualityComparer<T>.Default時，它使用一個緩存比較器（如果有的話）。如果這是您第一次使用該類型的默認相等比較器，則會調用名爲CreateComparer的方法並緩存結果供以後使用。這裏是修剪和.NET 4.5簡化實施CreateComparer：

var t = (RuntimeType)typeof(T); 

// If T is byte, 
// return a ByteEqualityComparer. 

// If T implements IEquatable<T>, 
if (typeof(IEquatable<T>).IsAssignableFrom(t)) 
    return (EqualityComparer<T>) 
      RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter(
       (RuntimeType)typeof(GenericEqualityComparer<int>), t); 

// If T is a Nullable<U> where U implements IEquatable<U>, 
// return a NullableEqualityComparer<U> 

// If T is an int-based Enum, 
// return an EnumEqualityComparer<T> 

// Otherwise return an ObjectEqualityComparer<T> 

但是這是什麼意思爲實現IEquatable<T>類型？
這裏，GenericEqualityComparer<T>定義：

internal class GenericEqualityComparer<T> : EqualityComparer<T> 
    where T: IEquatable<T> 
// ... 

神奇發生在泛型類型約束（where T : IEquatable<T>部分），因爲使用它不包括拳擊，如果T是值類型，像(IEquatable<T>)T沒有鑄造發生在這裏，這是仿製藥的主要益處。

因此，假設我們需要一個將整數映射到字符串的字典。
如果我們使用默認構造函數初始化一個會發生什麼？

var dict = new Dictionary<int, string>(); 

• 我們知道，一個字典使用EqualityComparer<T>.Default除非我們指定另一個。
• 我們知道EqualityComparer<int>.Default會檢查int是否執行IEquatable<int>。
• 我們知道int（Int32）實施IEquatable<Int32>。

到EqualityComparer<T>.Default首先調用將創建並緩存它可能需要一些通用的比較器，但在初始化時，它是一個強類型GenericEqualityComparer<T>，並用它不會造成任何拳擊或任何不必要的開銷。

所有後續調用EqualityComparer<T>.Default將返回緩存的比較器，這意味着初始化的開銷只對每種類型是一次性的。

---

那麼這是什麼意思？

• 國家執行自定義相等比較，如果T沒有實現IEquatable<T>或你想讓它做什麼它的實施IEquatable<T>沒有做。
  （即obj1.Equals(obj2)不會給你想要的結果。）

在Jonathan的回答中使用StringComparer是一個很好的例子，你爲什麼要指定一個自定義的相等比較器。

• 沒有實現爲性能而定製的相等比較，如果T實現IEquatable<T>和的IEquatable<T>執行你想要做什麼就做。
  （即obj1.Equals(obj2)給你想要的結果）。

在後一種情況下，請改用EqualityComparer<T>.Default。

Answer 4

我面臨巨大的麻煩，使相同的EqualityComparer ...關鍵部分是針對GetHashCode和object[]記錄更多然後20​​K時，其產生重複鍵..下面是解決

public class ObJectArrayEqualityComparer : IEqualityComparer<object[]> 
{ 
    public bool Equals(object[] x, object[] y) 
    { 
     if (x.Length != y.Length) 
     { 
      return false; 
     } 
     for (int i = 0; i < x.Length; i++) 
     { 
      var tempX = x[i]; 
      var tempY = y[i]; 
      if ((tempX==null || tempX ==DBNull.Value) 
       && (tempY == null || tempY == DBNull.Value)) 
      { 
       return true; 
      } 

      if (!tempX.Equals(tempY) 
       && !System.Collections.StructuralComparisons.StructuralEqualityComparer.Equals(tempX, tempY)) 
      { 
       return false; 
      } 
     } 
     return true; 
    } 

    public int GetHashCode(object[] obj) 
    { 
     if (obj.Length == 1) 
     { 
      return obj[0].GetHashCode(); 
     } 

     int result = 0; 

     for (int i = 0; i < obj.Length; i++) 
     { 
      result = result + (obj[i].GetHashCode() * (65 + i)); 
     } 

     return result; 
    } 
}