前言
1. 本文根据 jdk1.8 源码来分析 HashMap 的容量取值问题;
2. 本文有做 jdk1.8 HashMap.resize()扩容方法的源码解析: 见下文 "一, 3. 扩容: 同样需要保证扩容后的容量是 2 的 n 次幂";
3. 目录:
一, jdk1.8 中, 对 "HashMap 的容量一定是 2 的 n 次幂" 做了严格控制
1. 默认初始容量
2. 使用 HashMap 的有参构造函数来自定义容量的大小(保证容量是 2 的 n 次幂)
3. 扩容: 同样需要保证扩容后的容量是 2 的 n 次幂 ( jdk1.8 HashMap.resize() 扩容方法的源码解析)
二, 为什么 HashMap 的容量一定要是 2 的 n 次幂? 或者说, 保证 "HashMap 的容量一定是 2 的 n 次幂" 有什么好处?
1. 关系到元素在桶中的位置计算问题
2. 关系到扩容后元素在 newCap 中的放置问题
2.1 源码解析
2.2 深入分析(含图解)
一, jdk1.8 中, 对 "HashMap 的容量一定要是 2 的 n 次幂" 做了严格控制
1. 默认初始容量:
- /**
- * The default initial capacity - MUST be a power of two.(默认初始容量 -- 必须是 2 的 n 次幂.)
- */
- static final int DEFAULT_INITIAL_CAPACITY = 1 <<4; // aka 16(16 = 2^4)
2. 使用 HashMap 的有参构造函数来自定义容量的大小(保证容量是 2 的 n 次幂):
HashMap 总共有 4 个构造函数, 其中有 2 个构造函数可以自定义容量的大小:
1HashMap(int initialCapacity): 底层调用的是2HashMap(int initialCapacity, float loadFactor)构造函数
- public HashMap(int initialCapacity) {
- this(initialCapacity, DEFAULT_LOAD_FACTOR);
- }
- 2HashMap(int initialCapacity, float loadFactor)
- public HashMap(int initialCapacity, float loadFactor) {
- if (initialCapacity < 0)
- throw new IllegalArgumentException("Illegal initial capacity:" + initialCapacity);
- if (initialCapacity> MAXIMUM_CAPACITY)
- initialCapacity = MAXIMUM_CAPACITY;
- if (loadFactor <= 0 || Float.isNaN(loadFactor))
- throw new IllegalArgumentException("Illegal load factor:" + loadFactor);
- this.loadFactor = loadFactor;
- this.threshold = tableSizeFor(initialCapacity);//tableSizeFor(initialCapacity)方法是重点!!!
- }
这里有个问题: 使用1或2构造函数来自定义容量时, 怎么能够保证传入的容量一定是 2 的 n 次幂呢?
答案就在标记出来的 tableSizeFor(initialCapacity)方法中:
- /**
- * Returns a power of two size for the given target capacity.
- */
- static final int tableSizeFor(int cap) {
- int n = cap - 1;
- n |= n>>> 1;
- n |= n>>> 2;
- n |= n>>> 4;
- n |= n>>> 8;
- n |= n>>> 16;
- return (n <0) ? 1 : (n>= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
- }
上面这段代码的作用:
假如你传的 cap 是 5, 那么最终的初始容量为 8; 假如你传的 cap 是 24, 那么最终的初始容量为 32.
这是因为 5 并非是 2 的 n 次幂, 而大于等于 5 且距离 5 最近的 2 的 n 次幂是 8(8 = 2^3); 同样的, 24 也并非 2 的 n 次幂, 大于等于 24 且距离 24 最近的 2 的 n 次幂是 32(32 = 2^5).
假如你传的 cap 是 64, 那么最终的初始容量就是 64, 因为 64 是 2^6, 它就是等于 cap 的最小 2 的 n 次幂.
总结起来就一句话: 通过位移运算, 找到大于或等于 cap 的 最小 2 的 n 次幂.
jdk1.7 的初始容量处理机制和上面 jdk1.8 具有相同的作用, 但 1.7 的代码好懂很多:
- public HashMap(int initialCapacity, float loadFactor) {
- ......
- int capacity = 1;
- while (capacity <initialCapacity) {
- capacity <<= 1;
- }
- ......
- }
3. 扩容: 同样需要保证扩容后的容量是 2 的 n 次幂 ( jdk1.8 HashMap.resize() 扩容方法的源码解析)
resize()扩容方法主要做了三件事(这里这里重点讲前两件事, 第三件事在下文的 "三, 2." 中讲):
1计算新容量(新桶) newCap 和新阈值 newThr;
2根据计算出的 newCap 创建新的桶数组 table, 并对 table 做初始化;
3将键值对节点重新放到新的桶数组里;
- final Node<K,V>[] resize() { // 扩容
- //---------------- -------------------------- 1. 计算新容量(新桶) newCap 和新阈值 newThr. ---------------------------------
- Node<K,V>[] oldTab = table;
- int oldCap = (oldTab == null) ? 0 : oldTab.length;// 看容量是否已初始化
- int oldThr = threshold;// 下次扩容要达到的阈值. threshold(阈值) = capacity * loadFactor.
- int newCap, newThr = 0;
- if (oldCap> 0) {// 容量已初始化过了: 检查容量和阈值是否达到上限《==========
- if (oldCap>= MAXIMUM_CAPACITY) {//oldCap>= 2^30, 已达到扩容上限, 停止扩容
- threshold = Integer.MAX_VALUE;
- return oldTab;
- }
- // newCap <2^30 && oldCap> 16, 还能再扩容: 2 倍扩容
- else if ((newCap = oldCap <<1) < MAXIMUM_CAPACITY && oldCap>= DEFAULT_INITIAL_CAPACITY)
- newThr = oldThr <<1; // 扩容: 阈值 * 2.(注意: 阈值是有可能越界的)
- }
- // 容量未初始化 && 阈值> 0.
- //[啥时会满足层判断: 使用 HashMap(int initialCapacity, float loadFactor)或 HashMap(int initialCapacity)构造函数实例化 HashMap 时, threshold 才会有值.]
- else if (oldThr> 0)
- newCap = oldThr;// 初始容量设为阈值
- else { // 容量未初始化 && 阈值 <= 0 :
- //[啥时会满足这层判断:1使用无参构造函数实例化 HashMap 时;2在 "if (oldCap> 0)" 判断层 newThr 溢出了.]
- newCap = DEFAULT_INITIAL_CAPACITY;
- newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
- }
- if (newThr == 0) {// 什么情况下才会进入这个判断框: 前面执行了 else if (oldThr> 0), 并没有为 newThr 赋值, 就会进入这个判断框.
- float ft = (float)newCap * loadFactor;
- newThr = (newCap <MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE);
- }
- threshold = newThr;
- //------------------------------------------------------2. 扩容:------------------------------------------------------------------
- @SuppressWarnings({"rawtypes","unchecked"})
- Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];// 扩容
- table = newTab;
- //--------------------------------------------- 3. 将键值对节点重新放到新的桶数组里.------------------------------------------------
- ......// 此处源码见下文 "二, 2."
- return newTab;
- }
通过 resize()扩容方法的源码可以知道: 每次扩容, 都是将容量扩大一倍, 所以新容量依旧是 2 的 n 次幂. 如 oldCap 是 16 的话, 那么 newCap 则为 32.
通过上面三点可以确定, 不论是默认初始容量, 还是自定义容量大小, 又或者是扩容后的容量, 都必须保证一定是 2 的 n 次幂.
二, 为什么 HashMap 的容量一定要是 2 的 n 次幂? 或者说, 保证 "HashMap 的容量一定是 2 的 n 次幂" 有什么好处?
原因有两个:
1. 关系到元素在桶中的位置计算问题:
简单来讲, 一个元素放到哪个桶中, 是通过 "hash % capacity" 取模运算得到的余数来确定的(注:"元素的 key 的哈希值" 在本文统一简称为 "hash").
hashMap 用另一种方式来替代取模运算 -- 位运算:(capacity - 1) & hash. 这种运算方式为什么可以得到跟取模一样的结果呢? 答案是 capacity 是 2 的 N 次幂.(计算机做位运算的效率远高于做取模运算的效率, 测试见: https://www.cnblogs.com/laipimei/p/11316812.html)
证明取模和位运算结果的一致性:
2. 关系到扩容后元素在 newCap 中的放置问题:
扩容后, 如何实现将 oldCap 中的元素重新放到 newCap 中?
我们不难想到的实现方式是: 遍历所有 Node, 然后重新 put 到新的 table 中, 中间会涉及计算新桶位置, 处理 hash 碰撞等处理. 这里有个不容忽视的问题 -- 哈希碰撞. 在元素 put 进桶中时, 就已经处理过了哈希碰撞问题: 哈希值一样但通过 equals()比较确定内容不同的元素, 会在同一个桶中形成链表, 链表长度>=8 时将链表转为红黑树; 扩容时, 需要重新处理这些元素的哈希碰撞问题, 如果数据量一大....... 要完......
jdk1.8 用了优雅又高效的方式来处理扩容后元素的放置问题, 下面我们一起来看看 jdk1.8 到底是怎么做的.
2.1 先看 jdk1.8 源码实现:
- final Node<K,V>[] resize() { // 扩容方法
- //---------------- -------------------------- 1. 计算新容量(新桶) newCap 和新阈值 newThr: -------------------------------------------
- ...... // 此处源码见前文 "一, 3."
- //---------------------------------------------------------2. 扩容:------------------------------------------------------------------
- ...... // 此处源码见前文 "一, 3."
- //--------------------------------------------- 3. 将键值对节点重新放到新的桶数组里:------------------------------------------------
- if (oldTab != null) {// 容量已经初始化过了:
- for (int j = 0; j <oldCap; ++j) {// 一个桶一个桶去遍历, j 用于记录 oldCap 中当前桶的位置
- Node<K,V> e;
- if ((e = oldTab[j]) != null) {// 当前桶上有节点, 就赋值给 e 节点
- oldTab[j] = null;// 把该节点置为 null(现在这个桶上什么都没有了)
- if (e.next == null)//e 节点后没有节点了: 在新容器上重新计算 e 节点的放置位置《===== 1桶上只有一个节点
- newTab[e.hash & (newCap - 1)] = e;
- else if (e instanceof TreeNode)//e 节点后面是红黑树: 先将红黑树拆成 2 个子链表, 再将子链表的头节点放到新容器中《===== 2桶上是红黑树
- ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
- else { // preserve order
- Node<K,V> loHead = null, loTail = null;
- Node<K,V> hiHead = null, hiTail = null;
- Node<K,V> next;
- do { // 遍历链表, 并将链表节点按原顺序进行分组《===== 3桶上是链表
- next = e.next;
- if ((e.hash & oldCap) == 0) {//"定位值等于 0" 的为一组:
- if (loTail == null)
- loHead = e;
- else
- loTail.next = e;
- loTail = e;
- }
- else {//"定位值不等于 0" 的为一组:
- if (hiTail == null)
- hiHead = e;
- else
- hiTail.next = e;
- hiTail = e;
- }
- } while ((e = next) != null);
- // 将分好的子链表放到 newCap 中:
- if (loTail != null) {
- loTail.next = null;
- newTab[j] = loHead;// 原链表在 oldCap 的什么位置,"定位值等于 0" 的子链表的头节点就放到 newCap 的什么位置
- }
- if (hiTail != null) {
- hiTail.next = null;
- newTab[j + oldCap] = hiHead; //"定位值不等于 0" 的子节点的头节点在 newCap 的位置 = 原链表在 oldCap 中的位置 + oldCap
- }
- }
- }
- }
- }
- return newTab;
- }
2.2 深入分析(含图解)
1 如果桶上只有一个节点(后面即没链表也没树): 元素直接做 "hash & (newCap - 1)" 运算, 根据结果将元素节点放到 newCap 的相应位置;
2如果桶上是链表:
将链表上的所有节点做 "hash & oldCap" 运算(注意, 这里 oldCap 没有 - 1), 会得到一个定位值("定位值" 这个名字是我自己取的, 为了更好理解该值的意义). 定位值要么是 "0", 要么是 "小于 capacity 的正整数"! 这是个规律, 之所以能得此规律和 capacity 取值一定是 2 的 n 次幂有直接关系, 如果容量不是 2 的 n 次幂, 那么定位值就不再要么是 "0", 要么是 "小于 capacity 的正整数", 它还有可能是其他的数;
根据定位值的不同, 会将链表一分为二得到两个子链表, 这两个子链表根据各自的定位值直接放到 newCap 中:
子链表的定位值 == 0: 则链表在 oldCap 中是什么位置, 就将子链表的头节点直接放到 newCap 的什么位置;
子链表的定位值 == 小于 capacity 的正整数: 则将子链表的头节点放到 newCap 的 "oldCap + 定位值" 的位置;
这么做的好处: 链表在被拆分成两个子链表前就已经处理过了元素的哈希碰撞问题, 子链表不用重新处理哈希碰撞问题, 可以直接将头节点直接放到 newCap 的合适的位置上, 完成 "扩容后将元素放到 newCap" 这一工作. 正因为如此, 大大提高了 jdk1.8 的 HashMap 的扩容效率.
下面将通过画图的形式, 进一步理解 HashMap 到底是怎么将元素放到 newCap 中的.
前面我们说了 jdk1.8 的 HashMap 元素放到哪个桶中哪个位置, 是通过计算 "(capacity - 1) & hash" 得到的余数来确定的. 现在有四个元素, 哈希值分别为 35,27,19,43, 当 "容量 = 8" 时, 计算所得余数都等于 3, 所以这 4 个元素会被放到 table[3] 的位置, 如下图所示:
进行一次扩容后, 现在容量 = 16, 再次计算 "(capacity - 1) & hash" 后, 这四个元素在 newCap 中的位置会有所变化: 要么在原位置, 要么在 "oldCap + 原位置"; 也就是说这四个元素被分成了两组. 如下图所示:
下面我们不用 "(capacity - 1) & hash" 的方式来放置元素, 而是根据 jdk1.8 中 HashMap.resize()扩容方法来放置元素: 先通过 "hash & oldCap" 得到定位值, 再根据定位值同样能将链表一分为二(见证奇迹的时候到了):
"定位值 = 0" 的为一组, 这组元素就是前面将容量从 8 扩到 16 后, 通过 "(newCap - 1) & hash" 计算确定 "放回原位置" 的那些元素;
"定位值 != 0" 的为一组, 这组元素就是扩容后, 确定 "oldCap + 原位置" 的那些元素. 如下图所示:
再将这两组元素节点分别连接成子链表: loHead 是 "定位值 == 0" 的子链表的头节点; hiHead 是 "定位值 != 0" 的子链表的头节点. 如下图所示:
最后, 将子链表的头节点 loHead 放到 newCap 中, 位置和在 oldCap 中的原位置一致; 将另一个子链表的头节点 hiHead 放到 newCap 的 "oldCap + 原位置" 上. 到这里 HashMap 就完成了扩容后将元素重新放到 newCap 中的工作了. 如下图所示:
到这里其实我们已经把 "容量一定是 2 的 n 次幂是 提高扩容后将元素重新放到 newCap 中的效率 的前提" 解释完了, 现在还有一个小小的问题 -- 通过定位值将链表一分为二, 会分得均匀吗? 如果分得很不均匀会怎么样?
众所周知, 要想 HashMap 的查询速度快, 那就得尽量做到让元素均匀地散落到每个桶里. 将链表平均分成两个子链表, 就意味着让元素更均匀地放到桶中了, 增加了元素散列性, 从而提高了元素的查找效率. 那 jdk1.8 又是如何将链表分得更平均的呢? 这关系到两点:1元素的哈希值更随机, 散列;2通过 "hash & oldCap" 中的 oldCap 再次增加元素放置位置的随机性. 第1点和哈希算法的实现直接相关, 这里不细说; 第2点的意思如下:
以 "capacity = 8" 为例, 下面这些都是当 "容量 = 8" 时放在 table[3]位置上的元素的 hash 值. 扩容时做 "hash & oldCap" 运算, 通过下图我们可以发现, oldCap 所在的位上(即倒数第 4 位), 元素的 hash 值在这个位是 0 还是 1 具有随机性.
也就是说, jdk1.8 在元素通过哈希算法使 hash 值已经具有随机性的前提下, 再做了一个增加元素放置位置随机性的运算.
3如果桶上是红黑树:
将红黑树重新放到 newCap 中的逻辑和将链表重新放到 newCap 的的逻辑差不多. 不同之处在于, 重新放后, 会将红黑树拆分成两条由 TreeNode 组成的子链表:
此时, 如果子链表长度 <= UNTREEIFY_THRESHOLD(即 <= 6 ), 则将由 TreeNode 组成的子链表 转换成 由 Node 组成的普通子链表, 然后再根据定位值将子链表的头节点放到 newCap 中;
否则, 根据条件重新将 "由 TreeNode 组成的子链表" 重新树化, 然后再根据定位值将树的头节点放到 newCap 中.
本文不对 "HashMap 扩容时红黑树在 newCap 中的重新放置" 做详细解释, 后面我会再写一篇有关《红黑树转回链表的具体时机》的博文, 在这篇博文中会做详细的源码解析.
一言蔽之: jdk1.8 HashMap 的容量一定要是 2 的 n 次幂, 是为了提高 "计算元素放哪个桶" 的效率, 也是为了提高扩容效率(避免了扩容后再重复处理哈希碰撞问题).
[第一次写这么多字的博文, 如有笔误之处, 还望在评论中帮忙指出, 谢谢~]
来源: https://www.cnblogs.com/laipimei/p/11316140.html