一、新办法
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<>();@Testpublic 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
- 通过spread()办法计算出的hash必然是负数
- 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;}- 通过
(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办法等）