搜索不存在且从未存在的密钥 O(n)？
Searching for a key that doesn't and has never existed O(n)?
我们以线性探测为例，因为它很简单。
你有一个（虚构的）散列 table 谁的键看起来像这样：
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
当然，算法无法判断密钥是否存在，除非它检查整个 table。
然而，在为此寻找答案时，我偶然发现了这个页面：https://msdn.microsoft.com/en-us/library/system.collections.hashtable.containskey(v=vs.110).aspx，其中指出它是 O(1)。当然，如果密钥存在，它可以是 O(1)，但它不会是平均的，对吗？最坏的情况（每次密钥不存在？）将是 O(n)。
我这样想对吗？
编辑：
我刚刚意识到它会在遇到空 space 时停止...所以这意味着如果 table 已满，它只会达到 O(n)？这一定是您不想要集群的原因？
I just realised that it would stop when it hit an empty space... So
this means that it would only reach O(n) if the table is full? Which
must be why you don't want clustering?
你是对的。请记住，每个使用开放寻址作为冲突解决技术（线性探测属于开放寻址）的体面散列 table 实现都会存储一个称为负载因子的特殊数字。负载因子是散列中的项目数 table 与可用插槽总数之间的比率。当负载因子增加超过特定值时，散列 table 会扩展 - 这是保持探测数量足够小并确保良好性能的方法。
由于您搜索了 C# 实现，我花时间找到了一个 documentation 描述散列 table 在 C# 2.0 中的实现。它指出：
As aforementioned, Microsoft has tuned the Hashtable to use a default
load factor of 0.72. Therefore, for you can expect on average 3.5
probes per collision. Because this estimate does not vary based on the
number of items in the Hashtable, the asymptotic access time for a
Hashtable is O(1), which beats the pants off of the O(n) search time
for an array.
我们以线性探测为例，因为它很简单。
你有一个（虚构的）散列 table 谁的键看起来像这样：
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
当然，算法无法判断密钥是否存在，除非它检查整个 table。
然而，在为此寻找答案时，我偶然发现了这个页面：https://msdn.microsoft.com/en-us/library/system.collections.hashtable.containskey(v=vs.110).aspx，其中指出它是 O(1)。当然，如果密钥存在，它可以是 O(1)，但它不会是平均的，对吗？最坏的情况（每次密钥不存在？）将是 O(n)。
我这样想对吗？
编辑： 我刚刚意识到它会在遇到空 space 时停止...所以这意味着如果 table 已满，它只会达到 O(n)？这一定是您不想要集群的原因？
I just realised that it would stop when it hit an empty space... So this means that it would only reach O(n) if the table is full? Which must be why you don't want clustering?
你是对的。请记住，每个使用开放寻址作为冲突解决技术（线性探测属于开放寻址）的体面散列 table 实现都会存储一个称为负载因子的特殊数字。负载因子是散列中的项目数 table 与可用插槽总数之间的比率。当负载因子增加超过特定值时，散列 table 会扩展 - 这是保持探测数量足够小并确保良好性能的方法。
由于您搜索了 C# 实现，我花时间找到了一个 documentation 描述散列 table 在 C# 2.0 中的实现。它指出：
As aforementioned, Microsoft has tuned the Hashtable to use a default load factor of 0.72. Therefore, for you can expect on average 3.5 probes per collision. Because this estimate does not vary based on the number of items in the Hashtable, the asymptotic access time for a Hashtable is O(1), which beats the pants off of the O(n) search time for an array.