键值对Map-04

1.jdk1.7 中 CHM 数据结构？

ConcurrentHashMap 和 HashMap 结构差不多，不过 ConcurrentHashMap 支持并发操作。所以结构更加复杂一些。

整个 ConcurrentHashMap 由一个个 segment 组成。segment 代表一段的意思。所以 ConcurrentHashMap 也叫分段锁。简单理解，ConcurrentHashMap 是由 segment 数组组成。segment 继承自 reentrantlock 来进行加锁，所以每个 segment 是线程安全的，整个 ConcurrentHashMap 就是线程安全的。

ConcurrentHashMap 与 HashMap 和 Hashtable 最大的不同在于：put 和 get 两次 Hash 到达指定的 HashEntry，第一次 hash 到达 Segment,第二次到达 Segment 里面的 Entry,然后在遍历 entry 链表.

2.CHM 的构造函数有几个？

public ConcurrentHashMap() {
}

public ConcurrentHashMap(int initialCapacity) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException();
    int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
               MAXIMUM_CAPACITY :
               tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
    this.sizeCtl = cap;
}


public ConcurrentHashMap(Map<? extends K, ? extends V> m) {
    this.sizeCtl = DEFAULT_CAPACITY;
    putAll(m);
}

public ConcurrentHashMap(int initialCapacity, float loadFactor) {
  	this(initialCapacity, loadFactor, 1);
}
//可设置初始容量和阈值和并发级别
public ConcurrentHashMap(int initialCapacity,
                         float loadFactor, int concurrencyLevel) {
    if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0)
        throw new IllegalArgumentException();
    if (initialCapacity < concurrencyLevel)   // Use at least as many bins
        initialCapacity = concurrencyLevel;   // as estimated threads
    long size = (long)(1.0 + (long)initialCapacity / loadFactor);
    int cap = (size >= (long)MAXIMUM_CAPACITY) ?
        MAXIMUM_CAPACITY : tableSizeFor((int)size);
    this.sizeCtl = cap;
}

concurrencyLevel:并发级别，并发数，segment 数。默认是 16，也就是说默认是 16 个 segments。

理论上来说，最多支持 16 个线程并发写。操作分布在不同的 segment 上，对单独的 segment 进行加锁处理，可以做到线程安全，可以在初始化的时候设置此值，设置之后不支持扩容。

3.jdk1.7 的 CHM 是如何进行锁操作的？

数据结构：ReentrantLock+Segment+HashEntry 组成，写的时候对单个 segment 加锁

4.jdk1.8 的 CHM 是如何保证并发的？

数据结构为数组+链表/红黑树，内部大量采用 cas 来实现。JDK8 中 ConcurrentHashMap 参考了 JDK8 HashMap 的实现，采用了数组+链表/红黑树的实现方式来设计，内部大量采用 CAS 操作。

CAS 是 compare and swap 的缩写，即我们所说的比较交换。cas 是一种基于锁的操作，而且是乐观锁。在 java 中锁分为乐观锁和悲观锁。悲观锁是将资源锁住，等一个之前获得锁的线程释放锁之后，下一个线程才可以访问。而乐观锁采取了一种宽泛的态度，通过某种方式不加锁来处理资源，比如通过给记录加 version 来获取数据，性能较悲观锁有很大的提高。

JDK8 中彻底放弃了 Segment 转而采用的是 Node，其设计思想也不再是 JDK1.7 中的分段锁思想。

Node:保存 key，value 及 key 的 hash 值的数据结构。其中 value 和 next 都用 volatile 修饰，保证并发的

可见性。

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    volatile V val;//并发可见性
    volatile Node<K,V> next;//并发可见性

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

5.jdk1.8 的 CHM 和 jdk1.7 的区别？

数据结构上的区别，在 jdk1.7 中使用的是 ReentrantLock+Segment+HashEntry ，在 jdk1.8 中使用的是 Node+CAS+synchronized+红黑树。

• JDK1.8 的实现降低锁的粒度，JDK1.7 版本锁的粒度是基于 Segment 的，包含多个 HashEntry，而 JDK1.8 锁的粒度就是 HashEntry（首节点）
• 取消了 segment 分段锁，采用数组+链表+红黑树。
• 1.7 中用 ReentrantLock+Segment 加锁，1.8 中使用的是 CAS+synchronized 加锁,对数组元素 Node 加锁。
• 在链表节点大于 8 时,且数组长度大于等于 64 时，会转为红黑树。数据量大时，hash 冲突加剧，性能下降。
• 查询时间复杂度，1.7 最坏时是单链表 O(n),1.8 是红黑树 O(logn)
• JDK1.8 版本的数据结构变得更加简单，使得操作也更加清晰流畅，因为已经使用 synchronized 来进行同步，所以不需要分段锁的概念，也就不需要 Segment 这种数据结构了，由于粒度的降低，实现的复杂度也增加了
• JDK1.8 使用红黑树来优化链表，基于长度很长的链表的遍历是一个很漫长的过程，而红黑树的遍历效率是很快的，代替一定阈值的链表，这样形成一个最佳拍档

6.Hashtable 和 CHM 在多线程下区别？

多线程环境下都是线程安全的，ConcurrentHashMap 的效率更高。

HashTable 使用一把锁处理并发问题，在多线程情况下，多个线程竞争同一个锁，效率较低，导致阻塞。

ConcurrentHashMap 分两个版本

• 1.7 使用分段锁，相当于把 HashMap 分成多段，每一段都拥有各自的锁，这样可以实现多线程访问。
• 1.8 采用了 cas 和 synchronized 加锁，锁粒度细化到元素本身，理论上是最高级别的并发。

7.CHM 的 get()为什么不需要加锁?

ConcurrentHashMap 的 get 操作可以无锁是由于 Node 的元素 val 和指针 next 是用 volatile 修饰的，在多线程环境下线程 A 修改结点的 val 或者新增节点的时候是对线程 B 可见的。

在 Node 上加 volatile 的目的是什么呢？
其实就是为了使得 Node 数组在扩容的时候对其他线程具有可见性而加的 volatile。

get 操作全程不需要加锁是因为 Node 的成员 val 是用 volatile 修饰的和 Node 用 volatile 修饰没有关系。
Node 用 volatile 修饰主要是保证在数组扩容的时候保证可见性。

8.CHM 是如何进行扩容的?

private transient volatile int sizeCtl;

通过构造函数可以发现 sizeCtl 变量经常出现，该变量通过查看 jdk 源码注释可知该变量主要控制初始化或扩容：

• -1，表示线程正在进行初始化操作。
• -(1+nThreads)，表示 n 个线程正在进行扩容。
• 0，默认值，后续在真正初始化的时候使用默认容量。
• 大于 0，初始化或扩容完成后下一次的扩容门槛。

private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
    int n = tab.length, stride;
    // 单核不拆分，下面讨论多核的情况
    // 计算步长，拆分任务n >>> 3 = n / 2^3
    // 先将n分为8份，然后等分给每个cpu，若最后计算的步长小于最小步长16，则设置为16
    if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
        stride = MIN_TRANSFER_STRIDE; // subdivide range
    if (nextTab == null) {            // initiating
        try {
            // 扩容 2倍
            @SuppressWarnings("unchecked")
            Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];
            nextTab = nt;
        } catch (Throwable ex) {      // try to cope with OOME
            sizeCtl = Integer.MAX_VALUE;
            return;
        }
        nextTable = nextTab;
        // transferIndex 记录迁移进度
        transferIndex = n;
    }
    int nextn = nextTab.length;
    ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
    // 从后面的迁移逻辑看到 迁移复制元素是逆序迁移
    // advance= true 则代表可继续向前一个位置迁移复制元素
    boolean advance = true;
    // 是否所有线程都全部迁移完毕，true则可以将nextTab赋值给table了
    boolean finishing = false; // to ensure sweep before committing nextTab
    // i 代表当前线程正在迁移的数组位置，bound代表它本次可以迁移的范围下限
    for (int i = 0, bound = 0;;) {
        Node<K,V> f; int fh;
        while (advance) {
            int nextIndex, nextBound;
           // （1）两种情况不需要继续向前一个位置迁移复制元素（逆序）：
            // ①i每次自减1，i>=bound说明本批次迁移未完成，不需要继续向前推进。
            // ②finishing标志为true，说明所有线程分配的迁移任务都已经完成了，则不需要向前推进。
            // 若 --i < bound，说明当前批次的迁移任务完成，可继续分配新范围的任务
            // 也就是一个线程可以多次分到任务，能者多劳。
            if (--i >= bound || finishing)
                // 向前一个位置迁移复制元素
                advance = false;
             //(2) 每次执行，都会把 transferIndex 最新的值同步给 nextIndex
            else if ((nextIndex = transferIndex) <= 0) {
                //若 transferIndex小于等于0，则说明原数组中所有位置的迁移任务都分配完毕（不代表所有位置都迁移完毕）
                //于是，需要跳出while循环，并把 i设为 -1，
                // 以跳到（4）判断正在处理的线程是否完成自己负责范围内迁移工作。
                i = -1;
                advance = false;
            }
            else if (U.compareAndSwapInt
                     (this, TRANSFERINDEX, nextIndex,
                      nextBound = (nextIndex > stride ?
                                   nextIndex - stride : 0))) {
                //（3）cas 设置TRANSFERINDEX，分配任务范围[nextBound,nextIndex)，任务的长度是stride
                // 举例，假设 n=64，即初始的transferIndex=64，stride=16
                // nextIndex=transferIndex=64，nextBound=nextIndex-stride=48
                // bound=48
                // i=63
                // 从后往前复制
                bound = nextBound;
                i = nextIndex - 1;
                advance = false;  // 本次任务分配完成，结束循环
            }
        }
        // （4）i已经越界了，整个数组的迁移任务已经全部分配完毕
        if (i < 0 || i >= n || i + n >= nextn) {
            int sc;
            if (finishing) {
                // 扩容完毕
                // nextTable置为空
                nextTable = null;
                // 新数组赋值给旧数组
                table = nextTab;
                // sizeCtl 设置为新的数组长度的 3/4.即 3/4 *2n
                sizeCtl = (n << 1) - (n >>> 1);
                return;
            }
            // 到这，说明所有的迁移任务都分配完了
            // 当前线程也已经完成了自己的迁移任务（无论参与了几次迁移），
            // 则sc-1，表明参与扩容的线程数减1
            if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
                // 迁移开始时，会设置 sc=(rs << RESIZE_STAMP_SHIFT) + 2
                // 每当有一个线程参与迁移，sc 就会加 1。
                // 因此，这里就是去校验当前 sc 是否和初始值相等。
                if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
                    // 不相等，当前线程扩容任务结束。
                    return;
                // 相等，说明还有一个线程还在扩容迁移（不一定是触发扩容的第一个线程）
                // 则当前线程会从后向前检查一遍，哪些位置的节点没有复制完，就帮忙一起复制。
                // 一圈扫描下来，肯定是全部迁移完毕了，则finishing可提前设置为true。
                finishing = advance = true;
                i = n; // recheck before commit
            }
        }
        else if ((f = tabAt(tab, i)) == null)
            // （5）若i的位置元素为空，就把占位节点设置为fwd标志。
            // 设置成功，advance置为true，向前推进复制
            advance = casTabAt(tab, i, null, fwd);
        else if ((fh = f.hash) == MOVED)
            // （6）若当前位置的头结点是 ForwardingNode ，则说明这个位置的所有节点已经迁移完成，
            // 可以继续向前迁移复制其他位置的节点
            advance = true; // already processed
        else {
            // （7）对tab[i]进行迁移，可能是链表 or 红黑树
            synchronized (f) {
                if (tabAt(tab, i) == f) {
                    Node<K,V> ln, hn;
                    if (fh >= 0) {
                        // 链表
                        int runBit = fh & n;
                        Node<K,V> lastRun = f;
                        // lastRun并不是一条链表的最后一个，一条链表的节点可以分为两类，
                        // 在循环中寻找lastRun的满足条件是链表中最后一个与前一个节点runBit不相等的节点作为lastRun，
                        // 而此时lastRun后面可能还有节点，但runBit都是和lastRun相等的节点。
                        // 这里找lastRun和java7是一样的
                        for (Node<K,V> p = f.next; p != null; p = p.next) {
                            // 计算p的位置
                            int b = p.hash & n;
                            if (b != runBit) {
                                // 和runBit不是同一位置
                                runBit = b;
                                lastRun = p;
                            }
                        }
                        // hash & n=0为低位节点，hash & n!=0为高位节点。
                        // 判断找到的lastRun是低位节点还是高位节点
                        if (runBit == 0) {
                            ln = lastRun;
                            hn = null;
                        }
                        else {
                            hn = lastRun;
                            ln = null;
                        }
                        // lastRun之前的结点因为fh&n不确定，所以全部需要再hash分配。
                        for (Node<K,V> p = f; p != lastRun; p = p.next) {
                            int ph = p.hash; K pk = p.key; V pv = p.val;
                            if ((ph & n) == 0)
                                ln = new Node<K,V>(ph, pk, pv, ln);
                            else
                                hn = new Node<K,V>(ph, pk, pv, hn);
                        }
                        setTabAt(nextTab, i, ln);
                        setTabAt(nextTab, i + n, hn);
                        setTabAt(tab, i, fwd);
                        advance = true;
                    }
                    else if (f instanceof TreeBin) {
                        // 是红黑树，
                        // 原理上和链表迁移的过程差不多，也是将节点分成高位节点和低位节点
                        TreeBin<K,V> t = (TreeBin<K,V>)f;
                        // lo低位树头节点，loTail低位树尾节点
                        // hi高位树头节点，hiTail高位树尾节点
                        TreeNode<K,V> lo = null, loTail = null;
                        TreeNode<K,V> hi = null, hiTail = null;
                        int lc = 0, hc = 0;
                        for (Node<K,V> e = t.first; e != null; e = e.next) {
                            int h = e.hash;
                            TreeNode<K,V> p = new TreeNode<K,V>
                                (h, e.key, e.val, null, null);
                            if ((h & n) == 0) {
                                if ((p.prev = loTail) == null)
                                    lo = p;
                                else
                                    loTail.next = p;
                                // 尾插法
                                loTail = p;
                                ++lc;
                            }
                            else {
                                if ((p.prev = hiTail) == null)
                                    hi = p;
                                else
                                    hiTail.next = p;
                                hiTail = p;
                                ++hc;
                            }
                        }
                        // 低位节点的个数 <= UNTREEIFY_THRESHOLD=6, 则树退为链表
                        // 否则判断是否有高位节点，无，则原先那棵树t就是一棵低位树，直接赋值给ln
                        // 有高位节点，则低位节点重新树化。
                        // 高位节点的判断同理
                        ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) :
                            (hc != 0) ? new TreeBin<K,V>(lo) : t;
                        hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :
                            (lc != 0) ? new TreeBin<K,V>(hi) : t;
                        setTabAt(nextTab, i, ln);
                        setTabAt(nextTab, i + n, hn);
                        setTabAt(tab, i, fwd);
                        advance = true;
                    }
                }
            }
        }
    }
}

9.CHM 的 put 方法源码?

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

final V putVal(K key, V value, boolean onlyIfAbsent) {
    if (key == null || value == null) throw new NullPointerException();
    // 1. 哈希值高低位扰动
    int hash = spread(key.hashCode());
    int binCount = 0;
    for (Node<K,V>[] tab = table;;) {
        Node<K,V> f; int n, i, fh;
        if (tab == null || (n = tab.length) == 0)
            // 2. tab 为空 初始化 懒汉模式
            tab = initTable();
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
            // 3. tab不为null，则通过(n - 1) & hash 计算 tab对应索引下标，找到node
            // node为null说明没有发生hash冲突，cas 设置新节点node到tab的对应位置，成功则结束循环
            if (casTabAt(tab, i, null,
                         new Node<K,V>(hash, key, value, null)))
                break;                   // no lock when adding to empty bin
        }
        else if ((fh = f.hash) == MOVED)
            // 4. 发现哈希值为MOVED时，
            // 说明数组正在扩容，帮助扩容，这个节点只可能是ForwardingNode
            tab = helpTransfer(tab, f);
        else {
            // 5.正常情况下发生哈希冲突
            V oldVal = null;
            synchronized (f) {
                // 再次检查i位置的节点是否还是f
                // 如果有变动则重新循环
                if (tabAt(tab, i) == f) {
                    if (fh >= 0) {
                        // 6. fh>=0 是链表
                        binCount = 1;
                        for (Node<K,V> e = f;; ++binCount) {
                            K ek;
                            if (e.hash == hash &&
                                ((ek = e.key) == key ||
                                 (ek != null && key.equals(ek)))) {
                                // 链表中已经有hash相等且（key地址相等 or key值相等）
                                // 则判断是否需要替换
                                // put onlyIfAbsent=false，新值替换旧值
                                // putIfAbsent onlyIfAbsent=true,新值不替换旧值
                                oldVal = e.val;
                                if (!onlyIfAbsent)
                                    e.val = value;
                                break;
                            }
                            // 解决hash冲突的方式
                            // 链表法，新节点放在了链表尾部（尾插法），这里和jdk1.7不一样
                            Node<K,V> pred = e;
                            if ((e = e.next) == null) {
                                pred.next = new Node<K,V>(hash, key,
                                                          value, null);
                                break;
                            }
                        }
                    }
                    else if (f instanceof TreeBin) {
                        // 7.红黑树
                        Node<K,V> p;
                        binCount = 2;
                        if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
                                                       value)) != null) {
                            // putTreeVal的返回值是已经存在的节点
                            // p != null 说明 key已经存在，看是否需要替换value
                            oldVal = p.val;
                            if (!onlyIfAbsent)
                                p.val = value;
                        }
                    }
                }
            }
            if (binCount != 0) {
                // 8. binCount，链表的长度>=8时 可能变为红黑树，也可能是扩容
                // 数组长度小于64时，是扩容数组
                if (binCount >= TREEIFY_THRESHOLD)
                    treeifyBin(tab, i);
                if (oldVal != null)
                    // 若旧值不为null，则说明是替换，不需要后面的addCount
                    return oldVal;
                break;
            }
        }
    }
    // 9. 元素数量+1
    addCount(1L, binCount);
    return null;
}

10.key 和 value 为什么不能为 null?

ConcurrentHashMap 中 key 和 value 为什么不能为 null 呢?下面从 HashMap 和 ConcurrentHashMap 的对比,详细说明.根据 HashMap 的源码可以知道,当 key 为 null 时，计算出的 hash 值为 0，value 放置在第 0 个桶上

//HashMap
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

根据 ConcurrentHashMap 源码可以知道,ConcurrentHashMap 没有像 HashMap 一样先计算 hash,先进行了判断 key 和 value 是否为 null,为 null 会抛出空值针异常,主要是因为存在二义性问题且 ConcurrentHashMap 没法解决

• 可能没有这个 key
• 可能有这个 key，只不过 value 为 null

因为 ConcurrentHashMap 是线程安全的，一般使用在并发环境下，你一开始 get 方法获取到 null 之后，再去调用 containsKey 方法，没法确保 get 方法和 containsKey 方法之间，没有别的线程来捣乱，刚好把你要查询的对象设置了进去或者删除掉了。

//ConcurrentHashMap
final V putVal(K key, V value, boolean onlyIfAbsent) {
  if (key == null || value == null) throw new NullPointerException();
  int hash = spread(key.hashCode());
  int binCount = 0;
  ......
}

11.jdk1.8 中 CHM 最大并发量

在 JDK1.8 中，ConcurrentHashMap 的并发性能得到了大幅提升，最大支持的并发量也有所增加。根据官方文档的描述，JDK1.8 中的 ConcurrentHashMap 最大可以同时支持并发读写操作的线程数是理论上的最大值，即 CPU 核心数乘以 2。

12.compute 方法

compute 方法具有原子性,保证 ConcurrentHashMap 的 get 和 put 的原子性。

compute方法有三个版本：

1. compute(K key, BiFunction<? super K,? super V,? extends V> remappingFunction)：

   • 这个方法会对给定的键执行指定的函数。
   • 如果键不存在，函数将不会被执行，且方法会返回null。
   • 如果函数返回的值为null，则键会被从ConcurrentHashMap中移除（如果存在的话）。
   • 如果函数返回的值不为null，则新值会与键相关联。

2. computeIfAbsent(K key, Function<? super K,? extends V> mappingFunction)：

   • 这个方法会在键不存在时执行指定的函数。
   • 如果键不存在，函数将被执行，返回的值会与键关联，并作为方法的返回值。
   • 如果键已经存在，方法不会执行函数，直接返回已存在的值。

3. computeIfPresent(K key, BiFunction<? super K,? super V,? extends V> remappingFunction)：

   • 这个方法会在键存在时执行指定的函数。
   • 如果键存在，函数将被执行，返回的值会与键关联，并作为方法的返回值。
   • 如果键不存在，方法不会执行函数，返回null。

这些compute方法允许你在多线程环境下以安全的方式更新ConcurrentHashMap中的键值对。由于它们的操作是原子性的，可以有效地避免竞态条件和数据不一致性问题。

public class Juc_29_question_ConcurrentHashMap_02 extends Thread {
    private static final ConcurrentHashMap<String, Integer> invokeMap = new ConcurrentHashMap<>();

    static {
        invokeMap.put("key", 0);
    }

    @Test
    public void test1() throws InterruptedException {
        for (int i = 0; i < 5; i++) {
            Juc_29_question_ConcurrentHashMap_02 thread = new Juc_29_question_ConcurrentHashMap_02();
            thread.start();
        }
    }

    @Override
    public void run() {
        System.out.println(invokeMap.compute("key", (key, value) -> value + 1));
    }
}

源码

public V compute(K key,
                     BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
        if (key == null || remappingFunction == null)
            throw new NullPointerException();
        int h = spread(key.hashCode());
        V val = null;
        int delta = 0;
        int binCount = 0;
        for (Node<K,V>[] tab = table;;) {
            Node<K,V> f; int n, i, fh;
            if (tab == null || (n = tab.length) == 0)
                tab = initTable();
            else if ((f = tabAt(tab, i = (n - 1) & h)) == null) {
                Node<K,V> r = new ReservationNode<K,V>();
                synchronized (r) {
                    if (casTabAt(tab, i, null, r)) {
                        binCount = 1;
                        Node<K,V> node = null;
                        try {
                            if ((val = remappingFunction.apply(key, null)) != null) {
                                delta = 1;
                                node = new Node<K,V>(h, key, val, null);
                            }
                        } finally {
                            setTabAt(tab, i, node);
                        }
                    }
                }
                if (binCount != 0)
                    break;
            }
            else if ((fh = f.hash) == MOVED)
                tab = helpTransfer(tab, f);
            else {
                synchronized (f) {
                    if (tabAt(tab, i) == f) {
                        if (fh >= 0) {
                            binCount = 1;
                            for (Node<K,V> e = f, pred = null;; ++binCount) {
                                K ek;
                                if (e.hash == h &&
                                    ((ek = e.key) == key ||
                                     (ek != null && key.equals(ek)))) {
                                    val = remappingFunction.apply(key, e.val);
                                    if (val != null)
                                        e.val = val;
                                    else {
                                        delta = -1;
                                        Node<K,V> en = e.next;
                                        if (pred != null)
                                            pred.next = en;
                                        else
                                            setTabAt(tab, i, en);
                                    }
                                    break;
                                }
                                pred = e;
                                if ((e = e.next) == null) {
                                    val = remappingFunction.apply(key, null);
                                    if (val != null) {
                                        delta = 1;
                                        pred.next =
                                            new Node<K,V>(h, key, val, null);
                                    }
                                    break;
                                }
                            }
                        }
                        else if (f instanceof TreeBin) {
                            binCount = 1;
                            TreeBin<K,V> t = (TreeBin<K,V>)f;
                            TreeNode<K,V> r, p;
                            if ((r = t.root) != null)
                                p = r.findTreeNode(h, key, null);
                            else
                                p = null;
                            V pv = (p == null) ? null : p.val;
                            val = remappingFunction.apply(key, pv);
                            if (val != null) {
                                if (p != null)
                                    p.val = val;
                                else {
                                    delta = 1;
                                    t.putTreeVal(h, key, val);
                                }
                            }
                            else if (p != null) {
                                delta = -1;
                                if (t.removeTreeNode(p))
                                    setTabAt(tab, i, untreeify(t.first));
                            }
                        }
                    }
                }
                if (binCount != 0) {
                    if (binCount >= TREEIFY_THRESHOLD)
                        treeifyBin(tab, i);
                    break;
                }
            }
        }
        if (delta != 0)
            addCount((long)delta, binCount);
        return val;
    }

或者

public class Juc_29_question_ConcurrentHashMap_01 extends Thread {
    private static final ConcurrentHashMap<String, Integer> invokeMap = new ConcurrentHashMap<>();
    private static final Object lock = new Object();  // 添加一个锁对象

    static {
        invokeMap.put("key", 0);
    }

    @Test
    public void test1() throws InterruptedException {
        for (int i = 0; i < 5; i++) {
            Juc_29_question_ConcurrentHashMap_01 thread = new Juc_29_question_ConcurrentHashMap_01();
            thread.start();
        }
    }

    @Override
    public void run() {
        synchronized (lock) {
            invokeMap.put("key", invokeMap.get("key") + 1);
            System.out.println(invokeMap);
        }
    }
}

13.computeIfAbsent

computeIfAbsent 是一个在 Java 编程语言中用于 Map 接口的方法，它允许你根据指定的键执行一个计算操作，如果该键在 Map 中不存在的话。如果键存在，则方法返回与该键关联的值；如果键不存在，则方法会执行给定的计算函数以生成一个值，并将键和生成的值放入 Map 中，然后返回该值。

以下是 computeIfAbsent 方法的签名：

V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction)

其中：

• key 是你想要在 Map 中查找或添加的键。
• mappingFunction 是一个函数，它接受一个键作为输入并返回一个值。如果键不存在于 Map 中，这个函数会被调用，生成一个值，然后将该键和生成的值放入 Map 中。如果键已经存在于 Map 中，这个函数不会被调用，方法会直接返回与该键关联的值。

这个方法的用途在于，当你需要按需计算某个键对应的值时，可以使用它来避免重复计算，同时保持代码的简洁性和可读性。

以下是一个简单的示例，展示了如何使用 computeIfAbsent 方法：

import java.util.*;

public class ComputeIfAbsentExample {
    public static void main(String[] args) {
        Map<String, List<Integer>> map = new HashMap<>();

        // 使用 computeIfAbsent 添加值到 Map 中
      	//这里add是在外层,注意看清楚写法
        map.computeIfAbsent("even", key -> new ArrayList<>()).add(2);
        map.computeIfAbsent("even", key -> new ArrayList<>()).add(4);

        map.computeIfAbsent("odd", key -> new ArrayList<>()).add(1);
        map.computeIfAbsent("odd", key -> new ArrayList<>()).add(3);

        System.out.println(map); // 输出: {even=[2, 4], odd=[1, 3]}
    }
}

在这个示例中，我们创建了一个 Map，然后使用 computeIfAbsent 方法将偶数和奇数分别添加到 “even” 和 “odd” 键所对应的列表中。由于 “even” 和 “odd” 键在 Map 中不存在，计算函数会被调用来生成一个新的列表，并将值添加到列表中。最后，我们输出了 Map，可以看到生成的结果。

14.computeIfPresent

computeIfPresent 是一个在 Java 编程语言中用于 java.util.Map 接口的方法。它是 Java 8 引入的一种函数式编程风格的方法，用于在映射中根据给定的键执行一个函数来更新键对应的值。

以下是 computeIfPresent 方法的方法签名：

V computeIfPresent(K key, BiFunction<? super K,? super V,? extends V> remappingFunction)

这里的参数解释如下：

• key：要操作的键。
• remappingFunction：一个函数，接受两个参数，即键和当前与键相关联的值。它返回一个新的值，该值将替代旧值作为键的新值。如果函数返回 null，则表示删除键和其关联的值。

computeIfPresent 的作用是，当指定的键在映射中存在时，使用 remappingFunction 对当前值进行处理，然后将处理后的新值与键关联。如果键不存在，该方法不会执行任何操作。

以下是一个简单的示例，展示了 computeIfPresent 的用法：

import java.util.HashMap;
import java.util.Map;

public class ComputeIfPresentExample {
    public static void main(String[] args) {
        Map<String, Integer> map = new HashMap<>();
        map.put("one", 1);
        map.put("two", 2);

        // 使用 computeIfPresent 更新值
        map.computeIfPresent("one", (key, value) -> value + 10);

        // 输出更新后的映射
        System.out.println(map); // 输出: {one=11, two=2}

        // 尝试使用 computeIfPresent 更新不存在的键
        map.computeIfPresent("three", (key, value) -> value + 10);

        // 输出不变，因为键 "three" 不存在
        System.out.println(map); // 输出: {one=11, two=2}
    }
}

在上述示例中，computeIfPresent 方法用于更新键 “one” 对应的值，然后再尝试对不存在的键 “three” 使用该方法，但由于键 “three” 不存在，没有发生任何变化。

15.putIfAbsent

基本介绍:

在 Java 中，putIfAbsent 和 getOrDefault 是用于 Map 接口的两个不同的方法，下面分别解释 putIfAbsent 和 getOrDefault 的用法。

putIfAbsent 方法:

putIfAbsent 方法用于向映射中添加键值对，但仅在指定的键尚不存在时才添加。如果指定的键已经存在，则不会执行添加操作。该方法常用于确保在并发环境中不会重复添加相同的键值对。以下是示例代码：

import java.util.HashMap;
import java.util.Map;

public class PutIfAbsentExample {
    public static void main(String[] args) {
        Map<String, Integer> map = new HashMap<>();

        map.put("key1", 10);
        map.putIfAbsent("key1", 20); // 不会覆盖现有键值对
        map.putIfAbsent("key2", 30);

        System.out.println(map); // 输出: {key1=10, key2=30}
    }
}

putIfAbsent 的并发安全性:

putIfAbsent 方法在 Java 中通常用于并发环境中的 ConcurrentMap 实现，例如 ConcurrentHashMap。这个方法的设计是为了在多线程环境下安全地执行添加操作，确保在同一时间只有一个线程能够成功地将键值对添加到映射中。

在 ConcurrentHashMap 中，putIfAbsent 方法使用了一种称为 “compare-and-swap”（CAS）的机制来确保原子性。CAS 是一种多线程同步的技术，它比传统的锁定机制更轻量级。

在 putIfAbsent 方法中，首先会尝试用给定的键检索值，然后只有在该键不存在时才尝试添加。整个过程是原子性的，因此在并发情况下，多个线程可以同时调用 putIfAbsent 方法，但只有一个线程最终会成功地将键值对添加到映射中。

以下是一个简单的示例，演示了在并发情况下使用 ConcurrentHashMap 中的 putIfAbsent 方法：

import java.util.concurrent.ConcurrentHashMap;

public class ConcurrentExample {
    public static void main(String[] args) {
        ConcurrentHashMap<String, Integer> concurrentMap = new ConcurrentHashMap<>();

        // 线程1尝试添加键值对
        new Thread(() -> {
            Integer value = concurrentMap.putIfAbsent("key", 1);
            System.out.println("Thread 1 - Added: " + value);
        }).start();

        // 线程2尝试添加相同的键值对
        new Thread(() -> {
            Integer value = concurrentMap.putIfAbsent("key", 2);
            System.out.println("Thread 2 - Added: " + value);
        }).start();
    }
}

在这个例子中，只有一个线程最终会成功地将键值对添加到映射中，而另一个线程会得到 putIfAbsent 方法返回的已存在的值。

putIfAbsent 方法在 ConcurrentMap 中提供了一种并发安全的方式来添加元素，适用于多线程环境。

16.getOrDefault

getOrDefault 方法:

getOrDefault 方法用于获取指定键的值，如果该键不存在，则返回一个默认值。这个方法对于避免检查键是否存在并处理默认值很有用。

示例代码:

import java.util.HashMap;
import java.util.Map;

public class GetOrDefaultExample {
    public static void main(String[] args) {
        Map<String, Integer> map = new HashMap<>();

        map.put("key1", 10);
        map.put("key2", 20);

        int value1 = map.getOrDefault("key1", 0); // 存在的键，返回对应的值
        int value3 = map.getOrDefault("key3", 0); // 不存在的键，返回默认值 0

        System.out.println(value1); // 输出: 10
        System.out.println(value3); // 输出: 0
    }
}

使用场景:

getOrDefault 方法在 Java 中的 Map 接口中定义，它用于获取指定键对应的值，如果键不存在，则返回一个默认值。这个方法在许多场景下都非常有用，特别是在处理默认值或避免空指针异常的情况下。以下是一些常用的地方：

1. 避免空指针异常： 当你使用传统的 get 方法获取值时，如果键不存在，返回的是 null。使用 getOrDefault 可以避免因为空值而引发空指针异常。

   Map<String, Integer> map = new HashMap<>();
   Integer value = map.getOrDefault("key", 0); // 如果键不存在，返回默认值 0
   

2. 处理默认值： 当你需要获取一个值，如果键不存在则使用一个默认值，而不是 null。

   Map<String, String> config = getConfig(); // 从某处获取配置信息的映射
   String username = config.getOrDefault("username", "guest"); // 如果键不存在，返回默认用户名 "guest"
   

3. 统计元素出现的次数： 在统计元素出现次数时，可以使用 getOrDefault 来为不存在的元素提供一个默认的计数值。

   Map<String, Integer> wordCount = new HashMap<>();
   String word = "apple";
   
   // 统计单词出现次数
   wordCount.put(word, wordCount.getOrDefault(word, 0) + 1);
   

4. 初始化映射： 在初始化映射时，可以使用 getOrDefault 设置默认值。

   Map<String, List<String>> userRoles = new HashMap<>();
   
   // 初始化用户角色列表
   userRoles.put("admin", userRoles.getOrDefault("admin", new ArrayList<>()));
   

getOrDefault 是一个很方便的方法，可以简化代码，提高可读性，并且在处理映射中的键值对时提供了灵活性。