duplicates - 基本哈希表算法 - 删除重复项

Question

我今天早上刚刚参加了一次面试，我被问到的问题是“给出一种从整数列表中删除重复项的算法”。这是一个相当标准的问题，所以我非常有信心能够回答它。

我是在解释，但我说了类似“你可以使用哈希表。从第一个整数开始并将其插入到哈希表中。然后对于每个连续的整数进行哈希表查找以检查该整数是否已经存在在哈希表中，如果没有则插入它，如果已经存在则将其丢弃，因为它是重复的。因此以这种方式迭代列表。如果哈希表设计正确，则查找和插入平均应该是恒定时间”

然后面试官回答(我再次解释)“但是哈希表查找不是恒定时间，它们取决于其中已有多少元素。您描述的算法将是 O(n^2)”

然后我回答“真的吗？我想如果你设计了一个好的哈希函数，它会是常数时间？通常是 O(n)”

然后面试官回答“所以你的意思是，对于具有多个条目的哈希表和一个具有很少条目的哈希表，查找时间是相同的”

然后我说“是的。如果设计正确的话。”

然后面试官说“这不是真的”

所以我现在很困惑。如果有人能指出我哪里错了，我将不胜感激

Answer 1

If someone could point out where I am wrong

你完全没有错:正确设计的哈希表为你提供了 O(1) 的预期查找效率，并以摊销的 O(1) 插入，所以你的算法为O(N)。由于可能存在重复解析，在负载较重的哈希表中查找确实会慢一些，但预期的查找时间仍然是 O(1)。对于“摊销”不重要的实时系统来说，这可能不够好，但在所有实际情况下这已经足够了。

当然，您始终可以对最坏情况 O(N*LogN) 算法中看到的项目使用平衡树，或者如果数字具有合理的界限(例如， 0 到 100,000 之间)您可以使用 bool 数组来测试 O(1) 最坏情况下的成员资格，并且由于常数乘数较小，因此对哈希表有潜在的改进。