面试必问的HashMap源码put()方法和resize()方法——基于JDK1.8

目录

一、前言

HashMap太太太常用了，不做过多的介绍。进入正文直接冲源码。
本文主要是基于1.8的HashMap讲述部分源码，主要重点是put()方法和resize()方法

二、 HashMap 的构造方法

/**
* 设置初始化容量，调用的是下面的重载方法
*/publicHashMap(int initialCapacity){this(initialCapacity, DEFAULT_LOAD_FACTOR);}/**
* 设置初始化容量，和加载因子，只是赋值变量，但是并没有初始化数组
*/publicHashMap(int initialCapacity,float loadFactor){if(initialCapacity <0)thrownewIllegalArgumentException("Illegal initial capacity: "+
                                           initialCapacity);if(initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;if(loadFactor <=0||Float.isNaN(loadFactor))thrownewIllegalArgumentException("Illegal load factor: "+
                                           loadFactor);this.loadFactor = loadFactor;//设置数组的长度this.threshold =tableSizeFor(initialCapacity);}/**
* 无参构造方法，只是设置了一个加载阈值，并没有设置初始容量和扩容阈值，这个地方在后面扩容的时候要注意讨论
*/publicHashMap(){this.loadFactor = DEFAULT_LOAD_FACTOR;// all other fields defaulted}

三、 put（）方法

（一）、源码注释

/**
* put方法本质上是调用了putVal
*/publicVput(K key,V value){returnputVal(hash(key), key, value,false,true);}/**
 *put方法
 */finalVputVal(int hash,K key,V value,boolean onlyIfAbsent,boolean evict){Node<K,V>[] tab;Node<K,V> p;int n, i;//hashMap 构造方法并不会创建内部的数组，而是第一次put元素的时候才会创建//判断数组是否为null，或者长度是否为0if((tab = table)==null||(n = tab.length)==0)
        n =(tab =resize()).length;// (n - 1) & hash n为数组的长度，也就是2的n次幂，这个动作，相当于求余，找到//如果头结点为空，则把元素妨碍当前位置if((p = tab[i =(n -1)& hash])==null)
        tab[i]=newNode(hash, key, value,null);else{//进这个判断，则说明当前头结点已经有元素了，发生了hash碰撞Node<K,V> e;K k;if(p.hash == hash &&((k = p.key)== key ||(key !=null&& key.equals(k))))//判断当前头结点的key值，与将要放的key是否一致，如果一致，则将新的元素替换老的元素
            e = p;elseif(p instanceofTreeNode)//当前头结点的key值，与将要放的key不一致//则判断节点是否是树节，如果是数树节点的话，红黑树存放元素
            e =((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);else{//当前头结点的key值，与将要放的key不一致，也不是树节点，则说明这里是链表//遍历循环链表for(int binCount =0;;++binCount){//判断当前是不是链表的最后一个节点if((e = p.next)==null){// 尾插一个元素
                    p.next =newNode(hash, key, value,null);//判断链表的长度是否大于转化红黑树的阈值if(binCount >= TREEIFY_THRESHOLD -1)// -1 for 1st//转化成红黑树，注意这个函数里面，其实还有一个条件，当前hash的桶的个数，是否大于64，否则也不会转化成红黑树treeifyBin(tab, hash);break;}//当前节点不是最后一个节点执行逻辑，判断当前结点的key值，与将要放的key是否一致，如果一致，则将新的元素替换老的元素if(e.hash == hash &&((k = e.key)== key ||(key !=null&& key.equals(k))))break;//将下一个节点替换当前节点
                p = e;}}//判断e节点是不是null，观察上面的代码，我们会发现，e的值只有2种情况，如果hash种不存在当前要插入的key的时候，e会指向null；如果存在当前插入的key，则e会指向old 节点if(e !=null){// existing mapping for keyV oldValue = e.value;if(!onlyIfAbsent || oldValue ==null)
                e.value = value;afterNodeAccess(e);return oldValue;}}//modCount  含义todo ++modCount;//判断是否需要扩容if(++size > threshold)resize();afterNodeInsertion(evict);//因为如果存在当前插入的key的时候在上面已经return了，所以在这里只需要统一返回null即可returnnull;}

（二）、流程图

四、 resize（）方法

（一）、源码注释

finalNode<K,V>[]resize(){Node<K,V>[] oldTab = table;int oldCap =(oldTab ==null)?0: oldTab.length;int oldThr = threshold;int newCap, newThr =0;if(oldCap >0){// 第一种情况 数组中存在元素，说明已经初始化过if(oldCap >= MAXIMUM_CAPACITY){
               threshold =Integer.MAX_VALUE;return oldTab;}elseif((newCap = oldCap <<1)< MAXIMUM_CAPACITY &&
                   oldCap >= DEFAULT_INITIAL_CAPACITY)
               newThr = oldThr <<1;// double threshold}elseif(oldThr >0)// initial capacity was placed in threshold// 第二种情况 Map<String, String> map = new HashMap<>(16); new 带有参数的时候，第一次resize的时候会进入这个逻辑
           newCap = oldThr;else{// zero initial threshold signifies using defaults/** public HashMap() {this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted}
             第三种情况 空参new map的时候，并且第一次添加元素，会进入这个循环，给其设置初始值*/
           newCap = DEFAULT_INITIAL_CAPACITY;
           newThr =(int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}if(newThr ==0){//由上面第二种情况可以看出，没有设置newThr的值float ft =(float) newCap * loadFactor;
           newThr =(newCap < MAXIMUM_CAPACITY && ft <(float) MAXIMUM_CAPACITY ?(int) ft :Integer.MAX_VALUE);}
       threshold = newThr;// 创建一个新的空数组Node<K,V>[] newTab =(Node<K,V>[])newNode[newCap];
       table = newTab;// 第一次添加元素的时候也会执行resize()方法；如果老数组不为空，说明是扩容操作，那么涉及到元素的转移操作；if(oldTab !=null){// 根据容量进行循环整个数组，将非空元素进行复制for(int j =0; j < oldCap;++j){Node<K,V> e;// 获取数组的第j个元素if((e = oldTab[j])!=null){// 如果当前位置元素不为空，那么需要转移该元素到新数组
                   oldTab[j]=null;if(e.next ==null)//当前位置只有一个元素，即说明该元素不存在hash冲突
                       newTab[e.hash &(newCap -1)]= e;elseif(e instanceofTreeNode)//当前位置节点是树节点((TreeNode<K,V>) e).split(this, newTab, j, oldCap);else{// preserve order/** 当前位置是链表
                           扩容前，当前位置是一个链表，扩容后hash冲突的元素，可能保存在原来的位置，也有可能或移到当前位置+oldCap位置上，
                           有2个链表，所以需要2个头结点和2个尾部节点来标识2条链表*/Node<K,V> loHead =null, loTail =null;Node<K,V> hiHead =null, hiTail =null;Node<K,V> next;do{
                           next = e.next;// 高位为0，这个地方注意，e.hash & oldCap ，比如一开始有2个hash 分别是1001 0011 和 0100 0011，如果原来容量是16，                            // 1001 0011 和 0100 0011分别与上0000 1111（16-1= 15）那么他们会产生冲突，现在与的是0001 0000得到的是不一样的结果if((e.hash & oldCap)==0){//如果没有尾，说明链表为空，是第一次给新的数组 低位复制元素if(loTail ==null)// 链表为空时，头节点指向该元素
                                   loHead = e;else//在尾部添加元素，组装成链表
                                   loTail.next = e;// 把尾节点设置为当前元素
                               loTail = e;}//高位为1else{if(hiTail ==null)
                                   hiHead = e;else
                                   hiTail.next = e;
                               hiTail = e;}}while((e = next)!=null);if(loTail !=null){//低位的尾结点不为空的时候，低位的元素组成的链表还是放置在原来的位置
                           loTail.next =null;
                           newTab[j]= loHead;}if(hiTail !=null){//高位的尾结点不为空的时候,高位的元素组成的链表放置的位置只是在原有位置上偏移了老数组的长度个位置
                           hiTail.next =null;
                           newTab[j + oldCap]= hiHead;}}}}}return newTab;}

（二）、流程图

（三）、 resize方法的注意事项

resize()方法有2个注意点

一 、 就是newCap, newThr新的容量和新的扩容阈值的赋值这段if else逻辑判断，分别对应了三种情况，在上述流程图中有标注

（1）第一种情况：原来map中已经有元素，属于真实扩容
（2）第二种情况：第一次添加元素，且用的是有参构造出来的HashMap
（3）第三种情况：第一次添加元素，且用的是无参构造出来的HashMap

二、移动链表里的元素的时候，以为链表中存在的元素可能较多，需要将其移动

举个例子 假如有元素3 其hashcode计算得出是0000 0011 以及元素11其hashcode是0001 0011 那按照put方法，计算其位置
0000 0011 & 0000 1111 = 0000 0011
0001 0011 & 0000 1111 = 0000 0011 则他们2个都是放在3这个位置，注意这个时候与的是（16-1 ）=15
新计算的位置的时候 与的是16
0000 0011 & 0001 0000 = 0000 0000
0001 0011 & 0001 0000 = 0001 0000 根据计算结果是否为0，判断其放在原来的位置还是需要移动
如果产生移动，将会产生2个链表，一个低位链表，一个高位链表；故而有四个变量 Node<K, V> loHead = null, loTail = null;
Node<K, V> hiHead = null, hiTail = null;

备注：HashMap中这两个方法算是逻辑比较复杂的,理解这2个方法以后，get方法和remove方法基本也能理解。至于红黑树的相关源码，后续再写一篇相关的总结。

如果这篇【文章】有帮助到你，希望可以给博主点个赞👍，创作不易。后面我还会继续更新Redis集群的搭建、Redis的面试题等文章，我们一起继续学习吧。