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

Question

我不明白编译器如何聪明到为MyObject构造O（1）查找，在那里我可以在中放入任何东西

public class MyObject
{
    // ... 
}

我理解如何对有限数量的非基元（如）执行此操作

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

但是它怎么可能知道对于CCD_ 2的任何实现如何做到这一点呢？

Answer 1

1. 获取哈希代码
2. 向下生成一个数组索引的模
3. 看那里。如果有一个项目，看看它是否相等

到目前为止，完全O（1）。如果很多项目最终都有模化为同一索引的哈希代码，那么它就会失败。这种情况的发生是意料之中的，也会得到处理，但如果一直发生，你最终会出现O（n）行为（以及非常糟糕的持续成本）。

默认情况下，所有对象都具有基于引用标识的GetHashCode()和Equals()（也就是说，它们仅等于自身）。重写这些会更改它所具有的相等概念，因此在更改Equals()时必须始终更改GetHashCode()（所有相等的对象都必须具有相等的哈希代码）。您还可以通过使用IEqualityComparer<T>实现来强制使用不同的相等概念，该实现提供了不同的GetHashCode()和Equals()。

Answer 2

每个对象都有一个与其关联的哈希代码。有一个方法GetHashCode（在基本object类中定义为virtual）必须在类中重写，以便HashSet能够正常工作。

哈希代码是一个用于插入和标识的数值基于哈希的集合中的对象，例如Dictionary类、Hashtable类或派生的类型来自DictionaryBase类。GetHashCode方法提供了需要快速检查对象相等性的算法的哈希代码。

使用当前类，它将无法正常工作（因为GetHashCode未被重写）。相等性的比较将基于参考值而不是实际值。