Java 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将不得不遍历他们，呼吁他们equals每个人寻找比赛。

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

在JDK 8中，HashMap已经进行了调整，以便可以比较键的排序方式，然后将任何人口稠密的存储桶都实现为树，因此即使有很多具有相同哈希码的条目，复杂度也为O（log n）。当然，如果你的键类型的相等性和顺序不同，则可能会导致问题。

是的，如果你没有足够的内存来存储哈希映射，那么你将遇到麻烦…但是，无论使用哪种数据结构，这都是正确的。