运行时将n个元素插入空哈希表

Question

人们说需要将摊销的O（1）放入哈希表中。因此，放n个元素必须是O（n）。然而，对于大n而言，情况并非如此，因为正如一位回答者所说，“所有你需要满足预期摊销的O（1）就是扩展表格，并在发生碰撞时使用新的随机散列函数重新散列所有内容。” ;

那么：将n个元素插入哈希表的平均运行时间是多少？我意识到这可能与实现有关，所以请提一下你正在谈论的实现类型。

例如，如果存在（log n）等间隔的冲突，并且每个冲突需要O（k）来解析，其中k是哈希表的当前大小，那么您将具有此递归关系：

T(n) = T(n/2) + n/2 + n/2

（也就是说，你花时间插入n / 2个元素，然后你有一个碰撞，取n / 2来解决，然后你做剩余的n / 2插入没有碰撞）。这仍然是O（n），所以是的。但这是否合理？

Answer 1

这完全取决于你的重组效率有多低。具体来说，如果您可以第二次正确估计哈希表的预期大小，则运行时仍会接近O（n）。实际上，您必须在确定预期顺序之前指定重新计算大小计算的效率。

Answer 2

  

人们说需要将摊销的O（1）放入哈希表中。

从理论角度来看，预期摊销O（1）。

哈希表基本上是一种随机数据结构，与快速排序是一种随机算法相同。您需要生成具有一些随机性的哈希函数，否则存在不是O（1）的病理输入。

您可以使用动态完美哈希来实现预期摊销的O（1）：

我最初发布的天真想法是在每次碰撞时重新使用新的随机哈希函数。 （另请参见完美哈希函数）这个问题是需要O（n ^ 2）空间，来自生日悖论。

解决方案是使用两个哈希表，第二个表用于冲突;通过重建来解决第二个表上的冲突。该表将具有O（\ sqrt {n}）元素，因此将增长到O（n）大小。

在实践中，您通常只使用固定的哈希函数，因为您可以假设（或者不关心）您的输入是病态的，就像您经常快速排序而不预先输入输入一样。

Answer 3

所有O（1）都表示操作是在恒定时间内执行的，并且不取决于数据结构中元素的数量。

简单来说，这意味着无论数据结构有多大，您都必须支付相同的费用。

实际上，这意味着当您不必存储大量数据时，简单的数据结构（如树）通常通常更有效。根据我的经验，我发现树速度快〜1k元素（32位整数），然后哈希表接管。但像往常一样YMMW。

Answer 4

为什么不在您的系统上运行一些测试？也许如果您发布源代码，我们可以返回并在我们的系统上对它们进行测试，我们可以将其简化为一个非常有用的讨论。

这不是实现，而是环境决定算法实际需要多长时间。但是，您可以查看是否有可用的基准测试样本。我发布结果的问题没有用，因为人们不知道我的系统上还有什么运行，现在有多少RAM可用，等等。你只能有一个广泛的想法。这和大O给你的一样好。