Cla*_*diu 4 algorithm hash runtime hashtable hashmap
人们说它需要摊销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),所以是的.但这是否合理？
人们说它需要摊销O(1)才能放入哈希表.
从理论的角度来看,预计摊销O(1).
哈希表基本上是一种随机数据结构,与快速排序是一种随机算法相同.您需要生成具有一些随机性的哈希函数,否则存在不是O(1)的病理输入.
您可以使用动态完美散列实现预期的摊销O(1):
我最初发布的天真想法是在每次碰撞时重新使用新的随机哈希函数.(另见完美散列函数)这个问题是,这需要O(n ^ 2)空间,来自生日悖论.
解决方案是有两个哈希表,第二个表用于冲突; 通过重建来解决第二个表上的冲突.该表将具有O(\ sqrt {n})元素,因此将增长到O(n)大小.
在实践中,您通常只使用固定的哈希函数,因为您可以假设(或者不关心)您的输入是病态的,就像您经常快速排序而不预先输入输入一样.