问题描述
我对哈希表的时间复杂度感到困惑，许多文章指出哈希表是摊销O(1)"而不是真实顺序O(1)，这在实际应用中意味着什么.哈希表中操作的平均时间复杂度是多少，在实际实现中不是理论上的，为什么操作不是真实的O(1)?
I am confused about the time complexity of hash table many articles state that they are "amortized O(1)" not true order O(1) what does this mean in real applications. What is the average time complexity of the operations in a hash table, in actual implementation not in theory, and why are the operations not true O(1)?
推荐答案
我们无法预先知道您的哈希函数将产生多少次碰撞，以及是否需要调整大小.这会给哈希表的性能增加不可预测的元素，使其成为非O(1).但是，实际上，所有哈希表实现都在大量插入中提供O(1).这与数组插入相同-除非需要调整大小，否则为O(1)，在这种情况下为O(n)，再加上碰撞不确定性.
It's impossible to know in advance how many collisions you will get with your hash function, as well as things like needing to resize. This can add an element of unpredictability to the performance of a hash table, making it not true O(1). However, virtually all hash table implementations offer O(1) on the vast, vast, vast majority of inserts. This is the same as array inserting - it's O(1) unless you need to resize, in which case it's O(n), plus the collision uncertainty.
实际上，哈希冲突非常少见，您唯一需要担心这些细节的条件是特定代码的运行时间窗口非常紧凑.对于几乎所有用例，哈希表均为O(1).比O(1)插入更令人印象深刻的是O(1)查找.
In reality, hash collisions are very rare and the only condition in which you'd need to worry about these details is when your specific code has a very tight time window in which it must run. For virtually every use case, hash tables are O(1). More impressive than O(1) insertion is O(1) lookup.
这篇关于哈希表的时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！