时间戳

首页 > 解决方案 > Java HashMap 内部数据结构在 rehash 期间如何变化？

java - Java HashMap 内部数据结构在 rehash 期间如何变化？

问题描述

我正在尝试编写演示代码以显示当映射大小超过负载因子阈值时在 Hashmap 中发生重新散列。我如何证明重新散列正在内部发生。另外我想证明，即使在 rehash 期间旧条目被移动到新存储桶中，我也可以使用旧密钥获取旧元素（让我知道我的假设是正确的）。在示例代码下方。

import java.util.*;

    class RehashDemo{

        public static void main(String[] args){
            Map<Integer,String> numbers = new HashMap<>(10);
            for(int i = 0; i<10;i++){
                numbers.put(i,i+"");
            }
            System.out.println(numbers);

            for(int j = 15; j<=20;j++){
                numbers.put(j,j+"");
            }
            System.out.println(numbers);

        }


    }

标签： javacollectionshashmaphashtablehashcode

解决方案

编写一个演示rehashing的程序并不难，但是你必须了解很多关于HashMap的内部组织，对象的hashcode是如何生成的，hashcode是如何与HashMap的内部结构相关的，以及这如何影响迭代顺序。

简而言之，HashMap 由一组桶（“表”）组成。每个桶都是一个键值对的链表。将其密钥哈希值添加到已被占用的存储桶的对将添加到该存储桶的链表末尾。存储桶是通过调用键的hashCode()方法确定的，将其高位 16 位右无符号移位 16 进行异或运算（参见源代码），然后取表大小的模数。由于表大小始终是 2 的幂，这本质上是与 (tablesize-1) 的掩码进行与运算。对象的哈希码Integer就是它的整数值。（来源）。最后，HashMap 的迭代顺序依次遍历每个桶，也依次遍历每个桶内的对的链表。

毕竟，您可以看到小整数值最终会出现在相应的存储桶中。例如，Integer.valueOf(0).hashCode()为 0。在移位和异或之后它将保持为 0，并且任何表大小的模数都将保持为 0。因此，整数 0 最终在存储桶 0 中，整数 1 最终在存储桶 1 中，依此类推。但不要忘记存储桶是以表大小为模的。因此，如果表大小为 8，则整数 8 将在存储桶 0 中结束。

有了这些信息，我们可以用整数键填充 HashMap，这些键最终会出现在可预测的桶中。让我们创建一个表大小为 8 且默认加载因子为 0.75 的 HashMap，这意味着我们可以在重新散列之前添加六个映射。

Map<Integer, Integer> map = new HashMap<>(8);
map.put(0, 0);
map.put(8, 8);
map.put(1, 1);
map.put(9, 9);
map.put(2, 2);
map.put(10, 10);

{0=0, 8=8, 1=1, 9=9, 2=2, 10=10}

打印出地图（本质上，使用它的toString()方法）按上述顺序迭代地图。我们可以看到 0 和 8 最终在第一个存储桶中，1 和 9 在第二个存储桶中，2 和 10 在第三个存储桶中。现在让我们添加另一个条目：

map.put(3, 3);

{0=0, 1=1, 2=2, 3=3, 8=8, 9=9, 10=10}

迭代顺序变了！添加新映射超出了重新散列的阈值，因此表大小加倍至 16。重新散列已完成，这次的模数为 16 而不是 8。而 0 和 8 之前都在桶 0 中，现在它们在单独的存储桶，因为可用的存储桶数量是原来的两倍。与 1/9 和 2/10 相同。当表大小为 16 时，每个桶中旧表大小为 8 的第二个条目现在散列到其自己的桶中。您可以看到这一点，因为迭代顺序通过桶进行，现在每个桶中有一个条目。

当然，我仔细选择了整数值，以便在表大小为 8 时发生冲突，而在表大小为 16 时不会发生冲突。这让我们非常清楚地看到了重新散列。对于更典型的对象，哈希码（以及存储桶）更难预测，因此更难看到冲突以及重新哈希发生时发生的变化。

推荐阅读