java - 存储在同一个存储桶中的元素在重新哈希后是否可以重新分配到单独的存储桶中？

Question

到目前为止，我知道在 HashMap 中重新哈希后，所有条目都会使用新的表长度重新哈希。但我想知道发生碰撞时会发生什么。

例如

Map<String, String> map = new HashMap<>(5); 
map.put("a", "ape");
map.put("b", "bird"); 
map.put("c", "chicken");

假设它们有不同的哈希码，但是“b”和“c”在内部哈希后存储在同一个桶中。

现在我将插入第四个条目以达到负载因子，从而重新哈希表:

map.put("d", "dynamite");

是否可以将存在冲突的条目存储在单独的存储桶中，或者它们始终会在一起(根据我所读到的内容以相反的顺序)？

我认为标题的答案是否定的，因为我将得到 "b" 和 "c" 相同的内部哈希，但我我不确定。

Answer 1

您可以通过两种方式在此处查看冲突。

其中之一是两个对象从 hashCode() 返回相同的值方法。在这种情况下，无论哈希表数组的大小如何，它们最终都会位于同一个存储桶中。

另一种情况是，两个对象具有不同的哈希码，但由于数组大小小于 hashCode() 的 2³² 个唯一值，最终位于同一个存储桶中。理论上可以返回。通常，原始哈希码值将以数组大小为模，用于为条目找到正确的存储桶。假设初始数组大小为 16，对象 A 的哈希码为 3，对象 B 的哈希码为 19。由于 19 % 16 == 3，对象 A 和对象 B 将最终位于同一个存储桶中。如果您现在将数组大小调整为 18，则对象 A 最终将位于存储桶 3 % 20 == 3 中，但对象 B 将最终位于存储桶 19 % 20 == 19 中。因此，现在它们位于不同的存储桶中，这回答了中提出的问题标题带有"is"。