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

目录

一、前言二、 HashMap 的构造方法三、 put（）方法

（一）、源码注释（二）、流程图 四、 resize（）方法

（一）、源码注释（二）、流程图（三）、 resize方法的注意事项 一、前言

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

二、 HashMap 的构造方法

public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR);}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);}public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted}

三、 put（）方法 （一）、源码注释

public V put(K key, V value) { return putVal(hash(key), key, value, false, true); } final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node[] tab; Node p; int n, i; //hashMap 构造方法并不会创建内部的数组，而是第一次put元素的时候才会创建 //判断数组是否为null，或者长度是否为0 if ((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 e; K k; if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) //判断当前头结点的key值，与将要放的key是否一致，如果一致，则将新的元素替换老的元素 e = p; else if (p instanceof TreeNode) //当前头结点的key值，与将要放的key不一致 //则判断节点是否是树节，如果是数树节点的话，红黑树存放元素 e = ((TreeNode)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 key V 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即可 return null;}

（二）、流程图 四、 resize（）方法 （一）、源码注释

final Node[] resize() { Node[] 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; } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; // double threshold } else if (oldThr > 0) // initial capacity was placed in threshold // 第二种情况 Map map = new HashMap<>(16); new 带有参数的时候，第一次resize的时候会进入这个逻辑 newCap = oldThr; else { // zero initial threshold signifies using defaults 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[] newTab = (Node[]) new Node[newCap]; table = newTab; // 第一次添加元素的时候也会执行resize()方法；如果老数组不为空，说明是扩容操作，那么涉及到元素的转移操作； if (oldTab != null) { // 根据容量进行循环整个数组，将非空元素进行复制 for (int j = 0; j < oldCap; ++j) { Node e; // 获取数组的第j个元素 if ((e = oldTab[j]) != null) { // 如果当前位置元素不为空，那么需要转移该元素到新数组 oldTab[j] = null; if (e.next == null) //当前位置只有一个元素，即说明该元素不存在hash冲突 newTab[e.hash & (newCap - 1)] = e; else if (e instanceof TreeNode) //当前位置节点是树节点 ((TreeNode) e).split(this, newTab, j, oldCap); else { // preserve order Node loHead = null, loTail = null; Node hiHead = null, hiTail = null; Node 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; } //高位为1 else { 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 loHead = null, loTail = null;
Node hiHead = null, hiTail = null;

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

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