哈希映射获取/放置复杂性

data-structures hashmap java complexity-theory

2022-08-31 06:50:15

我们习惯于说操作是O（1）。但是，这取决于哈希实现。缺省对象哈希实际上是 JVM 堆中的内部地址。我们确定声称是O（1）就足够了吗？HashMapget/putget/put

可用内存是另一个问题。正如我从javadocs中了解到的那样，负载因子应该是0.75。如果我们在JVM中没有足够的内存并且负载因子超过限制怎么办？HashMap

所以，看起来 O（1）是不能保证的。这有意义还是我错过了什么？

答案 1

这取决于很多事情。它通常是O（1），有一个体面的哈希值，它本身就是恒定的时间......但是你可以有一个需要很长时间才能计算的哈希，如果哈希映射中有多个项目返回相同的哈希代码，则必须迭代它们，调用它们中的每一个来查找匹配项。getequals

在最坏的情况下，由于遍历同一哈希桶中的所有条目（例如，如果它们都具有相同的哈希代码），因此具有O（n）查找。幸运的是，根据我的经验，这种最坏的情况在现实生活中并不经常出现。所以不，O（1）当然不能保证 - 但它通常是你在考虑使用哪些算法和数据结构时应该假设的。HashMap

在 JDK 8 中，已经过调整，如果可以比较键进行排序，则任何密集填充的存储桶都实现为树，因此即使有很多条目具有相同的哈希代码，复杂性也是 O（log n）。当然，如果您有一个键类型，其中相等性和顺序不同，这可能会导致问题。HashMap

是的，如果您没有足够的内存用于哈希映射，您将遇到麻烦...但无论你使用什么数据结构，这都是正确的。

答案 2

已经提到哈希映射是平均值，如果是项目的数量，并且是大小。还有人提到，原则上整个事情可能会在查询时间内折叠成一个单一的链接列表。（这一切都假设计算哈希是常量时间）。O(n/m)nmO(n)

然而，不经常提到的是，至少概率（所以对于1000个项目，这是99.9%的机会），最大的桶不会被填满！因此，匹配二叉搜索树的平均复杂度。（常数是好的，更紧密的界限是）。1-1/nO(logn)(log n)*(m/n) + O(1)

这个理论边界所需要的只是你使用一个相当好的哈希函数（参见维基百科：通用哈希。它可以像）一样简单）。当然，给你哈希值的人不知道你是如何选择随机常数的。a*x>>m

TL;DR：在非常高的概率下，哈希映射的最坏情况获取/放置复杂性是。O(logn)