哈希碰撞线性探测运行时间

我正在尝试与一位朋友做功课，一个问题询问了线性探测方法的搜索，添加和删除的平均运行时间。我认为它是O（n），因为它必须检查一定数量的节点，直到它找到一个打开的节点为止。搜索时，它从原始索引处开始并向上移动，直到找到所需的数字。但我的朋友说这是O（1）。哪一个是对的？哈希碰撞线性探测运行时间

来源

2012-04-09 Richard

我想添加到Yavar答案：记住，O（1）不是一个运算。它可能是一个很大的常量，但是，如果它不是来自像n这样的变量，那并不重要。即使你需要通过20个节点来放置一个散列，它仍然是一个O（1）。当然，这适用于哈希表只有当某些条件为真，但求好设计的哈希表是O（1）平均 – Archeg 2012-04-09 11:51:38

当我们谈论渐近复杂性时，我们通常会考虑非常大的n。现在对于哈希表中的碰撞处理，一些方法是链式哈希&线性探测。在这两种情况下，可能发生两件事情（这将有助于回答您的问题）：1.您可能需要调整散列表的大小，因为它已满。2.可能会发生冲突。

在这将取决于你如何执行你的哈希表最坏的情况下，例如在线性探测你不找数，你继续移动，你要找的数量在年底。这是O（n）最坏情况下的运行时间。即将发生链接散列技术时，发生冲突时，处理它们时说我们已将密钥存储在平衡二叉树中，因此最坏情况下的运行时间为O（log n）。

现在即将到达最佳运行时间，我认为没有混淆，在任何情况下它都是O（1）。 O（n）会在最坏的情况下发生，而不是在设计良好的散列表的平均情况下发生。如果开始在平均情况哈希表发生不会找到数据结构的地方，因为上平均再平衡树会给你O（log n）的总是和上TOP将保留阶也。

很抱歉这么说，但不幸的是你的朋友是对的。你的情况会发生在最坏的情况下。

也看看这里的信息更丰富的东西即摊销运行时间：Time complexity of Hash table

来源

2012-04-09 11:34:37 Yavar

感谢@DanAllen，您的评论上述真的激励:) – Yavar 2014-12-16 19:46:24

哈希碰撞线性探测运行时间

回答

相关问题