当负载因子大于 1 时，如何填充 java 中的 hashMap？
How is a hashMap in java populated when load factor is more than 1?
我尝试创建一个包含以下详细信息的 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");
我发现一些放在不同桶中的值现在放在一个已经包含一些值的桶中，即使它们的哈希值不同。任何人都可以帮我理解吗？
谢谢
在您的第二个测试中，初始容量为 16，负载因子为 2。这意味着 HashMap 将使用 16 个元素的数组来存储条目（即有 16 个桶），并且只有当 Map 中的条目数达到 32 (16 * 2) 时，此数组才会调整大小。
这意味着一些具有不同 hashCode 的键必须存储在同一个桶中，因为桶的数量 (16) 小于条目总数（在您的情况下为 20）。
将键分配给存储桶分 3 步计算：
- 首先调用
hashCode 方法。
- 然后在
hashCode 上应用了一个附加功能，以减少可能由错误的 hashCode 实现造成的损害。
- 最后对上一步的结果进行取模运算，得到一个介于
0和capacity - 1之间的数。
第 3 步是具有不同 hashCode 的键可能最终出现在同一个桶中。
因此，如果您在未指定初始大小和加载因子的情况下初始化 HashMap，它将以大小 16 和加载因子 0.75 进行初始化。这意味着，一旦 HashMap 至少（初始大小 * 加载因子）大，即 12 个元素大，它将被重新散列，这意味着，它将增长到大约两倍大小，所有元素将被重新添加。
您现在将加载因子设置为 2，这意味着，现在 Map 只有在至少填充了 32 个元素时才会重新散列。
现在发生的是具有相同 hash mod bucketcount 的元素将被放入同一个桶中。每个包含一个以上元素的桶都包含一个列表，所有元素都放入其中。现在，当您尝试查找其中一个元素时，它首先会使用哈希找到存储桶。然后它必须遍历该桶中的整个列表以找到具有精确匹配的散列。这是相当昂贵的。
所以最后有一个权衡：重新散列非常昂贵，所以你应该尽量避免它。另一方面，如果你在一个桶中有多个元素，查找会变得非常昂贵，所以你真的应该尽量避免这种情况。所以你需要在这两者之间取得平衡。另一种方法是将初始大小设置得相当高，但这会占用更多未使用的内存。
javadoc 解释：
An instance of HashMap has two parameters that affect its performance:
initial capacity and load factor. The capacity is the number of
buckets in the hash table, and the initial capacity is simply the
capacity at the time the hash table is created. The load factor is a
measure of how full the hash table is allowed to get before its
capacity is automatically increased. When the number of entries in the
hash table exceeds the product of the load factor and the current
capacity, the hash table is rehashed (that is, internal data
structures are rebuilt) so that the hash table has approximately twice
the number of buckets.
As a general rule, the default load factor (.75) offers a good
tradeoff between time and space costs. Higher values decrease the
space overhead but increase the lookup cost (reflected in most of the
operations of the HashMap class, including get and put). The expected
number of entries in the map and its load factor should be taken into
account when setting its initial capacity, so as to minimize the
number of rehash operations. If the initial capacity is greater than
the maximum number of entries divided by the load factor, no rehash
operations will ever occur.
默认初始容量为16，负载因子为0.75。
因此，当条目数超过 12 (16 * 0.75) 时，其容量将增加到 32，并重新散列 hashtable。这就是为什么在第一种情况下，每个不同的元素都有自己的桶。
在你的第二种情况下，只有当条目数超过 32(16*2) 时，散列 table 才会调整大小。即使元素具有不同的哈希码值，在计算 hashcode%bucketsize 时，它也可能会发生冲突。这就是您在同一个桶中看到多个元素的原因
让我们用例子来验证一下 -
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 个桶中）
我尝试创建一个包含以下详细信息的 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");
我发现一些放在不同桶中的值现在放在一个已经包含一些值的桶中，即使它们的哈希值不同。任何人都可以帮我理解吗？
谢谢
在您的第二个测试中，初始容量为 16，负载因子为 2。这意味着 HashMap 将使用 16 个元素的数组来存储条目（即有 16 个桶），并且只有当 Map 中的条目数达到 32 (16 * 2) 时，此数组才会调整大小。
这意味着一些具有不同 hashCode 的键必须存储在同一个桶中，因为桶的数量 (16) 小于条目总数（在您的情况下为 20）。
将键分配给存储桶分 3 步计算：
- 首先调用
hashCode方法。 - 然后在
hashCode上应用了一个附加功能，以减少可能由错误的hashCode实现造成的损害。 - 最后对上一步的结果进行取模运算，得到一个介于
0和capacity - 1之间的数。
第 3 步是具有不同 hashCode 的键可能最终出现在同一个桶中。
因此，如果您在未指定初始大小和加载因子的情况下初始化 HashMap，它将以大小 16 和加载因子 0.75 进行初始化。这意味着，一旦 HashMap 至少（初始大小 * 加载因子）大，即 12 个元素大，它将被重新散列，这意味着，它将增长到大约两倍大小，所有元素将被重新添加。
您现在将加载因子设置为 2，这意味着，现在 Map 只有在至少填充了 32 个元素时才会重新散列。
现在发生的是具有相同 hash mod bucketcount 的元素将被放入同一个桶中。每个包含一个以上元素的桶都包含一个列表，所有元素都放入其中。现在，当您尝试查找其中一个元素时，它首先会使用哈希找到存储桶。然后它必须遍历该桶中的整个列表以找到具有精确匹配的散列。这是相当昂贵的。
所以最后有一个权衡：重新散列非常昂贵，所以你应该尽量避免它。另一方面，如果你在一个桶中有多个元素，查找会变得非常昂贵，所以你真的应该尽量避免这种情况。所以你需要在这两者之间取得平衡。另一种方法是将初始大小设置得相当高，但这会占用更多未使用的内存。
javadoc 解释：
An instance of HashMap has two parameters that affect its performance: initial capacity and load factor. The capacity is the number of buckets in the hash table, and the initial capacity is simply the capacity at the time the hash table is created. The load factor is a measure of how full the hash table is allowed to get before its capacity is automatically increased. When the number of entries in the hash table exceeds the product of the load factor and the current capacity, the hash table is rehashed (that is, internal data structures are rebuilt) so that the hash table has approximately twice the number of buckets.
As a general rule, the default load factor (.75) offers a good tradeoff between time and space costs. Higher values decrease the space overhead but increase the lookup cost (reflected in most of the operations of the HashMap class, including get and put). The expected number of entries in the map and its load factor should be taken into account when setting its initial capacity, so as to minimize the number of rehash operations. If the initial capacity is greater than the maximum number of entries divided by the load factor, no rehash operations will ever occur.
默认初始容量为16，负载因子为0.75。
因此，当条目数超过 12 (16 * 0.75) 时，其容量将增加到 32，并重新散列 hashtable。这就是为什么在第一种情况下，每个不同的元素都有自己的桶。
在你的第二种情况下，只有当条目数超过 32(16*2) 时，散列 table 才会调整大小。即使元素具有不同的哈希码值，在计算 hashcode%bucketsize 时，它也可能会发生冲突。这就是您在同一个桶中看到多个元素的原因
让我们用例子来验证一下 -
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 个桶中）