java.util.HashMap<K,V> 源码解析-增删改

1. 构造方法

public HashMap(int initialCapacity, float loadFactor)

• initialCapacity:初始容量，传入时，threshold(下次扩容阈值)为tableSizeFor(initialCapacity)即向上找最接近的2的整数次幂，不传入默认为0，在这种情况下，在第一次put元素时，table为空不够用导致resize()，resise后capacity为默认值16，threshold为16*loadFactor;
• loadFactor:负载因子，当table内存储数据达到此比例后，经验推断hash碰撞的可能性会大大提高，因此需要进行扩容，默认0.75，此属性为protect变量，修改需要新写HashMap的子类

2. 增删改

2.1. 增

实际调用下面的方法来进行新增操作：

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            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);
            else {
                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
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

2.1.2 流程

• 1)如果没初始化，调用resize方法
• 2)k-v对的默认位置为index=(capacity-1)&hash
• 3)若index的位置没有值（即不冲突），则将k-v对包裹进Node对象放入，Node对象的next为null，返回null
• 4)如果key.equals(原来的key),证明是值的覆盖，返回原来的值，在!onlyIfAbsent为真时，替换值
• 2)如果!key.equals(原来的key),证明是产生hash冲突,如下

2.1.3 hash冲突的处理

2.1.3.1 原节点已经是TreeNode，则调用TreeNode对象的putVal方法

e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value)

具体TreeNode新增节点细节见TreeNode描述

2.1.3.2 原节点不是TreeNode,即当前还是链状存储

1. 遍历此链，若有key与传入hash相等(==或者a.equals(b))的，则替换值，返回原值
2. 若不是替换的情况，则将新K-V对包裹到Node里，并挂到最后一个节点后，并判断当前的Node是否需要转换为TreeNode,若是则将此处的节点树化:treeifyBin(tab, hash)

3. 扩容

扩容一共分为两步，第一步确定新的table大小和下次扩容阈值，第二步，重新将现有的table中的所有node存入新table(中间可能涉及TreeNode转链表Node)

3.1 计算table大小和下次扩容阈值

st=>start: 开始
e=>end: 结束
tableEmpty=>condition: 内部table为空?
twiceCap=>operation: table大小翻倍：cap<=1;
twiceThr=>operation: 扩容阈值翻倍: thr<=1;
thrIsZero=>condition: 当前扩容阈值为0?
defaultCap=>operation: table大小设为初始值(默认16);
defaultThr=>operation: 扩容阈值=cap*loadFactor(默认0.75);
capSetAsOldThr=>operation: cap=当前扩容阈值
thrMultiFactor=>operation: 扩容阈值=cap*loadFactor

st->tableEmpty
tableEmpty(yes)->thrIsZero->e
thrIsZero(yes)->defaultCap->defaultThr->e
thrIsZero(no)->capSetAsOldThr->thrMultiFactor->e
tableEmpty(no)->twiceCap->twiceThr->e

3.2 原table中的Node元素拷贝到新table

遍历原table的每一个Node，对于非null的Node，执行下列操作来复制到新的table

st=?start: 开始