0%

ConcurrentHashMap源码

在并发的情况下,通常使用ConcurrentHashMap来保证程序的效率

简介

ConcurrentHashMap原理是当一个线程占用锁访问其中一个段数据的时候,
其他段的数据也能被其他线程访问,
能够实现真正的并发访问。

据说曾经的
ConcurrentHashMap使用分段锁技术,segment锁,保护了多个hash桶
将数据分成一段一段的存储,
然后给每一段数据配一把锁。(老代码懒得去找了

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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134

在JDK8里面变成了只对访问的hash桶加锁,一个锁只保护一个hash桶,细粒度更小,写操作的并发的到提升。



## PUT方法

concurrentHashMap是通过casTabAt来保证值得可见性。

在不加锁的情况下,线程A使用casTabAt方法对map进行操作,线程B能够直接使用tabAt访问到map里面的值。

通过for循环+CAS操作,实现并发安全的方式就是无锁算法(lock free)的经典实现。

如果存在hash冲突,会对使用native方法tabAt读取出来的f加锁,对f进行转换成链表或者树的处理

~~~java
/**
* 这个变量初次初始化时候会被创建
*/
transient volatile Node<K,V>[] table;
/** 用于控制整个变量的操作,初始为0 */
private transient volatile int sizeCtl;
public V put(K key, V value) {
return putVal(key, value, false);
}

/** 实现PUT方法 */
final V putVal(K key, V value, boolean onlyIfAbsent) {
// Key不允许为空
if (key == null || value == null) throw new NullPointerException();
// 计算key的hash值防碰撞
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) {
// 如果Map的最后i个元素为空,创建一个Node放到tab的第i个位置
// 使用casTabAt进行塞值,如果塞失败会重新进行循环来处理
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 {
// 有一模一样的Hash值存在
V oldVal = null;
// 对存在冲突的那个对象加锁
synchronized (f) {
// 如果那个对象还没有转换成树
if (tabAt(tab, i) == f) {
if (fh >= 0) {
binCount = 1;
for (Node<K,V> e = f;; ++binCount) {
K ek;
// 比较他们的当前锁住的对象f和传进来的hash值相同,Key相同或者对象地址相同
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;
}
}
}
}

if (binCount != 0) {
// 如果超过一个树的最大容量直接转换成树
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
addCount(1L, binCount);
return null;
}
/** 初始化 */
private final Node<K,V>[] initTable() {
Node<K,V>[] tab; int sc;
while ((tab = table) == null || tab.length == 0) {
// sizeCtl小于0,说明已经有线程在对它进行处理,当前线程进行创建的时候则需要先等等
if ((sc = sizeCtl) < 0)
Thread.yield(); // lost initialization race; just spin
// 使用底层代码保证只有一个值来改变sc的值 SIZECTL是当前类的内存地址,将状态修改成-1
else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
try {
if ((tab = table) == null || tab.length == 0) {
// DEFAULT_CAPACITY初始化为16
int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
// 创建一个长度为n的数组
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
table = tab = nt;
sc = n - (n >>> 2);
}
} finally {
sizeCtl = sc;
}
break;
}
}
return tab;
}

GET方法


public V get(Object key) {
    Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
    // 计算Hash
    int h = spread(key.hashCode());
    // 如果表不为空,且hash值存在
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (e = tabAt(tab, (n - 1) & h)) != null) {
        // key相同直接返回
        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;
}