c# - 在此实现中，hashset.contains如何为O(1)？

Question

HashSet.Contains在.Net中的实现是:

    /// <summary>
    /// Checks if this hashset contains the item
    /// </summary>
    /// <param name="item">item to check for containment</param>
    /// <returns>true if item contained; false if not</returns>
    public bool Contains(T item) {
        if (m_buckets != null) {
            int hashCode = InternalGetHashCode(item);
            // see note at "HashSet" level describing why "- 1" appears in for loop
            for (int i = m_buckets[hashCode % m_buckets.Length] - 1; i >= 0; i = m_slots[i].next) {
                if (m_slots[i].hashCode == hashCode && m_comparer.Equals(m_slots[i].value, item)) {
                    return true;
                }
            }
        }
        // either m_buckets is null or wasn't found
        return false;
    }

而且我在很多地方读到“哈希集中的搜索复杂度为O(1)”。如何？
那为什么会存在for循环呢？

编辑:.net引用链接:https://github.com/microsoft/referencesource/blob/master/System.Core/System/Collections/Generic/HashSet.cs

Answer 1

哈希表的经典实现方式是根据元素的哈希值将元素分配给多个存储桶之一。 If the hashing was perfect，即没有两个元素具有相同的哈希值，那么我们将生活在一个完美无缺的世界中，我们不需要关心任何事情-任何查找始终都是O(1)，因为我们只需要计算哈希值，获取存储桶，并说出其中是否有东西。

我们不是生活在一个完美的世界中。首先，考虑字符串哈希。在.NET中，存在(2 ^ 16)^ n个长度为n的字符串； GetHashCode返回一个long，并且long可能有2 ^ 64个值。这足以将每个长度为4的字符串散列为唯一的long，但是如果我们想要更长的字符串，则必须存在两个提供相同散列的不同值-这称为碰撞。另外，我们也不想一直保持2 ^ 64个存储桶。解决该问题的通常方法是获取哈希码，并以存储桶数为模来计算其值，以确定存储桶的编号1。因此，要点是-，我们需要允许发生冲突。

引用的.NET Framework implementation使用最简单的方式处理冲突-every bucket holds a linked list of all objects that result in the particular hash。您添加对象A，它已分配给存储桶i。您添加了对象B，它具有相同的哈希值，因此它被添加到i之后的存储桶A中的列表中。现在，如果您要查找任何元素，则需要遍历所有对象的列表，并调用实际的Equals方法来确定该对象是否实际上是您要查找的对象。这就解释了for循环-，在最坏的情况下，您必须遍历整个列表。

好的，那么“散列集中的搜索复杂度是O(1)”如何呢？ 不是。最坏情况下的复杂度与项目数成正比。平均为O(1)。 2如果所有对象都属于同一存储桶，则要求列表末尾的元素(或要求不在结构中但将属于同一存储桶的元素)为O(n)。

那么人们所说的“平均为O(1)”是什么意思？该结构监视与桶数成正比的多少个对象，如果超过了某个阈值(称为负载系数)，它将重新调整大小。显而易见，这使平均查找时间与负载因子成正比。

这就是为什么使哈希函数保持一致很重要的原因，这意味着两个随机选择的不同对象获得分配的相同long的概率为1/2 ^ 643。这样可以使哈希表中的对象分布保持一致，因此我们避免了一个桶包含大量项目的病理情况。

请注意，如果您知道哈希函数和哈希表使用的算法，则可以强制进行这种病理情况和O(n)查找。如果服务器从用户那里获取输入并将其存储在哈希表中，则知道哈希函数和哈希表实现的攻击者可以将其用作DDoS攻击的向量。 There are ways of dealing with that too。以此作为证明，是的，最坏的情况可能是O(n)，人们通常都知道这一点。

还有许多其他更复杂的哈希表实现方式。如果您有兴趣，则需要自己进行研究。由于查找结构在计算机科学中如此普遍，因此人们提出了各种疯狂的优化方法，这些优化方法不仅使理论上的操作数量减少，而且使CPU高速缓存未命中率最小化。

[1]这就是int i = m_buckets[hashCode % m_buckets.Length] - 1语句中发生的事情

[2]至少使用朴素链接的不是。 There exist hash tables with worst-case constant time complexity。但是通常，与理论上(在时间复杂度方面)较慢的实现相比，它们在实践中更糟糕，这主要是由于CPU高速缓存未命中。

[3]我假设可能的散列的域是所有long的集合，所以它们有2 ^ 64，但是我写的一切都归纳为任何其他非空的有限值集。