Java中ConcurrentHashMap源码解读

>>强大,10k+点赞的 SpringBoot 后台管理系统竟然出了详细教程!

ConcurrentHashMap

结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// 存储容器
transient volatile Node<K,V>[] table;
private transient volatile Node<K,V>[] nextTable;
// 计数map中元素个数
private transient volatile CounterCell[] counterCells;
// 负数时:-1代表正在初始化,-N代表有N-1个线程正在进行扩容
// 0时:table未被初始化
// 正数时:已初始化或下一次进行扩容的大小
private transient volatile int sizeCtl;
// 段/槽/片
static class Segment<K,V> extends ReentrantLock implements Serializable {}
// 节点类,变量使用了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;
}
// 树节点类
static final class TreeNode<K,V> extends Node<K,V> {
    TreeNode<K,V> parent;  // red-black tree links
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;    // needed to unlink next upon deletion
    boolean red;
}
  • 在HashMap的基础上,使用同步代码块,CAS思想保证线程安全,不再使用Java7中的Segment概念
  • 键或值不允许为空,否则会报NPE异常
  • 线程安全
  • Node 数据结构和 HashMap 基本相同, ConcurrentHashMap 的 Node 链表只允许对数据进行查找,不允许进行修改。
  • Node 数组也加上了 volatile 关键字。

size()和containsValue() 段数组是final的,并且其成员变量实际上也是final的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
final V putVal(K key, V value, boolean onlyIfAbsent) {
    if (key == null || value == null) throw new NullPointerException();
    int hash = spread(key.hashCode());// 计算hash值,比hashmap多了一个&操作
    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) {// 指定位置的节点的第一个节点
            // 为null,CAS操作添加新节点,操作失败进入下一次循环,典型的CAS思想
            if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null)))
                break;                   // no lock when adding to empty bin
        }
        // hash=-1,可以推测是扩容引起的
        else if ((fh = f.hash) == MOVED)
            tab = helpTransfer(tab, f);
        else {
            V oldVal = null;
            synchronized (f) {// f是指定位置的头节点,此时不为null
                if (tabAt(tab, i) == f) {
                    if (fh >= 0) {// 头节点的hash值,大于0进行链表处理
                        binCount = 1;// 记录此链表的长度
                        for (Node<K,V> e = f;; ++binCount) {
                            K ek;
                            // 相同的key存储,是否进行覆盖
                            if (e.hash == hash &&
                                ((ek = e.key) == key ||
                                    (ek != null && key.equals(ek)))) {
                                oldVal = e.val;
                                if (!onlyIfAbsent)
                                    e.val = value;
                                break;
                            }
                            // 不同的key存储,链表最后追加
                            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;
                        }
                    }
                }
            }
            if (binCount != 0) {
                // 节点数是否>=8,比hashmap少一个就开始重构
                if (binCount >= TREEIFY_THRESHOLD)
                    // 此方法会优先选择扩容(数组大小<64时),而不进行重构
                    treeifyBin(tab, i);
                if (oldVal != null)
                    return oldVal;
                break;
            }
        }
    }
    addCount(1L, binCount);// 扩容校验
    return null;
}

transfer() helpTransfer()

Java7 -> Java8

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
final Segment<K,V>[] segments;
 
static final class Segment<K,V> extends ReentrantLock implements Serializable {
  transient volatile HashEntry<K,V>[] table;
  transient int count;
}
 
static final class HashEntry<K,V> {
  final int hash;
  final K key;
  volatile V value;
  volatile HashEntry<K,V> next;
}
// 扩容过程在此方法中
private void rehash(HashEntry<K,V> node) {
}

可以看出,底层的存储是数组,姑且称之为父数组,元素类型是Segment, 每个元素含有一个数组(可称之为子数组)和计数数组元素数目的变量,数组中存储的是HashEntry类型的节点,是真正存储数组的节点单位,其next属性表明子数组中存储的是节点链表.

在扩容的时候,扩的也是子数组,而不是父数组.

Java8中不再采用分段锁机制,直接使用数组保存节点链表,将链表的首节点作为锁对象,构建同步代码块(put方法中). Java7中,子数组某位置中的链表元素过多也不会重构,此时查询性能较差,Java8中,和HashMap一样采取了重构为红黑树的机制,将时间复杂度从O(N)降低到O(logN).

HashTable

  • 使用synchronized锁住整张Hash表
  • 线程安全,但并发环境下效率低

 

 


作者:LuVx21

GitHub地址:https://github.com/LuVx21