关于哈希

哈希访问时间的问题是最好的时机O（1）和最坏情况下为O（n）。我想知道什么是平均情况？关于哈希

2011-02-28 user496949

对于不接近完全平均情况下的哈希是大致O（1）。细节取决于如何解决冲突以及散列的完整程度。通常效率开始真正下降80％左右的能力。

2011-02-28 09:08:03 bmenrigh

不此取决于散列算法的效率相对于该特定的一组中的当前数据中找到的键。你可能会非常不幸，看到意外高的碰撞。 – djna

也取决于你的数量。举例来说，如果你的键是字符串，如果您要添加N个不同的键散列，那么N个不同的字符串是平均长度至少欧米茄（日志N）的。机会是你的散列算法是欧米茄（字符串长度），所以它的欧米茄（日志N）的每个键只是凑吧，作为查找的一部分或插入。这仍然是O（n）的总虽然其中n是数据的总大小，而不是在哈希表元素（我已经叫N）的数量。 –

在实践中，Ô（1）。参见http://en.wikipedia.org/wiki/Hash_table#Performance_analysis

来源

2011-02-28 09:07:19

回答

相关问题