一、新办法

java 1.8 之后，HashMap 提供了一些新办法，不便了某些特定场景的操作

• compute

// 当 key 的值不存在时执行
computeIfAbsent(key,v->{
    // 业务代码
    return xxxx;
})

// 当 key 的值存在时执行
computeIfPresent(key,(k,v)->{
     // 业务代码
    return xxxx;
})

// 依据传入函数计算 key 的值
compute(key,(k,v)->{
     // 业务代码
    return xxxx;
})

应用举例：

ConcurrentHashMap<String,Integer> chm = new ConcurrentHashMap<>();

@Test
public void testCompute() throws InterruptedException {
    String key = "test";
    for(int i=0;i<10;i++){new Thread(()->{
            // 通过 compute 办法做某个 key 的 value 的累加
            chm.compute(key,(k,v)->{if(v==null){v = 10;}else {v += 10;}
                return v;
            });
        }).start();}

    TimeUnit.SECONDS.sleep(2L);
    System.out.println(chm.get(key));
}

• merge

// 合并 key 雷同的值，function 两个参数代表旧值、新值
merge(key,(oldVal,newVal)->{
    // 业务代码
    return xxxx;
})

二、实现原理

1. 初始化 table 数组

咱们从 put 办法动手进行剖析。
首先会进入 初始化 table 数组 逻辑

public V put(K key, V value) {return putVal(key, value, false);
}

transient volatile Node<K,V>[] table;

final V putVal(K key, V value, boolean onlyIfAbsent) {  
    // ... 省略...
    
    for (Node<K,V>[] tab = table;;) {
        // == 1. 初始化 tab
        if (tab == null || (n = tab.length) == 0){tab = initTable();
        }
        
        // ... 省略...

// ## sizeCtl 变量有状态机的作用
// -- 1、=-1，tab 正在初始化（或正在扩容）；// -- 2、> 0，示意扩容因子
// -- 3、<-1，用来计算扩容时的线程参加数
private transient volatile int sizeCtl;

private final Node<K,V>[] initTable() {Node<K,V>[] tab; int sc;
    while ((tab = table) == null || tab.length == 0) {
        
        // `< 0` 示意其它线程正在初始化 tab，以后线程尝试让出 cpu 控制权
        //（循环中再次进入，tab 可能曾经初始化好了）if ((sc = sizeCtl) < 0)
            Thread.yield();

        // cas 形式批改 sizeCtl 的值，改成 - 1 示意正在初始化；else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
            try {
                // 这里用到了 double-check
                if ((tab = table) == null || tab.length == 0) {int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
                    Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
                    table = tab = nt;
                    // 计算扩容因子的值，达到 `3/4 size` 扩容
                    sc = n - (n >>> 2);
                }
            } finally {
                // 设置成负数，示意扩容因子
                sizeCtl = sc;
            }
            break;
        }
    }
    return tab;
}

2. 一般 put

1. 通过 spread()办法计算出的hash 必然是负数
2. hash 为正数有非凡含意

static final int MOVED     = -1;    // 迁徙
static final int TREEBIN   = -2;    // 树

// ## hash 值计算，肯定为正; 复数有非凡含意（见下面的属性）static final int spread(int h) {
    // int 是 32 位
    // `h ^ (h >>> 16)`
    // 负数：高 16 位与 0 异或；正数：高 16 位与 1 异或（同 0 异 1）// 低 16 位与高 16 位异或，减少随机性
    
    // 上述后果再 `& HASH_BITS`，也就是 `& 0x7fffffff` = & 0111 1111..(前面全是 1)
    // 失去的肯定是一个负数（最高位 0 示意正）return (h ^ (h >>> 16)) & HASH_BITS;
}

3. 通过 (n-1)&hash 计算出落点桶

• 如果桶为空，新建 Node 后 cas 替换赋值
• 如果桶中有元素，先对头元素加锁，而后依据元素类型别离解决

来看下元素为链表的状况：
遍历链表，如果找到 key 相等的元素，替换；如果未找到，新建 Node 尾插链表

final V putVal(K key, V value, boolean onlyIfAbsent) {
    // ## key 和 val 均不能为空
    if (key == null || value == null) throw new NullPointerException();
    // ## hash 值计算
    int hash = spread(key.hashCode());

    int binCount = 0;

    for (Node<K,V>[] tab = table;;) {
        Node<K,V> f; int n, i, fh;

        // ... 省略初始化逻辑...

        // == 1. 桶没有节点，cas 形式创立
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
            if (casTabAt(tab, i, null,
                         new Node<K,V>(hash, key, value, null)))
                break;                   // no lock when adding to empty bin
        }

        // ... 省略...

        // == 2. 桶对应的节点有值的状况（又分链、红黑树几种状况）else {
            V oldVal = null;
            // ## 对桶指向的 Node 加锁
            // 在后面的逻辑中：i-hash 计算的落点桶的索引;f- 桶 i 的 Node 对象;fh- f 对象的 hash 值
            synchronized (f) {
                // double-check
                if (tabAt(tab, i) == f) {
                    // -- f 对象的 hash 值大于等于 0，示意链
                    if (fh >= 0) {
                        binCount = 1;
                        for (Node<K,V> e = f;; ++binCount) {
                            K ek;
                            // -- 在链上找到了 key 相等的元素，替换 value
                            if (e.hash == hash &&
                                ((ek = e.key) == key ||
                                 (ek != null && key.equals(ek)))) {
                                oldVal = e.val;
                                if (!onlyIfAbsent)
                                    e.val = value;
                                break;
                            }
                            Node<K,V> pred = e;
                            // -- 管制链的节点挪动；最终在链上没找到 key 雷同节点，则尾插节点
                            if ((e = e.next) == null) {
                                pred.next = new Node<K,V>(hash, key,
                                                          value, null);
                                break;
                            }
                        }
                    }
                     // -- 节点是树的状况
                    else if (f instanceof TreeBin) {//... 省略...}
                }
            }

            //... 省略...

3.put 引发扩容

1、扩容条件

满足条件之一时触发

• 链上元素 >=8，元素个数 <64
• 元素个数超过扩容因子

扩容前会计算扩容戳，扩容戳的计算与元素个数无关，同时也会与 sizeCtl 产生分割

由此得出 两个论断

• 扩容时，sizeCtl 必然为正数；
• 如果 sizeCtl-2=rs<<16，示意扩容完结

2、数据迁徙

扩容会引发桶数据迁徙

• 每个线程负责迁徙肯定数量的桶

上图中线程 A 分到桶 16-31，进行迁徙；
之后线程 B 分到桶 0 -15，帮忙迁徙；
再有线程 C 进入，试图帮忙迁徙（helpTransfer 办法）——因为桶曾经被迁徙线程瓜分完了（图中状况），无需帮忙。线程 C 会间接向新 tab 的桶中 put 数据

• 如果落点桶为空

将一个 Forwarding Node（fwd）放入桶中，fwd 的 nextTable 属性指向新 table

• 如果落点桶为树（疏忽）
• 如果落点桶为链

写不下了，下一篇持续剖析（下篇蕴含 链的迁徙原理 、 元素计数 、get 办法 等）