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
参考方案
哈希表的经典实现方式是根据元素的哈希值将元素分配给多个存储桶之一。 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，但是我写的所有内容都概括为任何其他非空的有限值集。
Improve this question 我在类wait()中找到了方法Object。这是最终的，这意味着该方法不能被覆盖。有什么想法为什么是最终的？ 参考方案 @Flavio-这实际上是一个很好的问题。当然，您不能覆盖它的原因是设计师将其“确定为最终”。做出此决定的一些潜在原因：您不希望人们弄乱基本类（“对象”类）上基本操作的语义。由于它是“最终的”，因…
Web应用程序上的恶意用户是否可以操纵Web应用程序前端发送的输入(在表单数据旁边)？ - javaWeb应用程序上的恶意用户是否可以通过任何可能的方式来操纵Web应用程序前端发送的输入（当然，这不是在谈论FORM DATA），但是发送的请求例如当我允许他编辑他的个人资料或他的内容时，他可能会操纵ID（userId或contentId），从而可能恶意地对其他用户的内容进行邪恶？这些输入固定在网页上并且不可编辑，但用户仍然可以操纵它们吗？用户是否可能以这种方…
什么时候在Hibernate中调用flush()和commit()？ - java我有以下情况： openSession() tx = session.beginTransaction(); try { ... session.saveOrUpdate(obj_1); ... session.saveOrUpdate(obj_2); ... session.saveOrUpdate(obj_3); session.flush(); tx.…
如何在“后台”中运行脚本的一部分(单个函数)？ - python我在具有以下基本结构（伪代码）的服务器上运行python脚本：for data_item in data_items: processed_result=process_data(data_item); #this takes time T0 upload_result_to_site(processed_result) #this takes time T…
为什么在Python中根据@staticmethod选择模块级别的函数(根据Google样式指南)？ - python根据《 Google Python样式指南》，绝对不应（几乎）使用静态方法： 除非为了与 在现有库中定义的API。编写模块级功能 代替该建议背后的原因是什么？这是否仅适用于Google？还是在Python中使用静态方法还有其他（更一般的）缺点？尤其是，如果我想在将由该类的其他公共成员函数调用的类中实现实用程序功能，则最佳实践是什么？class Foo: ..…