提问者:小点点

JavaHashMap内部数据结构在重新散列期间如何变化?


我正在尝试编写演示代码,以显示当地图大小超过负载因子阈值时,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);

        }


    }

共1个答案

匿名用户

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

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

在所有这些之后,您可以看到小的整数值最终会出现在相应的存储桶中。例如,Integer. value eOf(0).hashCode()是0。在shift-and-XOR之后它将保持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时就不会发生冲突。这让我们可以非常清楚地看到重新散列。对于更典型的对象,哈希码(以及桶)更难预测,因此更难看到冲突以及重新散列发生时发生的变化。