使用此实现，hashset.contains 如何成为 O(1)？

Question

.Net 中的 HashSet.Contains 实现是：

    /// <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) ，因为我们' d 只需要计算散列，获取桶并判断里面是否有东西。

我们并不是生活在一个完美的世界里。首先，考虑字符串散列。在 .NET 中，有 (2^16)^n 个可能的长度字符串n；GetHashCode返回 a long，并且 有 2^64 个可能的值long。这足以将每个长度为 4 的字符串散列到一个唯一的long，但是如果我们想要更长的字符串，则必须存在两个不同的值来提供相同的散列 - 这称为碰撞。此外，无论如何我们都不想一直维护 2^64 个存储桶。通常的处理方法是获取哈希码并以桶数为模计算其值以确定桶的编号¹。所以，要点是 -我们需要考虑碰撞。

引用的.NET Framework 实现使用最简单的处理冲突的方法 -每个存储桶都包含导致特定散列的所有对象的链接列表。您添加 object A，它被分配给一个 bucket i。您添加 object B，它具有相同的哈希值，因此它会i在A. 现在，如果您要查找任何元素，则需要遍历所有对象的列表并调用实际Equals方法来确定该对象是否确实是您要查找的对象。这解释了 for 循环 -在最坏的情况下，您必须遍历整个列表。

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

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

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

请注意，如果您知道哈希表使用的哈希函数和算法，则可以强制执行这种病态情况和 O(n) 查找。如果服务器从用户那里获取输入并将它们存储在哈希表中，则知道哈希函数和哈希表实现的攻击者可以将其用作 DDoS 攻击的向量。也有办法解决这个问题。将此视为证明，是的，最坏的情况可能是 O(n) 并且人们通常都知道这一点。

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

[1] 这正是声明中发生的事情 int i = m_buckets[hashCode % m_buckets.Length] - 1

[2] 至少那些使用朴素链接的不是。存在具有最坏情况恒定时间复杂度的哈希表。但与理论上（在时间复杂度方面）较慢的实现相比，它们在实践中通常更糟，主要是由于 CPU 缓存未命中。

[3] 我假设可能散列的域是所有longs的集合，所以它们有 2^64 个，但我写的所有内容都推广到任何其他非空的有限值集。