为什么使用GetHashCode()而不是Equals()？

Question

HashSet<T>.Add首先比较结果GetHashCode.如果它们是相同的,它会调用Equals.

现在,我的理解是为了实现GetHashCode,必须用对象的字段来完成某些事情.一个简单的示例实现可以在被覆盖的System.Object.GetHashCode的最佳算法是什么？.

在我的测试中,在填充随机数据的1.000.000对对象上进行比较,两者之间的性能或多或少相等.GetHashCode在链接示例中实现,Equals只需调用Equals所有字段.那么为什么要用GetHashCode它Equals？

Answer 1

对于某些类型,Equals测试可能相对昂贵.它通常必须比较类的每个字段.换句话说,它需要类的大小的线性时间.比较平等的更大的类更昂贵.

现在,如果您需要将一个对象与另一个对象进行比较,会发生什么？拨打Equals1000次可能会变得昂贵.如果N是类的大小,则需要进行N*2000字段访问

GetHashCode而是根据类的内容生成"大多数唯一"整数.换句话说,类字段被访问一次.一旦你有了,你可以将这个整数与构成其他对象的哈希码的1000个整数进行比较.

即使在这种天真的用例中,我们现在只需要N*1000个字段访问.

但是如果我们存储哈希码呢？当我们将一个对象插入一个哈希集时,它的哈希码计算一次.现在,任何我们想做的哈希集的查找时间,我们只需要计算一个哈希码(即外部对象的),然后你只需要简单的比较整数.所以N类字段访问(对于我们需要计算其哈希码的新对象),加上一些整数比较,这取决于算法,但是1)相对较少,2)便宜.

Answer 2

因为如果一个算法想要测试1个对象是否已经在一组1.000.000个对象中,它必须调用Equals1.000.000次,但GetHashCode()只需要调用一次(并且有几次调用Equals以消除虽然具有相同散列的不同对象码).