.NET编译器如何能够为HashSet <T>中的任何T构造O(1)查找？

Question

我不明白编译器如何足够聪明,可以构建一个O(1)查找MyObject,我可以在其中放置任何内容

public class MyObject
{
    // ... 
}

我理解如何为有限数量的非原语如:

public class MyObject
{
    int i { get; set; }
    char c { get; set; }
}

但它怎么可能知道如何执行任何实现MyObject呢？

Answer 1

1. 获取哈希码
2. 模数下来生成数组的索引.
3. 看这里.如果项目存在,看它是否相等.

到目前为止,完美的O(1).如果很多项目最终都具有模数下降到相同索引的哈希码,那么它就会失败.这种情况发生了一些预期和处理,但如果它一直发生,你最终会出现O(n)行为(并且实际上是非常糟糕的不变成本).

默认情况下,所有对象都有一个GetHashCode()和一个Equals()基于引用的标识(也就是说,它们只等于它们自己).覆盖这些更改它具有的相等概念,因此在更改GetHashCode()时必须始终更改Equals()(所有相等的对象必须具有相同的哈希码).您还可以通过使用IEqualityComparer<T>提供不同GetHashCode()和使用的实现来强制使用不同的相等概念Equals().

Answer 2

每个对象都有一个与之关联的哈希码.有一个方法(在基类中定义为virtual )必须在类中重写,以便可以正常工作.GetHashCode objectHashSet

甲散列码是一个数值,其用于插入和确定基于散列的集合的对象,如Dictionary类,Hashtable类,或从DictionaryBase类派生的类型.GetHashCode方法为需要快速检查对象相等性的算法提供此哈希代码.

使用当前的类,它将无法正常工作(因为GetHashCode未被覆盖).相等性的比较将在参考而不是实际值的基础上进行.