Java HashMap在rehashing过程中的内部数据结构如何变化？

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

        }


    }

- JavaUser

---

为什么不看源代码呢？ - Sharon Ben Asher

结构体不会“改变”！它们被丢弃，然后重新创建完全相同的结构体，只是更大而已。这是一个实现细节，对外部不可见。 - Boris the Spider

如果我们增加桶的大小，那么哈希码就有可能发生变化。我说得对吗？ - JavaUser

你可以通过调试器运行代码，看到在 HashMap 重新哈希后，一些条目被移动到新的桶中。 - Eran

@JavaUser 哈希码不会改变，只是重新映射到（可能）不同的桶中，因为使用模数桶的数量来决定桶。因此哈希码17最初将被映射到桶1，但在第一次重新哈希后，它将被映射到桶17。 - Eran

Answer 1

编写一个程序来演示重新散列并不难，但你必须理解许多关于HashMap内部结构的知识，包括对象哈希码是如何生成的、哈希码与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，这意味着我们可以添加6个映射项，然后才会重新散列。

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也是如此。旧表大小为8时每个桶中第二个条目现在在表格大小为16时哈希到自己的桶中。您可以看到，由于迭代按顺序通过桶进行，因此现在每个桶中都有一个条目。

当然，我精心选择整数值，使碰撞发生于表格大小为8而不是16。这让我们清楚地看到了重新哈希。对于更典型的对象，哈希码（以及桶）更难预测，因此很难看到碰撞和重新哈希时移动的内容。

- Stuart Marks