jdk collection concurrenthashmap

ConcurrentHashMap 的实现

初始化

有参构造

public class ConcurrentHashMap<K, V> extends AbstractMap<K, V>
        implements ConcurrentMap<K, V>, Serializable {
    private static final float LOAD_FACTOR = 0.75f;
    private transient volatile int sizeCtl;

    public ConcurrentHashMap(int initialCapacity) {
        this(initialCapacity, LOAD_FACTOR, 1);
    }

    public ConcurrentHashMap(int initialCapacity,
                             float loadFactor, int concurrencyLevel) {
        if (initialCapacity < concurrencyLevel) {
            initialCapacity = concurrencyLevel;
        }
        // 例如 initialCapacity 的值是 100，那么 size = 1 + 100 / 0.75 = 134
        long size = (long) (1.0 + (long) initialCapacity / loadFactor);
        // 容量是 2 的倍数
        int cap = (size >= (long) MAXIMUM_CAPACITY) ?
                MAXIMUM_CAPACITY : tableSizeFor((int) size);
        // sizeCtl 是 256
        this.sizeCtl = cap;
    }

    // 和 hashMap 一样，返回 > c 的一个 2^n 值
    private static final int tableSizeFor(int c) {
        int n = -1 >>> Integer.numberOfLeadingZeros(c - 1);
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }
}

无参构造

public class ConcurrentHashMap<K, V> extends AbstractMap<K, V>
        implements ConcurrentMap<K, V>, Serializable {
    public ConcurrentHashMap() {
    }
}

无参构造相较于有参构造，没有对 sizeCtl 进行赋值，而是在以下位置处理

public class ConcurrentHashMap<K, V> extends AbstractMap<K, V>
        implements ConcurrentMap<K, V>, Serializable {
    private static final int DEFAULT_CAPACITY = 16;
    private static final Unsafe U = Unsafe.getUnsafe();
    transient volatile Node<K, V>[] table;
    private static final long SIZECTL;

    private final Node<K, V>[] initTable() {
        Node<K, V>[] tab;
        int sc;
        while ((tab = table) == null || tab.length == 0) {
            if ((sc = sizeCtl) < 0) {
                Thread.yield();
            } else if (U.compareAndSetInt(this, SIZECTL, sc, -1)) {
                // 通过 cas 先把 sizeCtl 的值设置为 -1
                // 从而实现了加锁的效果
                if ((tab = table) == null || tab.length == 0) {
                    // 默认值是 16
                    int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
                    // 数组默认大小是 16
                    Node<K, V>[] nt = (Node<K, V>[]) new Node<?, ?>[n];
                    table = tab = nt;
                    // 相当于 n - n/4，默认值是 16 的话，sc = 12
                    sc = n - (n >>> 2);
                }
                // 由于只能有一个线程加锁成功，所以直接赋值没毛病
                sizeCtl = sc;
                break;
            }
        }
    }
}

size 的计算

public class ConcurrentHashMap<K, V> extends AbstractMap<K, V>
        implements ConcurrentMap<K, V>, Serializable {
    private transient volatile CounterCell[] counterCells;
    private transient volatile long baseCount;

    public int size() {
        long n = sumCount();
        return ((n < 0L) ? 0 :
                (n > (long) Integer.MAX_VALUE) ? Integer.MAX_VALUE :
                        (int) n);
    }

    final long sumCount() {
        CounterCell[] cs = counterCells;
        long sum = baseCount;
        if (cs != null) {
            for (CounterCell c : cs)
                if (c != null)
                    sum += c.value;
        }
        return sum;
    }
}

需要回答两个问题，baseCount 的变更，counterCells 的初始化，以及 counterCells 的变化。

baseCount 的变更

• 也就是说，默认无竞争的情况下，会直接更新 baseCount 的值，出现竞争则随机一个位置并执行 inc。
• CounterCell[] 的默认大小是 2

public class ConcurrentHashMap<K, V> extends AbstractMap<K, V>
        implements ConcurrentMap<K, V>, Serializable {
    private final void addCount(long x, int check) {
        CounterCell[] cs;
        long b, s;
        if ((cs = counterCells) != null ||
                !U.compareAndSetLong(this, BASECOUNT, b = baseCount, s = b + x)) {
            // 假设 x 的值是 1，baseCount 的值是 0
            // 则 s = b + x == 1
            // 所以上面就是在尝试把 baseCount 从 0 变成 1
            // 但是操作失败了，所以进入了这里

            CounterCell c;
            long v;
            int m;
            boolean uncontended = true;
            // m = cs 的长度 -1
            if (cs == null || (m = cs.length - 1) < 0 ||
                    // 首先 ThreadLocalRandom.getProbe() & m 等同于随机一个数，对 cs 长度取模
                    // c 是数组的任意元素，且此时 cs 不为空
                    (c = cs[ThreadLocalRandom.getProbe() & m]) == null ||
                    // c 不为空，v 是 c 的旧值，则 v + x 等于新值，然后 cas 对 c 的 value 字段赋值
                    !(uncontended = U.compareAndSetLong(c, CELLVALUE, v = c.value, v + x))) {
                // 大概率会因为  cs 为空而进来
                fullAddCount(x, uncontended);
                return;
            }
        }
    }
}

put 中的竞争

public class ConcurrentHashMap<K, V> extends AbstractMap<K, V>
        implements ConcurrentMap<K, V>, Serializable {
    public V put(K key, V value) {
        return putVal(key, value, false);
    }

    final V putVal(K key, V value, boolean onlyIfAbsent) {
        for (Node<K, V>[] tab = table; ; ) {
            Node<K, V> f;
            f = tabAt(tab, i = (n - 1) & hash);
            V oldVal = null;
            synchronized (f) {

            }
        }

    }
}