HashMap 的 resize 方法的执行过程?

有两种情况会调用 resize 方法:

  1. 第一次调用 HashMap 的 put 方法时,会调用 resize 方法对 table 数组进行初始化,如果不传入指定值,默认大小为 16。

  2. 扩容时会调用 resize,即 size > threshold 时,table 数组大小翻倍。

每次扩容之后容量都是翻倍。扩容后要将原数组中的所有元素找到在新数组中合适的位置。

当我们把 table[i] 位置的所有 Node 迁移到 newtab 中去的时候:这里面的 node 要么在 newtab 的 i 位置(不变),要么在 newtab 的 i + n 位置。也就是我们可以这样处理:把 table[i] 这个桶中的 node 拆分为两个链表 l1 和 l2:如果 hash & n 0,那么当前这个 node 被连接到 l1 链表;否则连接到 l2 链表。这样下来,当遍历完 table[i] 处的所有 node 的时候,我们得到两个链表 l1 和 l2,这时我们令 newtab[i] = l1,newtab[i + n] = l2,这就完成了 table[i] 位置所有 node 的迁移(rehash),这也是 HashMap 中容量一定的是 2 的整数次幂带来的方便之处。

发表评论