您当前的位置：首页 > 计算机 > 编程开发 > Java

【JDK源码】HashMap源码分析（附常见面试题）

时间：05-13来源：作者：点击数：

HashMap源码分析（附面试题）

1.什么是哈希？

在分析HashMap之前，我们先来了解什么是哈希？

概念：Hash也称散列、哈希，对应的英文都是Hash。基本原理就是把任意长度的输入，通过Hash算法变成固定长度的输出这个映射的规则就是对应的Hash算法，而原始数据映射后的二进制串就是哈希值。

Hash的特点:

从hash值不可以反向推导出原始的数据
输入数据的微小变化会得到完全不同的hash值，相同的数据会得到相同的
哈希算法的执行效率要高效，长的文本也能快速地计算出哈希值
hash算法的冲突概率要小

由于hash的原理是将输入空间的值映射成hash空间内，而hash值的空间远小于输入的空间。根据抽屉原理，一定会存在不同的输入被映射成相同输出的情况。

抽屉原理：桌上有十个苹果，要把这十个苹果放到九个抽屉里，无论怎样放，我们会发现至少会有一个抽屉里面放不少于两个苹果。

这一现象就是我们所说的“抽屉原理”。

2.HashMap的继承体系

HashMap采用key/value存储结构，每个key对应唯一的value，查询和修改的速度都很快，能达到O(1)的平均时间复杂度。它是非线程安全的，且不保证元素存储的顺序。

从继承体系可以看出：

HashMap 实现了Cloneable接口，可以被克隆。
HashMap 实现了Serializable接口，属于标记性接口，HashMap 对象可以被序列化和反序列化。
HashMap 继承了AbstractMap，父类提供了 Map 实现接口，具有Map的所有功能，以最大限度地减少实现此接口所需的工作。

3.底层存储结构

1.7 数组 + 链表
1.8 数组 + （链表 | 红黑树）

在Java中，HashMap的实现采用了（数组 + 链表 + 红黑树）的复杂结构，数组的一个元素又称作桶。

在添加元素时，会根据hash值算出元素在数组中的位置，如果该位置没有元素，则直接把元素放置在此处，如果该位置有元素了，则把元素以链表的形式放置在链表的尾部。

当一个链表的元素个数达到一定的数量（且数组的长度达到一定的长度）后，则把链表转化为红黑树，从而提高效率。

数组的查询效率为O(1)，链表的查询效率是O(k)，红黑树的查询效率是O(log k)，k为桶中的元素个数，所以当元素数量非常多的时候，转化为红黑树能极大地提高效率。

树化需要同时满足两个条件：

链表长度大于8，并不是大于等于8
数组长度达到64。如果数组长度不够64，会优先进行resize()扩容。

4.内部类

Node内部类

Node是HashMap的静态内部类，实现了Map.Entry<K,V>接口。我们存储的键值对都是以Node的形式存储在map中的。其重要属性如下：

static class Node<K,V> implements Map.Entry<K,V> {
    //基于key的hashValue经过hash扰动后得到的，是hash分布更均匀
    final int hash;
    //put进来的key
    final K key;
    //对应的value
    V value;
    //指向链表中的下一个Node
    Node<K,V> next;
    ...
}

5.HashMap核心属性分析

  	/**
     * HashMap的初始化容量（必须是 2 的 n 次幂）默认的初始容量为16
     */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

    /**
     * table最大长度
     */
    static final int MAXIMUM_CAPACITY = 1 << 30;

    /**
     * 默认的负载因子
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    /**
     * 树化阈值：当一个桶中的元素个数大于8时进行树化（同时需要数组长度达到64）
     */
    static final int TREEIFY_THRESHOLD = 8;

    /**
     * 树降级为链表的阈值：当一个桶中的元素个数小于等于6时把树转化为链表
     */
    static final int UNTREEIFY_THRESHOLD = 6;
    /**
     * Node数组，又叫作桶（bucket）
     */
    transient Node<K,V>[] table;

    /**
     * 作为entrySet()的缓存
     */
    transient Set<Map.Entry<K,V>> entrySet;

    /**
     * 当前哈希表中元素的个数
     */
    transient int size;

    /**
     * 当前哈希表结构修改次数
     */
    transient int modCount;

    /**
     * 扩容阈值，当你的哈希表中的元素超过阈值时，触发扩容（threshold = capacity * loadFactor）
     */
    int threshold;

    /**
     * 负载因子（默认0.75）
     */
    final float loadFactor;

从属性源码我们可以得到几个信息：

容量：容量为数组的长度，亦即桶的个数，默认为16，最大为2的30次方，当容量达到64时才可以树化。
装载因子：用来计算容量达到多少时才进行扩容，默认装载因子为0.75。
树化：当容量达到64且链表的长度大于8时进行树化，当链表的长度小于6时反树化。

6.HashMap构造方法

HashMap()

构造一个空的HashMap，默认初始容量（16）和默认负载因子（0.75）

public HashMap() {
   // 将默认的负载因子0.75赋值给loadFactor，并没有创建数组
   this.loadFactor = DEFAULT_LOAD_FACTOR; 
}

HashMap(int initialCapacity)

构造指定初始容量initialCapacity的HashMap，其实也是调用HashMap(int initialCapacity，float loadFactor)，默认的负载因子

/**
* 指定初始容量大小的构造函数
* @param initialCapacity
*/
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

HashMap(int initialCapacity，float loadFactor)

构造一个具有指定的初始容量initialCapacity和负载因子loadFactor的 HashMap

/*
指定“容量大小”和“负载因子”的构造函数
initialCapacity：指定的容量
loadFactor:指定的负载因子
*/
public HashMap(int initialCapacity, float loadFactor) {
    //判断初始容量initialCapacity是否小于0
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    //判断初始容量initialCapacity是否大于集合的最大容量MAXIMUM_CAPACITY
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    //判断负载因子loadFactor是否<=0或者是否是一个非数值
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    //将指定的负载因子loadFactor赋值给HashMap成员变量的负载因子
    this.loadFactor = loadFactor;
    //给扩容阈值赋值（只能是2的次方）
    this.threshold = tableSizeFor(initialCapacity);
}
	 /**
     * 作用：返回比指定cap容量大的最小2的n次幂数
     * 栗子：cap=10
     * n=10-1=9
     * 0b1001 | 0b0100 = 0b1101
     * 0b1101 | 0b0011 = 0b1111
     * 0b1111 | 0b0000 = 0b1111
     * 0b1111 | 0b0000 = 0b1111
     * 0b1111 | 0b0000 = 0b1111
     * ob1111->15
     * 15>0 -> return 15+1(16)
     * 模式：0001 1101 1100 => 0001 1111 1111 +1 => 0010 0000 0000
     */
static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

7.put方法

put方法的整体流程：

计算key的hash值
如果桶（数组）数量为0，则初始化桶
如果key所在的桶没有元素，则直接插入
如果key所在的桶中的第一个元素的key与待插入的key相同，说明找到了元素，转后续流程（9）处理
如果第一个元素是树节点，则调用树节点的putTreeVal()寻找元素或插入树节点
如果不是以上三种情况，则遍历桶对应的链表查找key是否存在于链表中
如果找到了对应key的元素，则转后续流程（9）处理
如果没找到对应key的元素，则在链表最后插入一个新节点并判断是否需要树化
如果找到了对应key的元素，则判断是否需要替换旧值，并直接返回旧值
如果插入了元素，则数量加1并判断是否需要扩容

public V put(K key, V value) {
	 // 调用hash(key)计算出key的hash值
    return putVal(hash(key), key, value, false, true);
}

	/**
     * 作用：让key的hash值的高16位参与运算
     * @param key
     * @return
     */
static final int hash(Object key) {
    int h;
    //key==null直接返回0
    //1、否则调用key的hashCode()方法计算出key的哈希值然后赋值给h,
    //2、后与h无符号右移16位后的二进制进行按位异或得到最后的hash值,
    //3、这样做是为了使计算出的hash更分散，让高16位可以参与（低16位具有高16位的特征）
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

	/**
     *
     * @param hash  key的hash值
     * @param key   原始key
     * @param value 要存放的值
     * @param onlyIfAbsent  如果 true 代表不更改现有的值，也就是说如果存在key就不改变，一般传入false
     * @param evict  如果为false表示 table 为创建状态
     * @return
     */
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    //tab：引用当前hashMap的散列表
    //p：表示当前散列表的元素
    //n：表示散列表数组的长度
    //i：表示路由寻址结果
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // 如果桶的数量为0，则初始化
    if ((tab = table) == null || (n = tab.length) == 0)
        // 调用resize()初始化
        n = (tab = resize()).length;
    //最简单的一种情况：寻址找到的桶位null，直接将创建一个新结点放入桶中
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        //e：不为null的话，找到一个与当前要插入的key-value一致的key元素
        //k：临时的一个key
        Node<K,V> e; K k;
        //表示桶位中的该元素，与你当前插入的元素key完全一致，表示后续要进行替换操作
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)
            // 如果第一个元素是树节点，则调用树节点的putTreeVal插入元素
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
			// 遍历这个桶对应的链表，binCount用于存储链表中元素的个数
            for (int binCount = 0; ; ++binCount) {
                //条件成立的话，说明迭代到最后一个元素了，也没找到一个与你插入的key一致的node
                //说明需要加入到当前链表的尾部
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    //条件成立的话，说明当前链表的长度达到树化的标准了，需要进行树化
                    if (binCount >= TREEIFY_THRESHOLD - 1)
                        //树化操作
                        treeifyBin(tab, hash);
                    break;
                }
                //说明条件成立的化，找到了相同key的node元素，进行替换操作
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        //e不等于null，说明找到了一个与你插入元素key完全一致的数据，需要进行替换
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            // 在节点被访问后做点什么事，在LinkedHashMap中用到
            afterNodeAccess(e);
            // 返回旧值
            return oldValue;
        }
    }
    //散列表结果修改次数加一，替换Node元素的value不计数
    ++modCount;
    //插入新元素，size自增
    //如果大于扩容阈值，扩容
    if (++size > threshold)
        resize();
    // 在节点插入后做点什么事，在LinkedHashMap中用到
    afterNodeInsertion(evict);
    // 没找到元素返回null
    return null;
}

8.resize扩容方法

整个扩容流程：

如果使用是默认构造方法，则第一次插入元素时初始化为默认值，容量为16，扩容门槛为12
如果使用的是非默认构造方法，则第一次插入元素时初始化容量等于扩容门槛，扩容门槛在构造方法里等于传入容量向上最近的2的n次方
如果旧容量大于0，则新容量等于旧容量的2倍，但不超过最大容量2的30次方，新扩容门槛为旧扩容门槛的2倍
创建一个新容量的桶
搬移元素，原链表分化成两个链表，低位链表存储在原来桶的位置，高位链表搬移到原来桶的位置加旧容量的位置

/**
     * 为什么需要扩容？
     * 为了解决hash冲突导致的链化影响查询效率的问题，扩容会缓解该问题
     *
     * @return
     */
final Node<K, V>[] resize() {
    //引用扩容前的哈希表
    Node<K, V>[] oldTab = table;
    //表示扩容之前的table数组的长度
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    //扩容之前的扩容阈值
    int oldThr = threshold;
    //newCap：扩容之后table数组的大小
    //newThr：扩容之后，下次在触发扩容的条件
    int newCap, newThr = 0;
    //条件入如果成立：说明hashMap中的散列表已经初始化过了，是一次正常扩容
    if (oldCap > 0) {
        //如果旧容量达到最大容量，则不再进行扩容
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 如果旧容量的两倍小于最大容量并且旧容量大于默认初始容量（16），则容量扩大为两部，扩容门槛也扩大为两倍
        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，第一次插入元素会走到这里
        //1.new HashMap(initCap,loadFactor);
        //2.new HashMap(initCap);
        //3.new HashMap(map); map有数据
        // 如果旧容量为0且旧扩容门槛大于0，则把新容量赋值为旧门槛
        newCap = oldThr;
    else {
        //使用默认构造方法创建的map，第一次插入元素会走这里
        newCap = DEFAULT_INITIAL_CAPACITY;
        //如果旧容量旧扩容门槛都是0，说明还未初始化过，则初始化容量为默认容量，扩容门槛为默认容量*默认装载因子
        newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }

    if (newThr == 0) {
        //如果旧容量旧扩容门槛都是0，说明还未初始化过，则初始化容量为默认容量，扩容门槛为默认容量*默认装载因子
        float ft = (float) newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float) MAXIMUM_CAPACITY ?
                  (int) ft : Integer.MAX_VALUE);
    }
    //赋值扩容门槛为新门槛
    threshold = newThr;
    //创建一个新容量的数组
    @SuppressWarnings({"rawtypes", "unchecked"})
    Node<K, V>[] newTab = (Node<K, V>[]) new Node[newCap];
    //把桶赋值为新数组
    table = newTab;
    //如果旧数组不为空，则搬移元素
    if (oldTab != null) {
        //遍历旧数组
        for (int j = 0; j < oldCap; ++j) {
            //当前node节点
            Node<K, V> e;
            //如果当前桶中第一个元素不为空，说明当前桶位有数据，赋值给e
            if ((e = oldTab[j]) != null) {
                //清空旧桶，方便JVM GC时回收内存
                oldTab[j] = null;
                if (e.next == null)
                    //第一种情况：当前桶位只有一个元素，从未发生过碰撞
                    //该情况直接计算出当前元素应该存放的新数组中的位置，然后扔进去就行
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    //第二种情况：当前桶位已经树化,则把这颗树打散成两颗树插入到新桶中去
                    ((TreeNode<K, V>) e).split(this, newTab, j, oldCap);
                else {
                    //第三种情况：链表情况
                    // 比如，假如原来容量为4，3、7、11、15这四个元素都在三号桶中
                    // 现在扩容到8，则3和11还是在三号桶，7和15要搬移到七号桶中去
                    // 也就是分化成了两个链表
                    //低位链表：存放在扩容之后下标位置与当前数组下标位置一致
                    Node<K, V> loHead = null, loTail = null;
                    //高位链表：存放在扩容之后的数组的下标位置=为当前数组下标位置+扩容之前数组的长度
                    Node<K, V> hiHead = null, hiTail = null;
                    Node<K, V> next;
                    do {
                        next = e.next;
                        // (e.hash & oldCap) == 0的元素放在低位链表中
                        //比如3&4==0
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        } else {
                            // (e.hash & oldCap) != 0的元素放在高位链表中
                            //比如，7&4！=0
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    // 遍历完成分化成两个链表了
                    // 低位链表在新桶中的位置与旧桶一样（即3和11还在三号桶中）
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    // 高位链表在新桶中的位置正好是原来的位置加上旧容量（即7和15搬移到七号桶了）
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

9.get方法

public V get(Object key) {
    Node<K, V> e;
    //这里hash(key)是因为put的时候hash了，这里取自然也需要hash
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

final Node<K, V> getNode(int hash, Object key) {
    //引用当前hashMap的散列表
    Node<K, V>[] tab;
    //first:桶位中的头元素
    //e:临时node元素
    Node<K, V> first, e;
    //n:table数组长度
    int n;
    K k;
    // 如果桶的数量大于0并且待查找的key所在的桶的第一个元素不为空
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        // 检查第一个元素是不是要查的元素，如果是直接返回
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        // 第一个元素不是要查找的元素，并且当前桶位不止一个元素，可能存在链表或者树
        if ((e = first.next) != null) {
            // 如果第一个元素是树节点，则按树的方式查找
            if (first instanceof TreeNode)
                return ((TreeNode<K, V>) first).getTreeNode(hash, key);
            // 否则就遍历整个链表查找该元素
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

get方法具体分这几步：

计算key的hash值
找到key所在的桶及其第一个元素
如果第一个元素的key等于待查找的key，直接返回
如果第一个元素是树节点就按树的方式来查找
否则就按链表方式查找

10.remove方法

public V remove(Object key) {
    Node<K, V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}

final Node<K, V> removeNode(int hash, Object key, Object value,
                            boolean matchValue, boolean movable) {
    //引用当前hashMap中的散列表
    Node<K, V>[] tab;
    //当前node元素
    Node<K, V> p;
    //n:表示散列表数组长度
    //index:表示寻址结果
    int n, index;
    // 如果桶的数量大于0且待删除的元素所在的桶的第一个元素不为空
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (p = tab[index = (n - 1) & hash]) != null) {
        //node:表示查找到的结果
        //e:表示当前node的下一个元素
        Node<K, V> node = null, e;
        K k;
        V v;
        // 如果第一个元素正好就是要找的元素，赋值给node变量后续删除使用
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            node = p;
        // 第一个元素不是要查找的元素，并且当前桶位不止一个元素，可能存在链表或者树
        else if ((e = p.next) != null) {
            if (p instanceof TreeNode)
                // 如果第一个元素是树节点，则以树的方式查找节点
                node = ((TreeNode<K, V>) p).getTreeNode(hash, key);
            else {
                // 否则遍历整个链表查找元素
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    p = e;
                } while ((e = e.next) != null);
            }
        }
        // 如果找到了元素，则看参数是否需要匹配value值，如果不需要匹配直接删除，如果需要匹配则看value值是否与传入的value相等
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {
            if (node instanceof TreeNode)
                // 如果是树节点，调用树的删除方法（以node调用的，是删除自己）
                ((TreeNode<K, V>) node).removeTreeNode(this, tab, movable);
            else if (node == p)
                // 如果待删除的元素是第一个元素，则把第二个元素移到第一的位置
                tab[index] = node.next;
            else
                // 否则删除node节点，将当前元素p的下一个元素设置为删除元素的下一个元素
                p.next = node.next;
            ++modCount;
            --size;
            // 删除节点后置处理
            afterNodeRemoval(node);
            return node;
        }
    }
    return null;
}

整个remove流程分为这几步：

先查找元素所在的节点
如果找到的节点是树节点，则按树的移除节点处理
如果找到的节点是桶中的第一个节点，则把第二个节点移到第一的位置
否则按链表删除节点处理
修改size，调用移除节点后置处理等

11.总结

HashMap是一种散列表，采用（数组 + 链表 + 红黑树）的存储结构
HashMap的默认初始容量为16（1<<4），默认装载因子为0.75f，容量总是2的n次方
HashMap扩容时每次容量变为原来的两倍
当桶的数量小于64时不会进行树化，只会扩容
当桶的数量大于64且单个桶中元素的数量大于8时，进行树化
当单个桶中元素数量小于6时，进行反树化
HashMap是非线程安全的容器
HashMap查找添加元素的时间复杂度都为O(1)

HashMap在JDK1.7和1.8中不同

1.7 数组 + 链表
1.8 数组 + （链表 | 红黑树）

为啥要用红黑树？

红黑树用来避免DoS攻击，防止链表超长时性能下降，树化应当是偶然情况，是保底策略

为何不一上来就树化？

hash 表的查找，更新的时间复杂度是O ( 1 ) O(1)O(1)，而红黑树的查找，更新的时间复杂度是O ( l o g 2 ⁡ n ) O(log_2⁡n )O(log2⁡n)
TreeNode 占用空间也比普通 Node 的大，如非必要，尽量还是使用链表

树化阈值为何是8？

hash 值如果足够随机，则在 hash 表内按泊松分布，在负载因子0.75的情况下，长度超过 8 的链表出现概率是 0.00000006，树化阈值选择 8 就是为了让树化几率足够小

树化规则

当链表长度超过树化阈值 8 时，先尝试扩容来减少链表长度，如果数组容量已经 >=64，才会进行树化
树化的两个条件：链表长度超过树化阈值>8&& 数组容量>=64

退化规则

情况1：在扩容时如果拆分树时，树元素个数<= 6则会退化链表
情况2：移除之前，remove 树节点时，若 root、root.left、root.right、root.left.left 有一个为 null ，也会退化为链表

索引计算方法

首先，计算对象的hashCode()
再进行调用 HashMap 的hash()方法进行二次哈希。二次 hash() 是为了综合高位数据，让哈希分布更为均匀
最后& (capacity – 1)得到索引

数组容量为何是 2 的 n 次幂

计算索引时效率更高：如果是 2 的 n 次幂可以使用位与运算代替取模
扩容时重新计算索引效率更高： hash & oldCap == 0 的元素留在原来位置，否则新位置 = 旧位置 + oldCap

注意：

二次 hash 是为了配合容量是 2 的 n 次幂这一设计前提，如果 hash 表的容量不是 2 的 n 次幂，则不必二次 hash
容量是 2 的 n 次幂这一设计计算索引效率更好，但 hash 的分散性就不好，需要二次 hash 来作为补偿，没有采用这一设计的典型例子是 Hashtable

put 流程

HashMap 是懒惰创建数组的，首次使用才创建数组
计算索引（桶下标）
如果桶下标还没人占用，创建 Node 占位返回
如果桶下标已经有人占用
- 已经是 TreeNode 走红黑树的添加或更新逻辑
- 是普通 Node，走链表的添加或更新逻辑，如果链表长度超过树化阈值，走树化逻辑
返回前检查容量是否超过阈值，一旦超过进行扩容