为什么HashMap中有这么多的空映射？

Question

在做一些调试时，我意识到我使用的HashMap的表有很多空映射，为什么？

例如，HashMap的大小为471.189，当它具有table=HashMap$Entry<K, V>[1048576]时，大约是所需的2.2倍。

Answer 1

hash table (wikipedia)的理论实现将创建大于必要的存储空间以减少散列冲突的可能性。将密钥值添加到散列中时，将进行计算（在密钥值的hashCode()上）以确定密钥将存储在散列表中的哪个位置。这就是哈希表概念能够快速使用的原因，哈希和哈希函数越好，碰撞越少，系统运行速度越快。

哈希表中的空白空间越大，发生碰撞的可能性越小。

如果发生碰撞，就会有一个系统允许以不同的方式存储值，但速度仍然很快，但并不完美。

底线是一个散列表是一个权衡，折衷之间的性能和'浪费'的空间。

当您调试时，您会看到HashMap中的空白空间，这是正常的，甚至是“健康的”。当散列表（HashMap）被填满时，它将'重新映射'数据到一个更大的散列表中。这个重新映射可能会很慢，所以，如果你知道你的哈希表将会增长到一个特定的大小，你应该预先分配空间使用capacity argument on the constructor