在重新散列期间Java HashMap内部数据结构如何变化？

Question

我正在尝试编写演示代码，以便在地图大小超过加载因子阈值时显示在Hashmap中发生重新散列。我怎样才能证明内部正在进行重组。此外，我想证明，尽管在重新散列期间旧条目被移动到新桶，我可以使用旧密钥获取旧元素（让我知道我的假设是正确的）。下面是示例代码。

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);

        }


    }

Answer 1

编写程序来演示rehashing并不困难，但你必须了解很多关于HashMap的内部组织，如何生成对象的哈希码，如何将哈希码与HashMap的内部结构相关联，以及它如何影响迭代顺序。

简而言之，HashMap由一系列桶（“表”）组成。每个存储桶都是键值对的链接列表。将密钥哈希值添加到已经占用的存储桶的对添加到该存储桶的链接列表的末尾。通过调用密钥的hashCode()方法确定存储区，将其高位16位右旋无符号移位16（参见source），然后取表格大小的模数。由于表大小始终是2的幂，因此基本上使用掩码（tablesize-1）进行AND运算。 Integer对象的哈希码就是它的整数值。 （source）。最后，HashMap的迭代顺序依次逐步遍历每个桶，并且还顺序地遍历每个桶内的对的链表。

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

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

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时不会发生冲突。这让我们可以非常清楚地看到重新散列。对于更典型的对象，哈希码（以及桶）更难以预测，因此更难以看到冲突以及在发生重新散列时会发生什么变化。