当加载因子大于1时，java中的hashMap是如何填充的？_java

我尝试使用以下详细信息创建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");

我看到每个输入都放在一个不同的桶里。 这意味着为每个键计算了不同的哈希码。 现在，如果我按如下方式修改我的代码： -

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将被放入同一个存储桶中。 每个包含多个元素的存储桶都包含一个列表，其中包含所有元素。 现在，当您尝试查找其中一个元素时，它首先使用哈希查找存储桶。 然后它必须迭代该存储桶中的整个列表以找到具有完全匹配的哈希。 这是非常昂贵的。

所以最后需要权衡一下：重新划分非常昂贵，所以你应该尽量避免它。 另一方面，如果存储桶中有多个元素，则查找会非常昂贵，因此您应该尽量避免使用它。 所以你需要在这两者之间取得平衡。 另一种方法是将初始大小设置得相当高，但这会占用更多未使用的内存。

在第二次测试中，初始容量为16，加载因子为2.这意味着HashMap将使用16个元素的数组来存储条目（即有16个桶），并且此数组仅在数量时调整大小地图中的条目达到32（16 * 2）。

这意味着具有不同hashCodes的一些密钥必须存储在同一个桶中，因为桶的数量（16）小于条目的总数（在您的情况下为20）。

桶的密钥分配分3步计算：

首先调用hashCode方法。
然后在hashCode上应用附加函数以减少可能由错误hashCode实现引起的损害。
最后，对前一步的结果应用模运算，以得到介于0和capacity - 1之间的数字。

第三步是具有不同hashCode的密钥可能最终在同一个桶中。

让我们用例子检查一下 -

i）在第一种情况下， load factor为0.75f， initialCapacity为16，这意味着当HashMap的桶数达到16 * 0.75 = 12时，将发生数组调整大小。

现在，每个密钥具有不同的HashCode因此HashCode modulo 16是唯一的，这导致所有前12个条目进入不同的桶，之后发生调整大小，并且当放入新条目时它们也最终在不同的桶中（ HashCode modulo 32是唯一的）。

ii）在第二种情况下， load factor是2.0f，这意味着当没有时会发生调整大小。 桶的数量达到16 * 2 = 32.您继续将条目放入地图中，并且从不调整大小（对于20个条目）使多个条目发生冲突。

所以，简而言之，在第一个例子中 - 前12个条目的HashCode modulo 16和所有条目的HashCode modulo 32是唯一的，而在第二种情况下，对于所有不是唯一的条目它总是HashCode modulo 16 （不能像所有20个条目一样）容纳16个水桶）

javadoc解释：

HashMap的一个实例有两个影响其性能的参数：初始容量和负载因子。 容量是哈希表中的桶数，初始容量只是创建哈希表时的容量。 加载因子是在自动增加容量之前允许哈希表获取的完整程度的度量。 当哈希表中的条目数超过加载因子和当前容量的乘积时，哈希表将被重新哈希（即，重建内部数据结构），以便哈希表具有大约两倍的桶数。

作为一般规则，默认加载因子（.75）在时间和空间成本之间提供了良好的权衡。 较高的值会减少空间开销，但会增加查找成本（反映在HashMap类的大多数操作中，包括get和put）。 在设置其初始容量时，应考虑映射中的预期条目数及其加载因子，以便最小化重新散列操作的数量。 如果初始容量大于最大条目数除以加载因子，则不会发生重新加载操作。

默认情况下，初始容量为16，负载因子为0.75。 因此，当条目数超过12 (16 * 0.75) ，其容量增加到32并且散列表被重新散列。 这就是为什么在你的第一种情况下，每个不同的元素都有自己的桶。

在第二种情况下，只有当条目数超过32(16*2) ，才会调整哈希表的大小。 即使元素具有不同的哈希码值，当计算哈希码％bucketsize时，它也可能发生冲突。 这就是你在同一个桶中看到多个元素的原因

当加载因子大于1时，java中的hashMap是如何填充的？

问题描述

1楼

2楼

3楼

4楼