基于JDK1.8的HashMap源码解析二(put和resize操作)

本篇博客主要讲解了HashMap的put和resize操作

相关系列

基于JDK1.8的HashMap源码解析一(变量和构造器)
基于JDK1.8的HashMap源码解析三(get和remove以及迭代器)

HashMap节点解析

// HashMap普通节点
static class Node<K,V> implements Map.Entry<K,V> {
    // 节点hash值，为HashMap方法hash(key)得到，和Node节点自身的hashCode()无关
    final int hash;
    // HashMap的key值
    final K key;
    // HashMap的value值
    V value;
    // 当前节点指向的下一节点(HashMap产生冲突时将会采用尾插法将新增节点插入下一节点)
    Node<K,V> next;

    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }

    public final K getKey()        { return key; }
    public final V getValue()      { return value; }
    public final String toString() { return key + "=" + value; }

    // 节点的hashCode
    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }

    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }

    public final boolean equals(Object o) {
        if (o == this)
            return true;
        if (o instanceof Map.Entry) {
            Map.Entry<?,?> e = (Map.Entry<?,?>)o;
            if (Objects.equals(key, e.getKey()) &&
                Objects.equals(value, e.getValue()))
                return true;
        }
        return false;
    }
}

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    // 父节点
    TreeNode<K,V> parent;  // red-black tree links
    // 左子节点
    TreeNode<K,V> left;
    // 右子节点
    TreeNode<K,V> right;
    // 前置节点
    TreeNode<K,V> prev;
    // 是否红节点
    boolean red;
    TreeNode(int hash, K key, V val, Node<K,V> next) {
        super(hash, key, val, next);
    }
}

HashMap拥有两种不同的节点，一种是普通的链表节点，一种是红黑树节点。红黑树比较难解析，因为HashMap源码跳过红黑树如何转换我们也能看懂，所以我打算以后放在一章专门的文章中讲解。普通节点很简单，其实就是我们大学数据结构课程常见的链表节点，我相信大家也能看懂，所以也不过多讲解了。

HashMap的put操作

// 计算key的hash，这是一个"扰动函数"让高16和低16位进行异或，使分布更平衡，主要是为了防止差的hash函数
// key为null的hash为0，所以key为null的键值对存放在table[0],和普通节点并无区别(HashMap1.7对key为null进行了特殊处理)
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

// put方法
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}
 
/**
 *实现map.put和相关方法。
 *
 * @param hash key的hash值
 * @param key  key
 * @param value  value
 * @param onlyIfAbsent  如果为true，则不更改现有值
 * @param evict 如果为false，则表处于创建模式。
 * @return 被替换的值，如果没有，则返回null
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    // tab是table的一个局部引用，p作用用来记录节点，同时用于后续循环记录位置
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // 如果集合没有初始化，则进行resize初始化
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 将插入的bucket元素赋值给p，同时判断插入的bucket有没有其他Node，没有直接插入
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        // e用来记录是否存在存在插入的key的节点，后期用来判断更新
        Node<K,V> e; K k;
        // 如果当前bucket头结点等于插入的key，则用e记录当前的节点
        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);
        // 插入的key不等于头结点，进入此分支判断
        else {
            // 进入循环判断是要新增还是更新
            for (int binCount = 0; ; ++binCount) {
                // 如果e等于null，则代表遍历到最后依旧没有对应的key，执行新增操作
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // 到了红黑树转换阈值则转换成红黑树
                    if (binCount >= TREEIFY_THRESHOLD - 1)
                        treeifyBin(tab, hash);
                    break;
                }
                // 如果遍历途中有与插入的key相同的节点，跳出循环
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                 // 记录当前遍历操作的节点
                 p = e;
            }
        }
        // 如果最后e存在，则更新值；如果是putIfAbsent()方法，则不更新返回旧值
        if (e != null) {
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            // 这是为linkedHashMap留的后路
            afterNodeAccess(e);
            // 更新则直接跳出函数
            return oldValue;
        }
    }
    
    // 增加内部操作的次数
    ++modCount;
    // 新增之后对size进行自增，如果达到扩容阈值则扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

// HashMap的插入中如果有当前key不更新方法
@Override
public V putIfAbsent(K key, V value) {
    return putVal(hash(key), key, value, true, true);
}

以上是HashMap的put操作的过程，总结如下:put首先判断是否初始化，没有就进行初始化操作。如果已经进行了初始化操作，根据hash判断插入的bucket中是否有值，没有则直接插入。如果有值，则循环遍历当前链表，找到是否存在相应的key，不存在执行插入操作，否则执行更新操作，期间插入过程到了红黑树的阈值则转换成红黑树。

HashMap的resize操作

final Node<K,V>[] resize() {
    // 内部entry数组
    Node<K,V>[] oldTab = table;
    // 内部数组大小
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    // 内部扩容阈值，可以看下构造器，如果是有参构造此值为新的容器所需要的大小，即2的幂次方
    int oldThr = threshold;
    // 扩容后entry数组大小，扩容后扩容阈值
    int newCap, newThr = 0;
    
    if (oldCap > 0) {
        // 如果entry数组大小不为空并且大于等于最大容量值，则将扩容阈值设为int最大值并返回原entry数组退出
        // 因为此时数组不再支持扩容了(其实设为MAXIMUM_CAPACITY也行)
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 如果支持扩容，则将旧数组容量和扩容阈值都扩容一倍(因为是2的幂次方)
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    // 如果entry数组容量等于0且旧的扩容阈值大于0，将初始化容量设为扩容阈值
    //此情况存在于有参构造HashMap中，这下知道扩容阈值为什么不*loadFactor吧，避免无用计算
    else if (oldThr > 0)
        newCap = oldThr;
    // 如果两个都为空(无参构造)，将容量和扩容阈值都设为默认
    else {
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // 如果新的扩容阈值等于0，则设置成容量*负载因子，也判断了边界
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    
    @SuppressWarnings({"rawtypes","unchecked"})
    // 创建新的entry数组，大小为扩容后大小并赋值给当前entry数组
    // 注意，若此时并发get，会出现取值错误，所以HashMap是线程不安全的
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            // 循环取出每一个bucket中的Node节点
            if ((e = oldTab[j]) != null) {
                // 取完就清除旧的引用，用完就扔
                oldTab[j] = null;
                // bucket中的节点没有子节点的话直接赋值给新的bucket
                if (e.next == null)
                    // 此处运算是计算新节点的位置，因为新容量值是旧的两倍，减1与运算之后要么是 原位置 要么是 原位置+oldCap
                    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;
                    // 高位头结点，高位尾结点(高位代表原来位置+oldCap)
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        // 获取下一节点
                        next = e.next;
                        // 节点hash和旧容量进行与操作，若为0，则代表新位置为原来的位置
                        // 为什么可以这样确定呢，因为oldCap是2的幂次方，和oldCap-1比除了新增位为1，其余都为0，
                        // 因此可以得出节点hash值新增位是0还是1，进而判断是原位置还是原位置+oldCap
                        if ((e.hash & oldCap) == 0) {
                            // 如果尾节点为null则将当前节点设置为头结点，否则插入尾结点之后，并将尾结点设置为当前节点
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
                            // 原理同上，不过是高位节点的设置
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    // 判断尾结点的下一节点是否为null,不为null继续进入循环
                    // 这里要绕过一个弯，因为最开始保存了头结点，且最开始的尾结点也是头结点
                    // 第二次的时候loTail.next = e;实际上因为loHead和loTail都是指向最初的头结点
                    // 所以你要知道这相当于给loHead插入了一个尾结点，之后继续用loTail记录插入的尾结点
                    // 所以loTail的作用仅仅是用于保存上一个尾结点并且将新的节点插入再记录当前节点(过了循环就是上一个的尾节点了)
                    } while ((e = next) != null);
                    // 将最后的尾结点的下一节点设置为null，将新链表的头节点插入bucket
                    // Tail判断为null的理由是可能resize()后仍然全在一个bucket
                    // Tail.next设置为null的理由是低位的尾结点可能还残留高位的尾结点(或相反)
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

以上就是HashMap的resize()全过程了，每一步我都进行了详细的说明，现在系统的说一下它的全过程吧。因为HashMap的延时初始化策略，首先判断是否初始化，没有则根据构造方法进行初始化容量，同时也判断了是否超出最大容量的边界。正常扩容阶段则创建一个新的entry数组，同时将原entry数组中的每一个bucket中的元素通过尾插法(JDK1.7中使用得头插法)移动到新的bucket中。另外，hashMap没有对key为null的键值对进行特殊处理整个过程也很简单，只是一些细节方面可能需要理解一下。

好了，第二章的解析就到这里吧，我们下章再见，因为笔者不会画图，如果有同学画图厉害愿意帮忙把其中一些不好理解的操作画图给我那就太感激不尽啦。