使用此实现，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;
    }

而且我看了很多地方"search complexity in hashset is O(1)"。如何？那为什么会有那个for循环？

编辑：.net 参考 link：https://github.com/microsoft/referencesource/blob/master/System.Core/System/Collections/Generic/HashSet.cs

Answer 1

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

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

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

好的，那么 "search complexity in hashset is O(1)" 怎么样？ 不是。最坏情况的复杂性与项目的数量成正比。是O(1) 平均.² 如果所有的对象都落到同一个桶中，求最后的元素列表的（或者对于那些不在结构中但会落入同一个桶的列表）将是O（n）。

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

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

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

还有许多其他更复杂的散列 table 可以实现的方法。如果你有兴趣，你需要自己研究。由于查找结构在计算机科学中非常普遍，人们提出了各种疯狂的优化，不仅最大限度地减少了理论上的操作次数，而且还最大限度地减少了诸如 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 个，但我写的所有内容都概括为任何其他非空值，有限的一组值。

使用此实现，hashset.contains 怎么可能是 O(1)？

How can hashset.contains be O(1) with this implementation?

c#

hashset

time-complexity

.net-core