use*_*354 6 hashtable duplicates
我今天早上刚接受了一次采访,我得到了一个问题"给出一个从整数列表中删除重复项的算法".这是一个相当标准的问题,所以我很有信心我可以回答它.
我正在解释,但我说的是"你可以使用哈希表.从第一个整数开始并将其插入哈希表.然后为每个连续的整数做一个哈希表查找以检查整数是否已经在哈希表中如果没有,那么插入它,如果它已经存在然后扔掉它,因为它是一个副本.所以以这种方式迭代列表.如果哈希表设计正确,查找和插入应该是平均的恒定时间.
然后面试官回应了(我再说一遍)"但哈希表查找不是恒定时间,它们取决于已经有多少元素.你描述的算法将是O(n ^ 2)"
然后我回答"真的吗？我认为如果你设计了一个好的哈希函数,那将是恒定的时间吗？通常是O(n)"
然后面试官回答"所以你说的是,对于有很多条目的哈希表和几个条目的哈希表,查找时间是相同的"
然后我说"是的.如果设计得当."
然后面试官说"这不是真的"
所以我现在很困惑.如果有人能指出我错在哪里,我将非常感激
如果有人能指出我错在哪里
你完全没有错：正确设计的哈希表为你提供了预期的查找效率O(1)和插入分摊效率O(1)，所以你的算法是O(N)。由于可能存在重复解析，在重负载的哈希表中查找确实会慢一些，但预期的查找时间仍然存在O(1)。对于“摊销”不重要的实时系统来说，这可能不够好，但在所有实际情况下这已经足够了。
当然，您始终可以对最坏情况O(N*LogN)算法中看到的项目使用平衡树，或者如果数字有合理的界限（例如，0 到 100,000 之间），您可以使用布尔数组来测试O(1)最坏情况下的成员资格-case，由于常数乘数较小，因此对哈希表有潜在的改进。