爲什麼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