在Dictionary中使用IEqualityComparer与HashCode和Equals（）的效率

我认为标题非常清楚。

我想知道在Dictionary使用IEqualityComparer时是否存在一定的效率开销？提供一个时它是如何工作的？

谢谢

Answer 1

它更快吗？

从gamedev的角度来看，如果你的键是一个值类型（struct，primitive，enum等），那么提供你自己的EqualityComparer的速度要快得多 – 因为EqualityComparer.Default将这个值框起来。

作为一个真实的例子，Managed DirectX广告牌样本的运行速度大约是C ++版本的30％; 其他所有样品的运行率均为~90％。 原因是广告牌正在使用默认比较器进行排序（因此被装箱），因为事实certificate，每个帧周围都会复制4MB的数据。

它是如何工作的？

Dictionary将通过默认构造函数为自身提供EqualityComparer.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(); dict.Add(myParam.ToUpperInvariant(), fooParam); // ... var val = dict[myParam.ToUpperInvariant()]; 

这真的很浪费，最好在构造函数上使用StringComparer：

 var dict = new Dictionary(StringComparer.OrdinalIgnoreCase); 

它更快（redux）？

在这种特定情况下，它要快得多，因为序数字符串比较是您可以做的最快的字符串比较类型。 快速基准：

 static void Main(string[] args) { var d1 = new Dictionary(); var d2 = new Dictionary(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 values, string val) { for (var i = 0; i < 10000000; i++) { values[val.ToUpperInvariant()] = values[val.ToUpperInvariant()]; } } static void RunTest2(Dictionary 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 ）可以消除装箱开销。 然而，在这些情况下发生装箱时有很多令人惊讶的规则，所以我建议使用配对界面（例如在这种情况下为IEqualityComparer ）。

Answer 2

Jonathan有一个很好的答案 ，指出如何使用正确的相等比较器改善性能，Jon在他的好答案中澄清了 Dictionary总是使用IEqualityComparer ，即EqualityComparer.Default除非你指定另一个。

我想IEquatable是当你使用默认的相等比较器时IEquatable接口的作用。

当您调用EqualityComparer.Default ，它会使用缓存的比较器（如果有）。 如果这是您第一次使用该类型的默认相等比较器，它会调用一个名为CreateComparer的方法并缓存该结果以供以后使用。 以下是.NET 4.5中CreateComparer的修剪和简化实现：

 var t = (RuntimeType)typeof(T); // If T is byte, // return a ByteEqualityComparer. // If T implements IEquatable, if (typeof(IEquatable).IsAssignableFrom(t)) return (EqualityComparer) RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter( (RuntimeType)typeof(GenericEqualityComparer), t); // If T is a Nullable where U implements IEquatable, // return a NullableEqualityComparer // If T is an int-based Enum, // return an EnumEqualityComparer // Otherwise return an ObjectEqualityComparer 

但是对于实现IEquatable类型意味着什么？
这里， GenericEqualityComparer的定义：

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

魔法发生在generics类型约束中（ where T : IEquatable部分），因为如果T是值类型，使用它不涉及装箱，这里没有像(IEquatable)T那样的铸造，这是主要的仿制药的好处。

所以，假设我们想要一个将整数映射到字符串的字典。
如果我们使用默认构造函数初始化一个会发生什么？

 var dict = new Dictionary(); 

• 我们知道除非我们指定另一个字典，否则字典使用EqualityComparer.Default 。
• 我们知道EqualityComparer.Default将检查int是否实现了IEquatable 。
• 我们知道int （ Int32 ）实现了IEquatable 。

首先调用EqualityComparer.Default将创建并缓存一个通用的比较器，它可能需要一点点但是在初始化时，它是一个强类型的GenericEqualityComparer并且使用它将不会导致装箱或不必要的开销。

并且对EqualityComparer.Default所有后续调用都将返回缓存的比较器，这意味着初始化的开销仅为每种类型一次性。

---

那么这一切意味着什么呢？

• 如果T没有实现IEquatable 或者它的IEquatable实现没有按照你想要它做的那样，那么实现一个自定义相等比较器。
  （即obj1.Equals(obj2)给你想要的结果。）

在Jonathan的回答中使用StringComparer是一个很好的例子，您可以指定自定义相等比较器。

• 如果T实现IEquatable 并且 IEquatable的实现执行了您想要的操作，则不要为了性能而实现自定义相等比较器。
  （即obj1.Equals(obj2)为您提供所需的结果）。

在后一种情况下，请改用EqualityComparer.Default 。

Answer 3

Dictionary<,> 总是使用IEqualityComparer – 如果你没有传递一个，它使用EqualityComparer.Default 。 因此，效率将取决于您的实现与EqualityComparer.Default （仅委托给Equals和GetHashCode ）相比的效率。

Answer 4

我在制作一个相同的EqualityComparer遇到了很大的麻烦…关键部分是GetHashCode ，当目标object[]并且记录超过20k时生成重复键。下面是解决方案

 public class ObJectArrayEqualityComparer : IEqualityComparer { 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; } }