在此实现中，hashset.contains如何为O（1）？

Question

HashSet。包含.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）

always，因为我们只需要计算哈希值，获取存储桶，然后说出其中是否有东西。

我们不是生活在一个完美的世界中。首先，考虑字符串哈希。在.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，它具有相同的哈希，因此将其添加到A之后的存储桶'i'中的列表中。现在，如果您要查找任何元素，则需要遍历所有对象的列表，并调用实际的Equals方法来确定该对象是否实际上是您要查找的对象。这就解释了for循环-

在最坏的情况下，您[[必须

遍历整个列表。好，那么“哈希集中的搜索复杂度是O（1）”如何？ 不是。最坏情况下的复杂度与项目数成正比。它是O（1）

平均

。 2如果所有对象都属于同一存储桶，请在列表的末尾请求元素（或对于不在结构中但会在列表中找到的元素）落在同一个桶中）将为O（n）。 所以人们所说的“平均为O（1）是什么意思？该结构监视与桶数成正比的多少个对象，如果超过了某个阈值（称为负载系数），它将调整大小。显而易见，这使平均查找时间与负载因子成正比。这就是为什么散列函数必须

uniform

的重要性，这意味着两个随机选择的不同对象得到相同的long分配的概率为1/2 ^ 64

3

。这样可以使哈希表中的对象分布保持一致，因此我们避免了一个桶包含大量项目的病理情况。 注意，如果您知道哈希函数和哈希表使用的算法，则可以强制进行这种病理情况和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，但是我写的所有内容都适用于任何其他非空的有限值集。