最坏情况下的搜索次数为零的散列复杂度

Question

散列表的大小为11，日期适合位置{3,5,7,9,6}如果未找到数据，必须进行多少次比较在最坏的情况下列表2,11,6

Answer 1

这在很大程度上取决于如何术语的预期和哈希表实现...

• “11号的哈希表”可能意味着11元素（特别是在C++中，.size()是查找表中有多少元素的函数）或11个桶，但在这种情况下可能意味着后者; “数据拟合”可能意味着每个桶的位置都有一个数据（单数据），也可能意味着可能有一个或多个（但是如果后者的意图和“大小“不是桶的数量，没有答案）。

• “多少次比较”通常是指键-VS-键比较，但执行需要执行的桶含量比较反对NO- [更多] - 值哨兵太

• 实现可能处理冲突使用每斗碰撞密钥列表，或者它可能老调重弹，或通过从散列到桶

因此，如果我们假设11桶，有些组偏移（位移列表）级联/跳在每个桶位置只有一个数据项{3,5,7,9,6}和按键按键比较isons和每个桶名义上的碰撞元素列表，那么可能发生的最坏情况就是将桶与现有入口进行比较，这意味着按键比较，然后是按键与哨兵比较。这可以满足“2”的答案。

如果系统使用位移列表或重新哈希表，通常几次都不会访问同一个桶（这在统计上不太可能），所以没有“最坏情况”的限制，因为实施放弃了。

如果特定的死简单的情况下，位移增量尝试下一个桶，它可能会放弃后访问一串填充桶并找到第一个空的...给出{3,5,7,9,6}最糟糕的情况是，它比较键然后在5和6之间，然后比较7与8的哨兵，进行3或4次总比较，具体取决于你如何计算。

如果大小指示元素的数量，使得11分布在{3,5,7,9,6}之间，这只有在任何单独的桶维护冲突键列表时才可能，则如果这些桶中的4个具有单个键，则剩余的桶可能有11-4 = 7，所以在失败之前可能有7次按键按键比较。

很难想象通过任何计数方法对产生6或11次比较的问题的任何合理解释。

如果有人在学术环境中问过你，在考虑问题时可能会有一些具体的实施和符号约定。如果缺少这样的上下文，那么任何人要么是非常懒惰，要么不熟悉哈希表的基础知识。