并发编程 ConcurrentHashMap

本文将介绍并发编程中的 ConcurrentHashMap。

一、ConcurrentHashMap - 1.7

1. 结构图

2. 并发控制手段

ConcurrentHashMap - 1.7 中，Java 使用分段锁机制。

简而言之，将整个 Hash 表划分为多个分段，每个分段类似于一个 Hashtable；将所有分段保存在分段数组中；在执行操作时，首先定位到分段，然后对分段加锁，以进行安全的操作。

3. 源码 - 读写

(1) get

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public V get(Object key) {
    Segment<K,V> s;
    HashEntry<K,V>[] tab;
    int h = hash(key);
    long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
    // 计算得到Segment
    if ((s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)) != null &&
        (tab = s.table) != null) {
        for (HashEntry<K,V> e = (HashEntry<K,V>) UNSAFE.getObjectVolatile
                 (tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE);
             e != null; e = e.next) {
            // 如果是链表，遍历查找键值对
            K k;
            if ((k = e.key) == key || (e.hash == h && key.equals(k)))
                return e.value;
        }
    }
    return null;
}

(2) put

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public V put(K key, V value) {
    Segment<K,V> s;
    
    // 计算得到具体的Segment
    
    return s.put(key, hash, value, false);
}

final V put(K key, int hash, V value, boolean onlyIfAbsent) {
	// 尝试加锁，若加锁失败，则调用scanAndLockForPut()方法自旋获取锁
    HashEntry<K,V> node = tryLock() ? null : scanAndLockForPut(key, hash, value);
    // 执行put操作
    ...
}

二、ConcurrentHashMap - 1.8

1. 结构图

2. 并发控制手段

结构与 HashMap 类似，为 “数组 + 链表 / 红黑树”。

通过 CAS 和 synchronized 保证访问时的线程安全。

3. 源码 - 读写

(1) get

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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());
    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)
            // 若hash为负值，说明为树节点或正在扩容，查找
            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;
}

(2) put

1
2
3
4
5
6
7
8
9
10
11
12
13
// 找到哈希表中的具体哈希桶
Node<K,V> f = tabAt(tab, i = (n - 1) & hash);

if (f == null) {
    // 若该哈希桶为空，则通过CAS放入元素
	casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null));
} else if ((fh = f.hash) == MOVED) {
    // 若正在数据迁移，则帮助迁移
 	tab = helpTransfer(tab, f);
} else {
    // 若该哈希桶不为空，则对头节点加锁将元素插入链表/红黑
 	···
}

参考

  • Java 并发编程实战