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

基于哈希表的 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中的源码。

也就是说,当链表的长度达到给出的阈值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().

		//声明两个Node数组,JDK1.8是Node 1.8之前使用的Entry
        Node[] tab; Node 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[] tab; Node 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 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)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[] resize() {
        Node[] 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