这个实现中`HashSet<T>.Contains`怎么可能是O(1)？

Question

HashSet<T>.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

哈希表的经典实现是根据元素的哈希值将元素分配到多个存储桶之一。 如果散列是完美的，即没有两个元素具有相同的散列，那么我们将生活在一个完美的世界中，我们不需要关心任何事情 - 任何查找都将是 O(1) always ，因为我们只需要计算哈希值，获取桶并判断里面是否有东西。

我们并不是生活在一个完美的世界中。首先，考虑字符串哈希。在.NET中，有(2^16)^n个可能的长度为

n

的字符串；

GetHashCode

返回一个

int

，并且

int

有 2^32 个可能的值。这足以将长度为 2 的每个字符串散列为唯一的

int

，但如果我们想要比这更长的字符串，必须存在两个不同的值给出相同的散列 - 这称为冲突。另外，无论如何，我们不想始终维护 2^32 个存储桶。处理这个问题的通常方法是获取哈希码并计算其值以存储桶数量为模以确定存储桶的数量¹。所以，要点是 - 我们需要允许碰撞。

所引用的 .NET Framework 实现 使用最简单的方法来处理冲突 - 每个存储桶都包含导致特定哈希值的所有对象的链表。您添加对象

A

，它被分配到一个存储桶

i

。您添加对象

B

，它具有相同的哈希值，因此它会在

i

之后添加到存储桶

A

中的列表中。现在，如果您查找任何元素，您需要遍历所有对象的列表并调用实际的

Equals

方法来查明该元素是否确实是您要查找的元素。这就解释了 for 循环 - 在最坏的情况下，你必须遍历整个列表。

好吧，那么“哈希集中的搜索复杂度为 O(1)”怎么样？ 不是的。最坏情况的复杂性与项目的数量成正比。平均时间复杂度为 O(1) 。2 ^{如果所有对象落入同一个桶，则请求列表末尾的元素（或者不在结构中但会落入同一个桶的元素） )} 将 为 O(n)。

那么人们所说的“平均时间为 O(1)”是什么意思呢？该结构监视有多少对象与存储桶的数量成比例，如果超过某个阈值（称为负载因子），它就会调整大小。很容易看出，这使得平均查找时间与负载因子成正比。

这就是为什么哈希函数“均匀”很重要，这意味着两个随机选择的不同对象获得相同的

int 分配的概率是 1/2^323

。这使哈希表中的对象分布保持一致，因此我们可以避免一个桶包含大量项目的病态情况。

^{请注意，如果您知道哈希函数和哈希表使用的算法，则可以强制执行这种病态情况和 O(n) 查找。如果服务器获取用户的输入并将其存储在哈希表中，则了解哈希函数和哈希表实现的攻击者可以将其用作 DDoS 攻击的向量。} 也有解决这个问题的方法

。将此视为一个证明，是的，最坏的情况可能是 O(n) 并且人们普遍意识到这一点。

还有数十种其他更复杂的哈希表实现方式。如果您有兴趣，则需要自己研究。由于查找结构在计算机科学中如此普遍，人们提出了各种疯狂的优化，不仅最大限度地减少了理论操作数，还最大限度地减少了 CPU 缓存未命中之类的事情。

[1] 这正是声明中所发生的情况

int i = m_buckets[hashCode % m_buckets.Length] - 1

---

[2] 至少那些使用朴素链接的不是。 

存在最坏情况恒定时间复杂度的哈希表

。但与理论上（就时间复杂度而言）较慢的实现相比，它们在实践中通常更糟糕，主要是由于 CPU 缓存未命中。

[3] 我假设可能的散列的域是所有 int

的集合，因此它们有 2^32 个，但我写的所有内容都概括为任何其他非空的有限值集。