HashMap获取/放置复杂性

我们习惯于说HashMap get/put操作是O（1）。但是这取决于哈希实现。默认对象散列实际上是JVM堆中的内部地址。我们确定它是否足以说明get/put是O（1）？

可用内存是另一个问题。正如我从javadocs了解到的， HashMap load factor应该是0.75。如果我们在JVM中没有足够的内存并且load factor超出限制呢？

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

这取决于很多事情。它通常是 O（1），有一个不错的散列本身是恒定的时间…但是你可能有一个散列需要很长的时间来计算，如果散列映射中有多个项目返回相同的散列码， get将不得不遍历他们每个人调用equalsfind一个匹配。

在最坏的情况下，由于散列在同一散列桶中的所有条目（例如，如果它们全部具有相同的散列码）， HashMap具有O（n）查找。幸运的是，根据我的经验，最坏的情况在现实生活中并不常见。所以不，O（1）肯定是不能保证的，但是在考虑使用哪种algorithm和数据结构时，通常应该假设它。

在JDK 8中， HashMap已经被调整，所以如果密钥可以比较sorting，那么任何密集的桶被实现为一棵树，所以即使有许多具有相同哈希代码的条目，复杂度为O（日志n）。当然，如果你有一个关键types，那么平等和sorting是不同的。

是的，如果你没有足够的内存散列映射，你将会遇到麻烦……但是无论你使用哪种数据结构，情况都是如此。

我不确定默认的哈希码是不是地址 – 我刚才读了OpenJDK哈希码生成源，我记得它有点复杂。仍然不是保证良好分配的东西，也许。然而，这在一定程度上是没有意义的，因为在hashmap中用作关键字的类很less使用默认的哈希码 – 它们提供了自己的实现，这应该是好的。

最重要的是，你可能不知道的（再次，这是基于阅读源 – 这是不能保证）是哈希映射搅拌之前使用它的散列，从整个词混合熵到底部位，这是它的地方除了最大的hashmaps外，都需要它。这有助于处理散列，特别是不自己做，虽然我不能想到任何你能看到的常见情况。

最后，当表超载时会发生什么，它退化为一组并行链表 – 性能变成O（n）。具体来说，所遍历的链接的数量平均是负载因子的一半。

HashMap操作是hashCode实现的依赖因素。对于理想的情况，可以说好的散列实现为每个对象提供唯一的散列码（无散列冲突），那么最好的，最坏的和平均的情况是O（1）。让我们考虑一个hashCode的错误实现总是返回1或者具有散列冲突的这样的散列的场景。在这种情况下，时间复杂度将是O（n）。

现在谈到关于内存问题的第二部分，那么JVM就会考虑内存约束。

已经提到，如果n是物品的数目， m是尺寸，则hashmaps平均为O(n/m) 。还有人提到，原则上整个事情可以用O(n)查询时间折成一个单独的链表。（这一切都假定计算哈希是恒定的时间）。

然而不经常提到的是，以至less1-1/n概率（所以1000个项目有99.9％的几率），最大的桶将不会被填充超过O(logn) ！因此匹配二叉search树的平均复杂度。（常数是好的，更严格的界限是(log n)*(m/n) + O(1) ）。

所有这些都需要使用一个相当好的散列函数（参见Wikipedia： Universal Hashing ，它可以像a*x>>m那样简单）。当然，给你哈希值的人不知道你是如何select你的随机常量的。

TL; DR：具有非常高的可能性最坏的情况下，hashmap的get / put复杂度是O(logn) 。