HashMap可以为一个密钥提供不同的桶索引吗？

Question

我关心的是检查Java HashMap如何为密钥获取相同的索引.即使它的大小从默认值16扩展到更高的值,因为我们不断添加条目.

我试图重现HashMap的索引算法.

int length=1<<5;
int v=6546546;
int h = new Integer(v).hashCode();
h =h^( (h >>> 20) ^ (h >>> 12));
h=h ^ h >>> 7 ^ h >>> 4;
System.out.println("index :: " + (h & (length-1)));

我为不同的"长度"值运行了我的代码.因此,对于相同的键,我得到不同的索引,因为HashMap的长度发生了变化.我在这里错过了什么？

我的结果:

length=1<<5;
index :: 10

length=1<<15; 

index :: 7082

length=1<<30;  
index :: 6626218

Answer 1

你错过了这样一个事实:每次长度改变时,条目都会重新分配 - 它们会被适当地放入新的存储桶中.这就是为什么当地图扩展时需要一些时间(O(N)) - 所有东西都需要从旧桶复制到新桶.

只要你一次只有一个长度的索引(不是混合),你就没事了.