我们习惯于说HashMap,get/put次运算是O(1).但是，这取决于散列实现.默认对象散列实际上是JVM堆中的内部地址.我们真的可以说get/put是O(1)吗？
可用内存是另一个问题.正如我从javadocs中了解到的，HashMap负载系数应该是0.75.如果JVM中没有足够的内存，并且负载因子超过了限制，该怎么办？
所以，看起来O(1)是不能保证的.这有意义吗，还是我错过了什么？
我们习惯于说HashMap,get/put次运算是O(1).但是，这取决于散列实现.默认对象散列实际上是JVM堆中的内部地址.我们真的可以说get/put是O(1)吗？
可用内存是另一个问题.正如我从javadocs中了解到的，HashMap负载系数应该是0.75.如果JVM中没有足够的内存，并且负载因子超过了限制，该怎么办？
所以，看起来O(1)是不能保证的.这有意义吗，还是我错过了什么？
这取决于很多事情.它是usuallyo(1)，有一个不错的散列，它本身就是常数时间...但是你可能有一个需要很长时间来计算的散列，and如果散列映射中有多个项目返回相同的散列码，get将不得不对它们进行迭代，并对每个项目调用equals来找到匹配项.
在最坏的情况下，由于遍历同一散列桶中的所有条目(例如，如果它们都有相同的散列代码)，HashMap具有O(n)查找.幸运的是，根据我的经验，这种最坏的情况在现实生活中并不经常出现.所以不，O(1)当然不能保证——但这通常是在考虑使用哪些算法和数据 struct 时应该假设的.
在JDK 8中，对HashMap进行了调整，这样如果可以比较密钥进行排序，那么任何密集的bucket都将实现为一棵树，这样即使有许多条目具有相同的哈希代码，复杂性也为O(logn).当然，如果您有一个等式和顺序不同的键类型，这可能会导致问题.
是的，如果你没有足够的内存来存储哈希映射，你会有麻烦...但不管你使用什么样的数据 struct ，这都是事实.