HashMap并发问题探究

字节面试官问了一个问题，为什么实习的项目里用ConcurrentHashMap而不是HashMap，这个map只是单线程在更新，其实用普通的HashMap也可以？我回答的是并发写的时候会有问题，应该不太对。下面使用jdk 1.8来验证一下。

其实我的实习项目里是先更新数据库，然后增量更新缓存。如果主线程和定时任务都在更新缓存的话，是会有写写并发的问题的。但这应该不是主要的原因。（写写并发带来的是脏数据和数据丢失的问题）。

真正的原因应该是主线程的读和定时任务的写并发时带来的问题

  • 数据可见性：put操作不一定会被get看到
  • 错误数据：扩容rehash的过程中get可能返回错误的数据
  • 死循环：主要是在rehash的过程中

写写并发

下面举个例子，2个线程往map里面put，跑100次，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
27
28
29
30
31
32
33
34
35
36
private static int putTask = 2;
private static int getTask = 1;
private static int step = 1000;

public static void hashMapConcurrentWrite() throws InterruptedException {
    Map<Item, Integer> map = new HashMap<>();
    CountDownLatch countDownLatch = new CountDownLatch(putTask);
    for (int taskId = 0; taskId < putTask; taskId++) {
        int finalTaskId = taskId;
        int start = finalTaskId * step;
        int end = start + step;
        new Thread(new Runnable() {
            @Override
            public void run() {
                for (int i = start; i < end; i++) {
                    map.put(new Item(i), i);
                }
                countDownLatch.countDown();
            }
        }, "test-" + taskId).start();
    }
    countDownLatch.await();
    System.out.println(map.size());
}

public static void testHashMapConcurrentWrite() {
    for (int i = 0; i < 100; i++) {
        try {
            System.out.printf("i = %d ", i);
            hashMapConcurrentWrite();
        } catch (Exception e) {
            e.printStackTrace();

        }
    }
}

脏数据、数据丢失

正确的数量应该是2000个，但是实际的数量往往比2000小

StackOverFlowError

1
2
3
Exception in thread "test-0" Exception in thread "test-1" java.lang.StackOverflowError
	at java.util.HashMap$TreeNode.find(HashMap.java:1901)
    ...

ClassCastException

在Node转为TreeNode的时候，出现类转换异常

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
test-0 ClassCastException caught: java.util.HashMap$Node cannot be cast to java.util.HashMap$TreeNode
java.lang.ClassCastException: java.util.HashMap$Node cannot be cast to java.util.HashMap$TreeNode
	at java.util.HashMap$TreeNode.moveRootToFront(HashMap.java:1859)
	at java.util.HashMap$TreeNode.treeify(HashMap.java:1975)
	at java.util.HashMap.treeifyBin(HashMap.java:773)
	at java.util.HashMap.putVal(HashMap.java:645)
	at java.util.HashMap.put(HashMap.java:613)
	at org.example.HashMapTest$1.run(HashMapTest.java:42)
	at java.lang.Thread.run(Thread.java:750)
test-1 ClassCastException caught: java.util.HashMap$Node cannot be cast to java.util.HashMap$TreeNode
java.lang.ClassCastException: java.util.HashMap$Node cannot be cast to java.util.HashMap$TreeNode
	at java.util.HashMap$TreeNode.moveRootToFront(HashMap.java:1859)
	at java.util.HashMap$TreeNode.treeify(HashMap.java:1975)
	at java.util.HashMap.treeifyBin(HashMap.java:773)
	at java.util.HashMap.putVal(HashMap.java:645)
	at java.util.HashMap.put(HashMap.java:613)
	at org.example.HashMapTest$1.run(HashMapTest.java:42)

死循环

HashMap原理

put

之前一直没搞懂put的树化到底是桶上已经插入了7个结点还是8个，答案应该是在已经插入8个结点的时候，要插入第9个结点的时候，会先将这个节点尾插至链表，然后treeifyBin，但是真正的树化需要目前已有的桶的数量等于MIN_TREEIFY_CAPACITY（一般是64）才可以，否则只是二倍扩容。

一个小测试，通过重写hashCode的方法，使得元素hash后只会存在hashCode为0和1的两个桶。下面这个只会在i = 17的时候树化，当i = 16的时候，由于桶的数量还没有到64，只有32，所以会先扩容。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
static class Item {
    private int id;
    Item(int id) {
        this.id = id;
    }

    @Override
    public int hashCode() {
        return id % 2;
    }
}

public static void testTreeify() {
    Map<Item, Integer> map = new HashMap<>();
    for (int i = 0; i < 1000; i++) {
        map.put(new Item(i), i);
    }

    System.out.println(map.size());
}

其实这个例子会经过三次扩容，然后插入第18个元素（i = 17）才树化

  • 第一次扩容：插入第1个元素，容量变为16，阈值为12
  • 第二次扩容：插入第13个元素，容量变为32，阈值为24
  • 第三次扩容：插入第17个元素（i = 16），容量变为64，阈值变为48
  • 再多插入一个元素，就扩容了

下面对put的源码进行剖析

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
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        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;
}

resize扩容

HashMap在new的时候其实不会真的给元素分配内存，而是有点lazy init的感觉，当插入第一个元素的时候，调用resize方法去分配空间。

假设我们没有指定初始容量

第一次扩容的时候

  • oldTab: null
  • oldCap: 0
  • oldThr: 0

之后会进入else分支

  • newCap: DEFAULT_INITIAL_CAPACITY(16)
  • newThr: 12

第二次扩容的时候

  • oldTab: not null
  • oldCap: 16
  • oldThr: 12
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
final Node<K,V>[] resize() {
    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;
        }
        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);
    }
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                    (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    //...
}
#Java
HashMap并发问题探究
http://hhubibi.github.io/2024/08/22/hashmap/
作者
hhubibi
发布于
2024年8月22日
许可协议