您现在的位置是：首页 > Java

当前栏目

ConcurrentHashMap源码解析

2023-02-18 16:34:05 时间

转载请以链接形式标明出处：本文出自:103style的博客

base on jdk_1.8.0_77

ConcurrentHashMap简介

ConcurrentHashMap 是在 HashMap 的线程安全的版本，不允许 空键空值。

和HashMap类似，ConcurrentHashMap使用了一个table来存储Node，ConcurrentHashMap同样使用记录的key的hashCode来寻找记录的存储index，而处理哈希冲突的方式与HashMap也是类似的，冲突的记录将被存储在同一个位置上，形成一条链表，当链表的长度大于8的时候会将链表转化为一棵 红黑树，从而将查找的复杂度从O(N)降到了O(lgN)。

接下来将详细分析ConcurrentHashMap的主要操作方法，以及ConcurrentHashMap是如何保证在并发环境下的线程安全的。

ConcurrentHashMap的常量介绍

static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; 能转化为数组的最大长度 231 -1 - 8.
private static final int DEFAULT_CONCURRENCY_LEVEL = 16; 默认的并发等级
private static final int MIN_TRANSFER_STRIDE = 16; 最小迁移步幅，只在transfer方法中用到
private static final int RESIZE_STAMP_BITS = 16; 用于记录sizeCtl中的 resize stamp
private static final int MAX_RESIZERS = (1 << (32 - RESIZE_STAMP_BITS)) - 1; 参与resize的最大线程数，如果是默认值，那么位 (1 << (32-16)) - 1 = 32 - 1 = 31
private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS; 用于记录sizeCtl中的 resize stamp偏移位
static final int HASH_BITS = 0x7fffffff; 哈希散列的值

和 HashMap 相同的常量：

//链表树化的阈值
static final int TREEIFY_THRESHOLD = 8;
//树边链表的阈值
static final int UNTREEIFY_THRESHOLD = 6;
//树化时的最小容量
static final int MIN_TREEIFY_CAPACITY = 64;
//最大容量
private static final int MAXIMUM_CAPACITY = 1 << 30;
//默认容量
private static final int DEFAULT_CAPACITY = 16;
//负载因子
private static final float LOAD_FACTOR = 0.75f;

ConcurrentHashMap的相关函数

spread(int h)：散列计算
tableSizeFor(int c)：根据传入的值计算ConcurrentHashMap的容量
size()：计算ConcurrentHashMap的大小
initTable()：初始化table
get(Object key)：取数据
put(K key, V value)：存数据
remove(Object key)：移除数据

spread(int h) 散列计算

作用同HashMap的 hash方法。

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

tableSizeFor(int c) 根据传入的值计算容量

即为计算大于等于传入数的最小的 2n 的值。

private static final int tableSizeFor(int c) {
    int n = c - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

size() 计算大小

对CounterCell数组中每一项求和。

/**
 * Table of counter cells. When non-null, size is a power of 2.
 */
private transient volatile CounterCell[] counterCells;
static final class CounterCell {
    volatile long value;
    CounterCell(long x) { value = x; }
}
public int size() {
    long n = sumCount();
    return ((n < 0L) ? 0 :
            (n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE :
                    (int)n);
}
final long sumCount() {
    CounterCell[] as = counterCells; CounterCell a;
    long sum = baseCount;
    if (as != null) {
        for (int i = 0; i < as.length; ++i) {
            if ((a = as[i]) != null)
                sum += a.value;
        }
    }
    return sum;
}

initTable() 初始化table

(1.0) 当sizeCtl < 0时，则会让出CPU的时间，等待下次重试。
(2.0) 当sizeCtl >= 0时，则通过 CAS 原子操作将 sizeCtl 设置为 -1。
(3.0) 设置成功之后，如果table为空，则初始化对应长度的 Node数组。并将当前容量能保存的最大数量(n * LOAD_FACTOR)赋值给sizeCtl

//-1：正在初始化 ,其他小于0的数则表示正在调整大小
private transient volatile int sizeCtl;
//Initializes table, using the size recorded in sizeCtl.
private final Node<K,V>[] initTable() {
    Node<K,V>[] tab; int sc;
    while ((tab = table) == null || tab.length == 0) {
        if ((sc = sizeCtl) < 0)//1.0
            Thread.yield(); // lost initialization race; just spin
        else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {//2.0
            try {
                if ((tab = table) == null || tab.length == 0) {//3.0
                    int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
                    @SuppressWarnings("unchecked")
                    Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
                    table = tab = nt;
                    sc = n - (n >>> 2);
                }
            } finally {
                sizeCtl = sc;
            }
            break;
        }
    }
    return tab;
}

get(Object key) 取数据

和HashMap 类似，当前的索引处时要获取的值则返回当前值，否则遍历链表。

public V get(Object key) {
    Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
    int h = spread(key.hashCode());
    if ((tab = table) != null && (n = tab.length) > 0 &&
            (e = tabAt(tab, (n - 1) & h)) != null) {
        if ((eh = e.hash) == h) {
            if ((ek = e.key) == key || (ek != null && key.equals(ek)))
                return e.val;
        }
        else if (eh < 0)
            return (p = e.find(h, key)) != null ? p.val : null;
        while ((e = e.next) != null) {
            if (e.hash == h &&
                    ((ek = e.key) == key || (ek != null && key.equals(ek))))
                return e.val;
        }
    }
    return null;
}

put(K key, V value) 存数据

public V put(K key, V value) {
    return putVal(key, value, false);
}
/** Implementation for put and putIfAbsent */
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;
    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) & hash)) == null) {
            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)
            tab = helpTransfer(tab, f);
        else {
            V oldVal = null;
            synchronized (f) {
                if (tabAt(tab, i) == f) {
                    if (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)))) {
                                oldVal = e.val;
                                if (!onlyIfAbsent)
                                    e.val = value;
                                break;
                            }
                            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) {
                        Node<K,V> p;
                        binCount = 2;
                        if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
                                value)) != null) {
                            oldVal = p.val;
                            if (!onlyIfAbsent)
                                p.val = value;
                        }
                    }
                    else if (f instanceof ReservationNode)
                        throw new IllegalStateException("Recursive update");
                }
            }
            if (binCount != 0) {
                if (binCount >= TREEIFY_THRESHOLD)
                    treeifyBin(tab, i);
                if (oldVal != null)
                    return oldVal;
                break;
            }
        }
    }
    addCount(1L, binCount);
    return null;
}

remove(Object key) 移除数据

public V remove(Object key) {
    return replaceNode(key, null, null);
}
final V replaceNode(Object key, V value, Object cv) {
    int hash = spread(key.hashCode());
    for (Node<K, V>[] tab = table; ; ) {
        Node<K, V> f;
        int n, i, fh;
        if (tab == null || (n = tab.length) == 0 ||
                (f = tabAt(tab, i = (n - 1) & hash)) == null)
            break;
        else if ((fh = f.hash) == MOVED)
            tab = helpTransfer(tab, f);
        else {
            V oldVal = null;
            boolean validated = false;
            synchronized (f) {
                if (tabAt(tab, i) == f) {
                    if (fh >= 0) {
                        validated = true;
                        for (Node<K, V> e = f, pred = null; ; ) {
                            K ek;
                            if (e.hash == hash &&
                                    ((ek = e.key) == key ||
                                            (ek != null && key.equals(ek)))) {
                                V ev = e.val;
                                if (cv == null || cv == ev ||
                                        (ev != null && cv.equals(ev))) {
                                    oldVal = ev;
                                    if (value != null)
                                        e.val = value;
                                    else if (pred != null)
                                        pred.next = e.next;
                                    else
                                        setTabAt(tab, i, e.next);
                                }
                                break;
                            }
                            pred = e;
                            if ((e = e.next) == null)
                                break;
                        }
                    } else if (f instanceof TreeBin) {
                        validated = true;
                        TreeBin<K, V> t = (TreeBin<K, V>) f;
                        TreeNode<K, V> r, p;
                        if ((r = t.root) != null &&
                                (p = r.findTreeNode(hash, key, null)) != null) {
                            V pv = p.val;
                            if (cv == null || cv == pv ||
                                    (pv != null && cv.equals(pv))) {
                                oldVal = pv;
                                if (value != null)
                                    p.val = value;
                                else if (t.removeTreeNode(p))
                                    setTabAt(tab, i, untreeify(t.first));
                            }
                        }
                    } else if (f instanceof ReservationNode)
                        throw new IllegalStateException("Recursive update");
                }
            }
            if (validated) {
                if (oldVal != null) {
                    if (value == null)
                        addCount(-1L, -1);
                    return oldVal;
                }
                break;
            }
        }
    }
    return null;
}

小结

通过上面对 ConcurrentHashMap 添加和删除数据 的方法的介绍，我们知道在对其进行 写操作 的时候，会对当前索引出的节点通过 CAS 或者 synchronized 来实现多线程同步。在读取数据的方法则不会做这些同步操作。

参考文章

Java 8 ConcurrentHashMap源码分析

以上

猜你喜欢

深耕宽带无线路由细分领域深圳信丰伟业创新研发铸就行业标杆
UDP/TCP 包的大小限制是多少？
几种用jLink命令行烧录hex文件的方法
深耕热管高效散热细分领域，广东新创意科技助推电子行业蓬勃发展
图文详解STM32单片机远程升级
熟悉又陌生的arm 编译器详解（armcc/armclang）
STM32高级开发——使用DFU方案
MDK Keil使用GCC编译图文详解
嵌入式开发如何统计运行占据内存
聊聊程序分散加载启动的奥秘
UniPro即时通信集成机器人让远程办公信息管理效率加速
c语言实现任务调度器
分支路径图调度框架在 vivo 效果广告业务的落地实践
C++内存模型，我们常说的堆栈究竟指什么？
原来C++变量在内存中不是紧密排列的，聊聊内存对齐
刷题时遇到了内存超界？分享一点小技巧
LeetCode周赛323，LeetCode官方的福利专场
常见的算法优化套路，用空间换时间
算法初学者的第一个数据结构，数组和vector
老梁学算法三年都会翻车的二分法，如何一朝顿悟？

zl程序教程