java - 当负载因子大于1时，如何填充Java中的hashMap？

我试图用以下详细信息创建一个HashMap:

HashMap<Integer,String> test = new HashMap<Integer,String>();
test.put(1, "Value1");
test.put(2, "Value2");
test.put(3, "Value3");
test.put(4, "Value4");
test.put(5, "Value5");
test.put(6, "Value6");
test.put(7, "Value7");
test.put(8, "Value8");
test.put(9, "Value9");
test.put(10, "Value10");
test.put(11, "Value11");
test.put(12, "Value12");
test.put(13, "Value13");
test.put(14, "Value14");
test.put(15, "Value15");
test.put(16, "Value16");
test.put(17, "Value17");
test.put(18, "Value18");
test.put(19, "Value19");
test.put(20, "Value20");

我看到每个输入都放在不同的存储桶中。这意味着为每个 key 计算了不同的哈希码。
现在，
如果我修改我的代码如下:-

HashMap<Integer,String> test = new HashMap<Integer,String>(16,2.0f);
test.put(1, "Value1");
test.put(2, "Value2");
test.put(3, "Value3");
test.put(4, "Value4");
test.put(5, "Value5");
test.put(6, "Value6");
test.put(7, "Value7");
test.put(8, "Value8");
test.put(9, "Value9");
test.put(10, "Value10");
test.put(11, "Value11");
test.put(12, "Value12");
test.put(13, "Value13");
test.put(14, "Value14");
test.put(15, "Value15");
test.put(16, "Value16");
test.put(17, "Value17");
test.put(18, "Value18");
test.put(19, "Value19");
test.put(20, "Value20");

我发现放在不同存储桶中的某些值现在被放入已经包含一些值的存储桶中，即使它们的哈希值不同。谁能帮我理解吗？

谢谢

最佳答案

因此，如果在未指定初始大小和负载因子的情况下初始化HashMap，它将被初始化为大小16和负载因子0.75。这意味着，一旦HashMap至少(初始大小*加载因子)大(因此12个元素大)，它将被重新填充，这意味着它将增长到大约两倍大小，并且所有元素将被重新添加。

现在，您将加载因子设置为2，这意味着，本地图至少填充了32个元素时，它才将被重新映射。

现在发生的是，将具有相同hash mod bucketcount的元素放入相同的存储桶中。每个包含一个以上元素的存储桶都包含一个列表，所有元素都放入其中。现在，当您尝试查找其中一个元素时，它首先使用哈希找到存储桶。然后，它必须遍历该存储桶中的整个列表，以找到具有完全匹配项的哈希。这是非常昂贵的。

因此，最终需要权衡取舍:重新哈希处理非常昂贵，因此您应避免使用它。另一方面，如果存储桶中有多个元素，查找将变得非常昂贵，因此您也应尽量避免这种情况。因此，您需要在两者之间取得平衡。另一种可行的方法是将初始大小设置得很高，但这会占用更多未使用的内存。