我们习惯说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) - 但这通常是您在考虑使用哪些算法和数据结构时应该假设的。
在 JDK 8 中，HashMap经过调整，如果可以比较键进行排序，那么任何密集填充的桶都会被实现为树，这样即使有很多具有相同哈希码的条目，复杂度也是 O(log n)。当然，如果您的键类型的相等性和顺序不同，这可能会导致问题。
是的，如果你没有足够的内存来存储哈希映射，你就会遇到麻烦......但无论你使用什么数据结构，这都是事实。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
