寻找一个不存在且从未存在的密钥O（n）？

你有一个（虚构的）哈希表是谁的键是这样的：

1 2 3 4 5 6 7 
[23| | 44|67|89| |22]

您要检查钥匙99，它不存在。它给人的哈希值5

肯定的算法是这样的：

Check 5: X 
Check 6: X 
Check 7: X 
Check 1: X 
Check 2: X 
Check 3: X 
Check 4: X 
Reached 5 again: Key not found

当然也没有办法，该算法能告诉我们，如果键存在或不存在，除非它会检查整个表。

但是，当搜索这个答案时，我偶然发现了这个页面：https://msdn.microsoft.com/en-us/library/system.collections.hashtable.containskey(v=vs.110).aspx，它表示它是O（1）。当然，如果密钥存在，它可以是O（1），但它会不会平均呢？而最坏的情况（每次钥匙不存在？）将是O（n）。

我正确的想这个吗？

编辑：我刚刚意识到，它会停止时，它打到一个空的空间......所以这意味着它只会达到O（n）如果表已满？这一定是你不想聚类的原因？

2016-10-22 Jamal Moir

是的，它可能有一个关键查找操作的O（n）复杂性，但这种情况非常罕见。这只会在你的散列函数很差时才会发生，即所有或几乎所有的键映射到同一个桶。如果你有一个好的散列函数确定一个密钥的存在是O（1）。 – Enrique

该文档没有说明使用了哪种冲突解决策略。所以你不能说它是否使用线性探测。 –

这不是'Dictionary '类在.NET中实现的方式。看看https://referencesource.microsoft.com/#mscorlib/system/collections/generic/dictionary.cs,d3599058f8d79be0 –

我才意识到，当它击中了一个空的空间，将停止......所以这意味着如果该表已满，将只能达到O（N）？哪一个一定是你不想聚类的原因？

你说得对。请记住，使用开放寻址作为冲突解决技术（线性探测属于开放寻址）的每个像样的散列表实现都会存储一个称为加载因子的特殊数字。负载因子是散列表中项目数与可用插槽总数之间的比率。当负载因子增加超过某个值时，散列表就会扩大 - 这就是保持足够小的探针数量并确保良好性能的方法。

由于您搜索了C＃实现，我花了很长时间，发现了一个描述在C＃2.0中实现哈希表的documentation。它声称：

如前所述，微软已经调整了Hashtable使用默认的加载因子0.72。因此，对于每次碰撞，您可以平均预期探测3.5个探针。由于此估计值不会根据散列表中的项数量而变化，因此散列表的散列表的渐近访问时间为O（1），这使阵列的O（n）搜索时间脱离裤子。

2016-10-22 16:53:47

回答