深入理解HashMap的底层原理(二)

- 日理万妓 2023-07-15 11:25 34阅读 0赞

> 基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作，并允许使用 null 值和 null 键。（除了非同步和允许使用 null 之外，HashMap 类与 Hashtable 大致相同。）此类不保证映射的顺序，特别是它不保证该顺序恒久不变。 此实现假定哈希函数将元素适当地分布在各桶之间，可为基本操作（get 和 put）提供稳定的性能。迭代 collection 视图所需的时间与 HashMap 实例的“容量”（桶的数量）及其大小（键-值映射关系数）成比例。所以，如果迭代性能很重要，则不要将初始容量设置得太高（或将加载因子设置得太低）  
> –摘自《百度百科》

## 前言 ##

一步一步，一小步，一大步，我相信知识的积累会有一个质的飞跃。  
写此文章的目的是为了记录自己的学习。记录在此也是希望各位业界的前辈们如果发现了不正确的地方，希望您能及时批评指正，在此感谢!

## 本篇内容 ##

在上一篇的文章中,粗略的介绍了HashMap中几个主要的基本概念。  
有感兴趣的朋友可以去支持一下。如若发现了问题,也希望您能及时纠正。  
本篇的内容是接着上一篇文章继续深入了解一下HashMap的扩容机制。  
既然了解到扩容,我们当然离不开数据结构。JDK1.8之前HashMap由组数+链表组成，引入的链表的目的主要是为了解决哈希冲突(当我put的时候HashMap会将我们的key进行哈希算法,然后将此哈希值作为索引存入数组中,既然是随机生成的数就会存在概率性,当两个key的哈希相等时此时就会引入链表)，***在JDK1.8之后对于解决Hash冲突有了较大的变化，当链表长度大于阈值(默认为8)并且当前数组长度大于64时候，此时该索引上的数据转化为红黑树存储，否则还是进行扩容***

> JDK1.8中必须是同时满足以上两个条件。  
> 先看看JDK中的源码。

![当链表数量达到阈值时会转为红黑树][20200316194357587.jpg]  
![会再次进行判断长度是否达到MIN\_TREEIFY\_CAPACITY][MIN_TREEIFY_CAPACITY]  
也就是说,当链表的长度达到给出的阈值8时,会调用treeifyBin方法,在treeifyBin方法中会再次进行一次判断,如果不满足最小数组长度会调用resize()方法进行扩容。  
本篇文章主要是针对resize()，先了解一下HashMap的扩容是如何执行的。

### 一、当我们put(k,v)的时候发生了什么？ ###

//这是JDK中的方法。
    /** * 参数： * hash(key):把key进行hash计算,用来当做索引 * key | value : 传入键值对 * onlyIfAbsent:boolean类型,如果为true则不能对值进行覆盖 * evict:如果为false表示处于创建模式。 * onlyIfAbsent和evict是一个判断的依据不需要我们进行传参,因此我们也只需要它的用处即可。 */
    public V put(K key, V value) { 
            return putVal(hash(key), key, value, false, true);
        }

我们可以看到在put方法的内部实际上是调用了putVal()方法。

### 二、putVal（）是如何扩容的. ###

实际上进行扩容操作的并不是putVal()，而是resize(),咱们在阅读源码的习惯也是逐级往下挖掘。所以我们就遵循这个逻辑。首先来看一下putVal()中是如何调用Resize().  
![在这里插入图片描述][20200316200401389.png]

//声明两个Node数组,JDK1.8是Node 1.8之前使用的Entry
            Node<K,V>[] tab; Node<K,V> p; int n, i;
    		//新数组,进行初始化得到数组
            if ((tab = table) == null || (n = tab.length) == 0)
    		//得到初始化数组和长度,第一次扩容
            n = (tab = resize()).length;

**pubVal方法中的内容当然不止于此，在此之前我们需要了解resize()的扩容机制，接下来就烦请大家往下挪一挪先看第三节的内容（若有不便，还请多多海涵.）**

下面再来看看putVal方法,该方法大部分是普通的逻辑没有特别之处,注意的是在最后会再次调用resize（）。

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                       boolean evict) { 
    		//声明两个Node数组,JDK1.8是Node 1.8之前使用的Entry
            Node<K,V>[] tab; Node<K,V> p; int n, i;
    		//新数组,进行初始化得到数组
            if ((tab = table) == null || (n = tab.length) == 0)
    		//得到初始化数组和长度
                n = (tab = resize()).length;
            if ((p = tab[i = (n - 1) & hash]) == null)//根据hash值获取该节点是否为空,是的话新建一个节点
                tab[i] = newNode(hash, key, value, null);
            else { 
    		
                Node<K,V> e; K k;
    			//说明hash值入新put的元素hash相等,key相等
                if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))
                    e = p;
    			//符合红黑树则转为红黑树
                else if (p instanceof TreeNode)
                    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
                else { 
                    for (int binCount = 0; ; ++binCount) { 
    					//表示此处只有一个头节点
                        if ((e = p.next) == null) { 
    						//那么直接新建一个节点
                            p.next = newNode(hash, key, value, null);
    						//如果链表的长度大于8,则将链表转为红黑树
                            if (binCount >= TREEIFY_THRESHOLD - 1) 
                                treeifyBin(tab, hash);
                            break;
                        }
                        if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                            break;
    					//更新p
                        p = e;
                    }
                }
    			//如果存在那么就覆盖
                if (e != null) {  
                    V oldValue = e.value;
    				// 判断是否允许覆盖，并且value是否为空
                    if (!onlyIfAbsent || oldValue == null)
                        e.value = value;
    					 // 回调以允许LinkedHashMap后置操作
                    afterNodeAccess(e);
                    return oldValue;
                }
            }
            ++modCount; // 更改操作次数
            if (++size > threshold) // 大于临界值
    		// 将数组大小设置为原来的2倍，并将原先的数组中的元素放到新数组中
                // 因为有链表，红黑树之类，因此还要调整他们
                resize(); //扩容
    		  // 回调以允许LinkedHashMap后置操作
            afterNodeInsertion(evict);
            return null;
        }

### 三、resize（）的扩容。 ###

final Node<K,V>[] resize() { 
            Node<K,V>[] oldTab = table; //未使用put之前的原始数组
            int oldCap = (oldTab == null) ? 0 : oldTab.length; //第一次初始化时为0，否则返回原始数组容量
            int oldThr = threshold; //临界值,
            int newCap, newThr = 0; //声明一个新的容量和阈值
            if (oldCap > 0) {  //原始数组长度大于0
    		//原始容量大于等于最大容量,则返回原数组，并且扩容临界值保持不变,否则进行扩容一倍
                if (oldCap >= MAXIMUM_CAPACITY) { 
                    threshold = Integer.MAX_VALUE;
                    return oldTab;
                }
    			//oldCap<<1 扩大一倍长度小于最大容量并且原始数组要大于等于默认容量
    			//将临界值翻倍
                else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                         oldCap >= DEFAULT_INITIAL_CAPACITY)
                    newThr = oldThr << 1; // double threshold
            }
    			
            else if (oldThr > 0) // 将初始容量设置为阈值
                newCap = oldThr;
            else {            
    			//第一次初始化使用默认的初始容量和阈值
                newCap = DEFAULT_INITIAL_CAPACITY;
                newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
            }
    		//第一次扩容初始化阈值
            if (newThr == 0) { 
                float ft = (float)newCap * loadFactor;
                newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                          (int)ft : Integer.MAX_VALUE);
            }
            threshold = newThr;
    		/* 上面的操作的结果就是以下两点 1.如果是第一次进行put的时候(新数组)： 1.1、如果初始化的时候带了参数 （HashMap(int initialCapacity, float loadFactor)）， 那么newCap就是你的initialCapacity参数 threshold就是 (int)(initialCapacity*loadFactor) 1.2、否则就按默认的算 initialCapacity = 16，threshold = 12 2.如果已经有元素了，那么直接扩容2倍，如果 oldCap >= DEFAULT_INITIAL_CAPACITY了，那么threshold也扩大两倍 */
    		//创建hash表
            @SuppressWarnings({ "rawtypes","unchecked"})
            Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
            table = newTab;
            if (oldTab != null) { 
    			//变量hash表
                for (int j = 0; j < oldCap; ++j) { 
                    Node<K,V> e;//临时节点
                    if ((e = oldTab[j]) != null) {  //如果旧的hash表当前存在节点,赋值给临时节点e
                        oldTab[j] = null;//删除旧的节点
                        if (e.next == null)//取出来的节点不存在下一个值,将该节点赋值给新的数组,并重新计算hash值作为key,e.next == null 也就是说该节点上只有这一个值,不存在链表
                            newTab[e.hash & (newCap - 1)] = e;
                        else if (e instanceof TreeNode) //转为红黑树
                            ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                        else {  // 否则维护现有的链表
                            Node<K,V> loHead = null, loTail = null;
                            Node<K,V> hiHead = null, hiTail = null;
                            Node<K,V> next;
                            do { 
                                next = e.next;
                                if ((e.hash & oldCap) == 0) {  //一个判断的依据,可以理解为索引位置不变,不做位移
                                    if (loTail == null) //初次赋值 将桶中的头结点添加到lohead中
                                        loHead = e;
                                    else //链表追加
                                        loTail.next = e;
                                    loTail = e; //lotail
                                }
                                else { 
                                    if (hiTail == null)
                                        hiHead = e;
                                    else
                                        hiTail.next = e;
                                    hiTail = e;
                                }
                            } while ((e = next) != null); //该链表中还存在next时继续遍历
    						//遍历结束后
                            if (loTail != null) { 
    							//在lo中的元素索引位置不变,赋值给新数组
                                loTail.next = null;
                                newTab[j] = loHead;
                            }
                            if (hiTail != null) { 
                                hiTail.next = null;
    							//在hi中的元素位置改变,为原始容量+原始索引
                                newTab[j + oldCap] = hiHead;
                            }
                        }
                    }
                }
            }
            return newTab;
        }

**对以上方法的解释（从上到下说 属于个人见解若有不对,希望及时指出,建议和源码一块看）：**

/** * 1. * 如果oldCap=0 说明是一个新的数组,否则是一个有长度的数组。 * oldTable是我们原始数组(put之前的) */
    int oldCap = (oldTab == null) ? 0 : oldTab.length
    /** * 2. * oldCap大于0说明是有长度的数组。 * 判断为true:原始容量大于等于最大容量,则返回原数组，并且扩容临界值保持不变,否则进行扩容一倍 * 为false：oldCap<<1 扩大一倍长度小于最大容量并且原始数组要大于等于默认容量，将临界值翻倍 * 关于位运算符这里简单说下，大佬可以忽略 * 例如:十进制的2 * 0000 0010 * <<1 0000 0100 ->十进制4 * <<1 0000 1000 ->十进制8 * <<1 0001 0000 ->十进制16 * 可以总结一下以上规律: * 移一次:2*2->移一次:2*2*2->移一次:2*2*2*2等价于 * 2*(2^1)->2*(2^2)->2*(2^3).....2*(2^n) * 明白这个之后对于<<1结果是扩大一倍相信应该不难理解了。 */
    if (oldCap > 0) { return "为了不占位置省略代码,可以对照上面源码看,建议用idea打开源码观看"}
    /** * 3. * 既然是else if 说明 if(oldCap>0)为false，即:这是一个新的数组 * 将初始容量设置为阈值(此时的阈值还没有与加载因子相乘) */
    else if (oldThr > 0)
    else{ 
    	//第一次初始化和第一次扩容
    }
    /** * 4.以下重点 * 主要对if(oldTab != null){}进行说明,大致的意思在本节开始都做了注释。下面会着重说一下 * 重要的部分 */
    //原始数组不为空
    if (oldTab != null) { 
    	//1.
    	 else if (e instanceof TreeNode) //转为红黑树
             ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
      	 else { 
    		//此处是扩容的重点,
    		/** * 扩容之后就是将现有数组节点的内容移到新的数组中,链表的设计原则是继续上下节点的 * 信息。那么HashMap是如何实现的呢? * 在此处先举个例子,我们在上面的也可以看到HashMap中的索引的计算是 * [e.hash&(newcap-1)] * 扩容之后的大小时原来的2倍,假设现在的容量是16扩容到32,原数组中的索引只会有2 * 种可能,变或不变。 * 不变的索引:存放在低拉链表中,也就中else中声明的 * (Node<K,V> loHead = null, loTail = null),低拉链表中的数据会转移到新数组中且 * 索引保持不变 * 变的索引:存放在高拉链表中,也就是esle中声明的 * (Node<K,V> hiHead = null, hiTail = null),高拉链表中的数据在新数组中且新索引 * 是旧的索引+oldCap旧的容量 * --假设旧的节点中某个节点的hash是15,旧的容量是16.(e.hash & oldCap) == 0肯定是 * true为什么呢,对& 与做个说明(大佬可以忽略此处)：两个都为1才是1 * 0000 0010 ->属性2的次幂值,都只有一个高位1,其余位肯定是0. * 16-> 0001 0000 * 15-> 0000 1111 * 0000 0000 * 如果(e.hash & oldCap) == 0为false说明此索引的位置需要发生变化,发生变化的索引 * 位置是旧的索引15+旧的容量16 = 31 位置相同 * 在此处你能发现 [e.hash&(newcap-1)]的妙处了,为什么不是[e.hash&(oldcap-1)] * 假设hash此时为16,[e.hash&(oldcap-1)] = 0 [e.hash&(newcap-1)] = 16 * 这样处理在扩容的同时解决了hash的冲突并且可以很快的计算出新的索引位置. * 不用纠结为什么要(e.hash & oldCap) == 0这样判断,因为你不得不承认JDK作者位运算符用的真的给跪了. * 在遍历结束后会将在lo中的元素索引位置不变,赋值给新数组 * 在hi中的元素位置改变,为原始容量+原始索引 * * 再回到第二节中继续看putVal方法 * */
    		
    	}
    }

上一篇:[深入理解HashMap的底层原理(一)][HashMap]粗略的介绍了HashMap中的主要变量和方法,有兴趣的朋友可以帮忙一起探讨指正不足之处.

如果有不正确,希望大佬们能及时纠正,再次感谢.

[20200316194357587.jpg]: /images/20230528/ffa05e85ef514e15b1232097e6992d20.png
[MIN_TREEIFY_CAPACITY]: /images/20230528/4262d553219742fa8d2158c2262a5182.png
[20200316200401389.png]: /images/20230528/a4274a9925794174a8fe243dd4b18a34.png
[HashMap]: https://blog.csdn.net/qq_40409260/article/details/104813519