Java 源码重读系列之 ConcurrentHashMap

古城微笑少年丶 2023-09-27 19:51 108阅读 0赞

### 0. 第一个属性 serialPersistentFields ###

因为 ConcurrentHashMap 的逻辑比较复杂，所以我们直接从 `serialPersistentFields` 属性说起，它之前的这些属性等用到的时候我们再看就好了，你只要知道 这个属性之前还有一堆固定的属性就好了。

`serialPersistentFields` 属性是一个 `ObjectStreamField` 的数组，而且默认添加了三个元素。

private static final ObjectStreamField[] serialPersistentFields = {
            new ObjectStreamField("segments", Segment[].class),
            new ObjectStreamField("segmentMask", Integer.TYPE),
            new ObjectStreamField("segmentShift", Integer.TYPE)
        };
    复制代码

我们点到 `ObjectStreamField` 类中去，它的类头有一段这样的描述：

* A description of a Serializable field from a Serializable class.  An array
     * of ObjectStreamFields is used to declare the Serializable fields of a class.
    复制代码

简单翻译一下就是，一个序列化类中可以序列化属性的描述。ObjectStreamFields 数组声明了这个类的可序列化的字段。

好了，这个类我们看到这就可以了，而且也知道了 ConcurrentHashMap 中 `serialPersistentFields` 属性的作用。就是声明了一下 ConcurrentHashMap 里有三个 属性可以被序列化。这三个属性分别是`segments、segmentMask、segmentShift` 。结束~

### 1. spread() ###

继续往下是 Node 类的定义，没什么好说的，我们遇到了第一个方法。

static final int spread(int h) {
            return (h ^ (h >>> 16)) & HASH_BITS;
        }
    复制代码

都是一些位运算。解释一下，这个方法会将 h 和 h 右移 16 位的数值进行异或（^）操作，得到的结果与 HASH\_BITS 进行与（&）操作。和 HASH\_BITS 进行与（&）操作，作用就是保证返回的结果的最高位一定是 0，也就是说，返回的结果一定是正数。（如果你对位运算没有什么概念的话，也可以不用纠结这个方法，这个方法的作用就是，给一个数，返回另外一个数。）

### 2. tabAt()、casTabAt()、setTabAt() ###

@SuppressWarnings("unchecked")
        static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
            return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
        }
    
        static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
                                            Node<K,V> c, Node<K,V> v) {
            return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
        }
    
        static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) {
            U.putObjectVolatile(tab, ((long)i << ASHIFT) + ABASE, v);
        }
    复制代码

这几个是其实是 ConcurrentHashMap 的核心操作方法。`tabAt()` 是获取，`casTabAt()` 是更新，并且是基于 CAS 方式实现的更新。`setTabAt()` 是插入。这些实现都使用了大名鼎鼎的 `sun.misc.Unsafe` 类。

如果你对这个类不熟悉的话，其实可以简单理解，这个类里的一些方法都是线程的。因为这个类提供的是一些硬件级别的原子操作。简单来说，`sun.misc.Unsafe` 类提供的方法都是线程安全的。理解到这里就可以了，再深入的内容，就不再本文范围内了。继续往下。

### 2. counterCells ###

继续往下的话，就看到了 `table` 和 `nextTable`，没什么说的，这个就是存储数据的数组了，至于 `nextTable`，通过注释可以看到，这个变量应该是只在扩容时使用到了，等用到的时候再说。

继续往下呢就是一些`int` 类型的值了，通过名字和注释也看不出来什么，直接跳过。等用到的时候再说。继续往下的话我们就看到了一个 `CounterCell[]` 数组了，点到这个类的定义，可以看到以下代码。

@sun.misc.Contended static final class CounterCell {
            volatile long value;
            CounterCell(long x) { value = x; }
        }
    复制代码

好像也没有多复杂，就一个使用了 `volatile` 标记的 数值。至于 `sun.misc.Contended` 注解，主要是解决 CPU **伪缓存** 问题的，提高性能和效率使用的，可以先不用关注。

但是，如果你阅读一下注释的话，就会发现这里面大有文章。涉及到两个非常复杂的东西：`LongAdder and Striped64`。关于 `LongAdder and Striped64` 的内容也不在本文范围内，有兴趣的话可以搜一下相关的文章。不了解也没有关系，不影响阅读。我们继续往下看。

### 3. keySet、values、entrySet ###

再往下就是几个 view 变量了。

// views
        private transient KeySetView<K,V> keySet;
        private transient ValuesView<K,V> values;
        private transient EntrySetView<K,V> entrySet;
    复制代码

看名字也应该能猜出来，这些变量应该是跟 HashMap 的 `keySet()、values()、entrySet()` 几个方法的作用类似。如果你点到它的定义就会看到，这几个类都继承了 `CollectionView` 这个类。

abstract static class CollectionView<K,V,E>
            implements Collection<E>, java.io.Serializable {
            private static final long serialVersionUID = 7249069246763182397L;
            final ConcurrentHashMap<K,V> map;
            CollectionView(ConcurrentHashMap<K,V> map)  { this.map = map; }
    
            //... ...
    复制代码

只看前面几行就可以了，内部有一个 `ConcurrentHashMap` 类型的变量，而且 `CollectionView` 只有一个带有 `ConcurrentHashMap` 参数的构造方法。盲猜也能猜到，上面的 xxxView 类内部操作的也都是 ConcurrentHashMap 存储的数据。了解这些就可以了，我们继续往下看。

### 3. 构造方法 ###

第一个是个空构造方法没有什么好说的，先看第二个。

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;
        }
    复制代码

通过注释和名称我们应该能够知道，这个构造方法可以初始化 Map 的容量。有意思的是，计算 `cap` 的方法。不知道你还记不记得 HashMap 的初始容量的构造方法是怎么计算容量的。代码在下面

this.threshold = tableSizeFor(initialCapacity);
    复制代码

而 ConcurrentHashMap 则是将 initialCapacity 加上了 initialCapacity 的一半又加了 1 作为 `tableSizeFor` 的参数。其实就是为了解决 HashMap 存在的可能出现两次扩容的问题。

**注意**，这里使用的是 `>>>`，不是 `>>`。`>>>` 的含义是**无符号右移**。它会把最高位表示正负的值也会右移，然后补 0。 所以 `>>>` 之后，一定是正数。如果 `>>>` 之前是正数的话，结果跟 `>>` 一致。如果是负数的话，就会出现一个很奇怪的正数。这是因为最高位表示负数的 1 也跟着右移了。由于代码里已经判断了小于 0 ，所以我们目前先按照除 2 理解即可。

还有一个点是，从代码来看，ConcurrentHashMap 的最大容量 **好像** 是用 `sizeCtl` 表示的。但是，如果仅仅是表示最大容量，为什么会定义一个这么奇怪的名字呢？ `Ctl` 的后缀应该是 `control` 的简写。具体是怎么控制的呢？

继续往下，我们先跳过带有 Map 参数的构造方法，因为这个涉及到 `putAll()` 方法。

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;
        }
    复制代码

这两个构造方法其实可以算做一个，我们直接看下面那个复杂的。

先判断了一下参数的取值，然后更新了一下 `initialCapacity` 参数，然后根据参数计算 `size`，考虑到 `loadFactor` 可能小于 1，导致 int 值越界，所以转成了 long 类型。

关于 `concurrencyLevel`，给的注释是：并发更新线程的预估数量。那上面那段判断更新就不难理解了。假如我预估会有 20 个线程同时更新这个初始容量为 15 的 Map，这个时候的初始容量会自动的改为 20 。

好像没有什么问题？有意思的是， `loadFactor` 这个参数竟然没有保存！！ 加载因子没有保存，那什么时候触发扩容呢？我们继续往下看。

### 4. putAll() ###

回到带有 Map 参数的构造方法。

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

没有什么复杂的，指定了下默认的初始容量（16）就直接 `putAll(m);` 了。

public void putAll(Map<? extends K, ? extends V> m) {
            tryPresize(m.size());
            for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
                putVal(e.getKey(), e.getValue(), false);
        }
    复制代码

好像也不难，先执行 `tryPresize(m.size());` 应该是初始扩容， 然后再 for 循环进行 `putVal()` 操作。