它是一个简单的 Java HashMap，元素如何添加到各自的桶中

Question

它是一个简单的 Java HashMap，如何将元素添加到各自的桶中。我知道 HashMap 调整大小和冲突解决以及良好的分布有助于提高性能这一事实。

在初始容量0到15中，这10个元素占用了6个桶，这10个元素的每个Key hashcode都是唯一的。它如何选择桶和碰撞。

调整大小和检索会发生什么？

Map<String, String> hmap = new HashMap();

hmap.put("One", "One");
hmap.put("Two", "Two");
hmap.put("Three", "Three");
hmap.put("Four", "Four");
hmap.put("Five", "Five");

hmap.put("Six", "Six");
hmap.put("Seven", "Seven");
hmap.put("Eight", "Eight");
hmap.put("Nine", "Nine");
hmap.put("Ten", "Ten");

Answer 1

HashMap 使用 Object#hashCode() as the linked Javadoc notes Returns a hash code value for the object. This method is supported for the benefit of hash tables such as those provided by HashMap. 要查看值，只需在您的键上调用 hashCode()。像，

String[] keyArray = { "One", "Two", "Three", "Four", "Five",
        "Six", "Seven", "Eight", "Nine", "Ten" };
for (String key : keyArray) {
    System.out.printf("%s - %d%n", key, key.hashCode());
}

输出（此处）

One - 79430
Two - 84524
Three - 80786814
Four - 2195782
Five - 2190034
Six - 83138
Seven - 79777773
Eight - 66953327
Nine - 2428114
Ten - 83965

Answer 2

您的 HashMap 有 16 个桶。由于它是一个 HashMap，您首先要获取键的 hashCode()，其中 returns 一个 int 值。

如何将 int 范围内的值分配给 16 个存储桶？一种方法是使用 % 余数运算符。

但是，除法（相对）慢，因此 HashMap 实现确保桶的数量始终是 2 的指数（16、32、64、128，...），因此它可以使用 bit - 掩蔽代替。要屏蔽，请使用按位 & (AND) 运算符和 buckets - 1.

所以，使用你的hmap（实际上，一个LinkedHashMap来保留顺序），你可以在这里看到桶计算：

System.out.println("Key      Hash Code        Bucket");
System.out.println("======= ==========        ======");
for (String key : hmap.keySet())
    System.out.printf("%-7s %10d & 15 = %d%n", '"' + key + '"', key.hashCode(), key.hashCode() & 15);

输出

Key      Hash Code        Bucket
======= ==========        ======
"One"        79430 & 15 = 6
"Two"        84524 & 15 = 12
"Three"   80786814 & 15 = 14
"Four"     2195782 & 15 = 6
"Five"     2190034 & 15 = 2
"Six"        83138 & 15 = 2
"Seven"   79777773 & 15 = 13
"Eight"   66953327 & 15 = 15
"Nine"     2428114 & 15 = 2
"Ten"        83965 & 15 = 13

这里有相当多的碰撞，在桶 2、6 和 13 中。

此处显示的存储桶与您在调试器中看到的不匹配，因为 HashMap 应用了一些额外的技巧来尝试创建更好的分布，但这是应用的基本逻辑。

如果将 HashMap 的大小重新调整为 32 个桶（2 的下一个指数），结果将是：

Key      Hash Code        Bucket
======= ==========        ======
"One"        79430 & 31 = 6
"Two"        84524 & 31 = 12
"Three"   80786814 & 31 = 30
"Four"     2195782 & 31 = 6
"Five"     2190034 & 31 = 18
"Six"        83138 & 31 = 2
"Seven"   79777773 & 31 = 13
"Eight"   66953327 & 31 = 15
"Nine"     2428114 & 31 = 18
"Ten"        83965 & 31 = 29

如您所见，密钥已移至其他存储桶，此处的冲突较少，在存储桶 6 和 18 中。

Answer 3

Hashmap 使用 hashcode 并对其进行和 (&)。这意味着如果你的哈希码是 12345，它需要 & 和 15（即桶数 -1）。简单地说，你可以拿走你所有的钥匙来做这样的事情，看看它在后端做了什么 "System.out.println("四.hashCode()&15);

它是一个简单的 Java HashMap，元素如何添加到各自的桶中

Its a Simple Java HashMap, How elements added in respective buckets

java

collision-detection

hashmap

collision