HashMap & ConcurrentHashMap

基于Java1.8分析HashMap与ConcurrentHashMap。

HashMap

初始化
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
public class HashMap<K,V> ... {

    // Hash桶
    transient Node<K,V>[] table;
    // 当size达到threshold就需要扩容（threshold = capacity * load factor）
    int threshold;
    // 负载因子（用于设置扩容时机）
    final float loadFactor;
    // 默认初始化容量
     static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    /* Map初始化 */
    public HashMap() {
        // 默认负载因子(DEFAULT_LOAD_FACTOR=75%)
        this.loadFactor = DEFAULT_LOAD_FACTOR;
    }
    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }
    public HashMap(int initialCapacity, float loadFactor) {
        ...
        // 初始化负载因子和初始容量
        this.loadFactor = loadFactor;
        // tableSizeFor用于设置一个2的幂次方整数
        this.threshold = tableSizeFor(initialCapacity);
    }
}

tableSizeFor用于设置一个最接近容量的2的幂次方整数。

计算Hash
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 设置KV
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}
// 计算哈希值（扰动函数）
static final int hash(Object key) {
    int h;
    // 利用int32位的特点（混合原始哈希码的高位和低位，以此来加大低位的随机性）
    // java1.7扰动4次, java1.8仅扰动一次
    // final int hash(Object k) {
    //    int h = 0;
    //    h ^= k.hashCode();
    //    h ^= (h >>> 20) ^ (h >>> 12);
    //    return h ^ (h >>> 7) ^ (h >>> 4);
    //}
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

(h = key.hashCode()) ^ (h >>> 16)的原因可以参考：
JDK 源码中 HashMap 的 hash 方法原理是什么？

设置KV

设置KV的过程大体如下：

  • 计算Hash值；
  • 判断冲突存储结构：红黑树or链表；
  • 判断是否需要把链表转换成红黑树；
  • 判断是否需要扩容。
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
// 设置KV
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
              boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        // 如果table为空初始化（table用于存储KV数据）
        if ((tab = table) == null || (n = tab.length) == 0)
            // 触发resize分配内存空间
            n = (tab = resize()).length;
        // 判断table中是否包含Hash节点i, i = (n-1) & hash
        if ((p = tab[i = (n - 1) & hash]) == null)
            // 不包含则新建节点
            tab[i] = newNode(hash, key, value, null);
        else {
            // 包含Hash节点i, 则需要考虑冲突链
            Node<K,V> e; K k;
            // 冲突1：Hash相同的相同Key, 则覆盖数据
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            // 冲突2：Hash相同的不同Key 挂载红黑树的情况
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            // 冲突3：Hash相同的不同Key 挂载链表的情况
            else {
                for (int binCount = 0; ; ++binCount) {
                    // 如果遍历到链表的尾部仍未发现相同key，则新增节点
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        // 如果链表长度大于等于TREEIFY_THRESHOLD，则把链表转换成为红黑树
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    // 如果发现相同节点，则退出当前链表遍历，e保存着相同节点
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            // 如果存在相同的Key, 则更新对应的Val值
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        // 判断是否需要扩容
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }
扩容

扩容的过程大体如下：

  • 判断是否为初始化情况；
  • 确认扩容容量；
  • 遍历原有数据进行迁移；
  • 计算迁移位置（桶的位置不变or改变）；
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
// 扩容
final Node<K,V>[] resize() {
    // 标记老table
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    // 非初始化的情况
    if (oldCap > 0) {
        // 大于最大容量，直接返回
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 满足容量限制 并且 原有用量大于默认容量（16），翻倍扩容
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    // 初始化
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // 初始化 或 容量仍然小于16， 重新计算新的容量阈值
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    // 初始化新table
    @SuppressWarnings({"rawtypes","unchecked"})
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    if (oldTab != null) {
        // 遍历老table数据进行迁移
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                // next为空，仅一个节点
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                // 红黑树
                else if (e instanceof TreeNode)
                    // 尝试拆分红黑树：小于阈值转为链表，否则仍然为红黑树
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                // 链表
                else { // preserve order
                    // 记录不需要移动的链表头和尾
                    Node<K,V> loHead = null, loTail = null;
                    // 记录需要移动的链表头和尾
                    Node<K,V> hiHead = null, hiTail = null;
                    /* 链表遍历 */
                    Node<K,V> next;
                    do {
                        next = e.next;
                        // 判断节点位置rehash后是否发生改变, 0为不变
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    /* 数据迁移 */
                    // 不需要移动位置的直接挂载原有链表
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    // 不要移动位置的在新的位置[j + oldCap]挂载原有链表
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

ConcurrentHashMap

Java1.8使用Synchronized和CAS替换了Java1.7的Segment。

Segment继承了ReentranLock(CAS + AQS)，属于乐观锁。

初始化
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
public class ConcurrentHashMap<K,V> ... {

    // 默认情况下第一次插入触发初始化（懒加载）
    // 数据表的容量默认是2的幂次
    transient volatile Node<K,V>[] table;

    // 初始化（配置）
    public ConcurrentHashMap(int initialCapacity,    // 初始容量
                           float loadFactor,      // 负载因子
                           int concurrencyLevel) { // 并行级别
                           
        if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0)
            throw new IllegalArgumentException();
        // concurrencyLevel：支持的并发级别
        // Map初始化大小一定要大于等于并发线程数量，否则必然发生竞争
        if (initialCapacity < concurrencyLevel)   // Use at least as many bins
            initialCapacity = concurrencyLevel;   // as estimated threads
        long size = (long)(1.0 + (long)initialCapacity / loadFactor);
        int cap = (size >= (long)MAXIMUM_CAPACITY) ?
            MAXIMUM_CAPACITY : tableSizeFor((int)size);
        this.sizeCtl = cap;
    }
    
    
    // sizeCtl < 0，代表正在初始化或扩容
    // 0： 默认
    // -1：初始化
    // -n：扩容的线程数量
    private transient volatile int sizeCtl;
    
    // 默认初始化table的容量，必须是2的n次方
    private static final int DEFAULT_CAPACITY = 16;
    
    // 初始化数据表
    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(); // lost initialization race; just spin
            else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
                // 通过CAS尝试设置初始化状态, sc = -1
                try {
                    // double check
                    if ((tab = table) == null || tab.length == 0) {
                        // 获取sc或默认容量
                        int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
                        // 初始化Node数组作为table
                        @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;
    }
}

设置KV

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
135
136
137
138
139
140
141
142
143
144
145
146
// 设置KV
public V put(K key, V value) {
    return putVal(key, value, false);
}

// 扰动函数
static final int spread(int h) {
    return (h ^ (h >>> 16)) & HASH_BITS;
}

// 设置KV
final V putVal(K key, V value, boolean onlyIfAbsent) {
    // key与value均不允许为空
    if (key == null || value == null) throw new NullPointerException();
    // 扰动函数
    int hash = spread(key.hashCode());
    // 记录hash下元素个数
    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) {
            // hash位置上为被占用，则直接CAS设置Node
            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)
            // 如果正在扩容，则CAS尝试在新的table中设置
            tab = helpTransfer(tab, f);
        else {
            V oldVal = null;
            // JAVA1.7 使用Segment锁
            // JAVA1.8 使用synchronized来支持并发控制
            synchronized (f) {
                if (tabAt(tab, i) == f) {
                    // hash值>0，则是链表，否则为树
                    if (fh >= 0) {
                        binCount = 1;
                        // 遍历链表
                        for (Node<K,V> e = f;; ++binCount) {
                            K ek;
                            // 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;
}

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    ...
    // Resize后拆分红黑树
    final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
        TreeNode<K,V> b = this;
        // 由于Resize扩大一倍后每一个桶都会拆分为两个，loHead与hiHead代表两个桶的链表首部指针
        // Relink into lo and hi lists, preserving order
        TreeNode<K,V> loHead = null, loTail = null;
        TreeNode<K,V> hiHead = null, hiTail = null;
        int lc = 0, hc = 0;
        // 遍历红黑树节点
        for (TreeNode<K,V> e = b, next; e != null; e = next) {
            next = (TreeNode<K,V>)e.next;
            e.next = null;
            // 判断是否为新拆分的桶
            if ((e.hash & bit) == 0) {
                if ((e.prev = loTail) == null)
                    loHead = e;
                else
                    loTail.next = e;
                loTail = e;
                ++lc;
            }
            // 判断是否为原有被拆分的桶
            else {
                if ((e.prev = hiTail) == null)
                    hiHead = e;
                else
                    hiTail.next = e;
                hiTail = e;
                ++hc;
            }
        }

        // 判断loHead链表是转换为链表还是红黑树
        if (loHead != null) {
            if (lc <= UNTREEIFY_THRESHOLD)
                tab[index] = loHead.untreeify(map);
            else {
                tab[index] = loHead;
                if (hiHead != null) // (else is already treeified)
                    loHead.treeify(tab);
            }
        }
        // 判断hiHead链表是转换为链表还是红黑树
        if (hiHead != null) {
            if (hc <= UNTREEIFY_THRESHOLD)
                tab[index + bit] = hiHead.untreeify(map);
            else {
                tab[index + bit] = hiHead;
                if (loHead != null)
                    hiHead.treeify(tab);
            }
        }
    }
}
1.7 & 1.8

ConcurrentHashMap在v1.7与v1.8中区别由两点：

① 【读】增加红黑树的支持，链地址法的查询的时间复杂度可以从O(N)降低到O(logN);

② 【写】加锁方式的变化：

  • v1.7中，采用Segment与HashEntry实现；
  • v1.8中，采用CAS、synchronized与Node实现。

与v1.7对比，v1.8中对锁的粒度进行了一次大的调整：

  • 从范围锁变为单位锁，提高了并发能力；
  • 不再使用Segment，也占用了更少的内存空间。

区别

ConcurrentHashMap与HashMap的区别在于支持多线程并发编程。

原理

① 当table为空时，利用CAS实现初始化;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
if (tab == null || (n = tab.length) == 0)
    tab = initTable();
   
private final Node<K,V>[] initTable() {
    Node<K,V>[] tab; int sc;
    // 循环尝试直到table初始化完成
    while ((tab = table) == null || tab.length == 0) {
        ...
        // 通过Unsafe的CAS来设置sizeCtl标志位
        else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
            ... //具体初始化逻辑
        }
    }
    return tab;
}

② 当哈希分桶的位置为空时，利用CAS来尝试设置链表；

1
2
3
4
5
6
7
8
9
10
if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
    // 如果设置成功则跳出循环
    if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null)))
        break;
        
static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
                                    Node<K,V> c, Node<K,V> v) {
    // Unsafe.compareAndSwapObject 对象的CAS来设置
    return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
}

③ 对于非空链表来说，使用synchronized悲观锁实现并发操作；

1
2
3
4
5
synchronized (f) {
   if (tabAt(tab, i) == f) {
       ...
   }      
}

④ ConcurrentHashMap的Resize过程(transfer)是支持并发的。

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
// 利用Unsafe的CAS来执行扩容
if (U.compareAndSwapInt(this, SIZECTL, sc, ...) 
      transfer(tab, ...);

private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
    int n = tab.length, stride;
    // 设置并发线程负责迁移区间大小
    if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
        stride = MIN_TRANSFER_STRIDE; // subdivide range
    // nextTab时需要扩展的桶，如果为空则需要重新初始化
    if (nextTab == null) {            // initiating
       // 初始化2倍大小
       Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];
       nextTab = nt;
       ...
    }
    ...
    // 循环迁移
    for (int i = 0, bound = 0;;) {
        Node<K,V> f; int fh;
        while (advance) {
            ...
            // 倒序迁移，i从右往左移动，直到边界
            if (--i >= bound || finishing)
                advance = false;
            ...
            // 利用Unsafe的CAS设置该线程的迁移区间，transferIndex = transferIndex - stride
            else if (U.compareAndSwapInt
                     (this, TRANSFERINDEX, nextIndex,
                      nextBound = (nextIndex > stride ?
                                   nextIndex - stride : 0))) {
                // 
                bound = nextBound;
                // 当前需要迁移的位置，从最后一个开始
                i = nextIndex - 1;
                advance = false;
            }
        }
        // 具体迁移逻辑，同设置KV逻辑相似（使用CAS与synchronized）
        ...
    }
}