HashMap线程安全分析

发表于 | 分类于 | 阅读次数

Java中通过锁实现同步的方式主要有2种：通过synchronized关键字和显示的lock。

Hashmap与线程安全

Java中map可以快速定位某个元素，查询速度比数组、list都要快，所以广泛应用于Java开发中。其底层数据结构也较为简单，本质是结合了数组和链表，即Entry数组。
但hashmap并不是线程安全的，在多线程高并发环境下会存在很多问题，其中出现在问题往往出现在put操作上。

Put方法执行过程

我们先看看put操作的源码，如下图所示：
img
put操作首先通过key的hashcode定位到数组某一个位置，然后结合equals方法查找是否存在相同的key，若存在直接修改value，否则addEntry增加新节点
img
addentry方法中会检查map size是否超过规定的值，若超过需要扩充容量，即resize操作
img
resize过程中会通过transfer方法会将数据转移到新的位置
img
现在我们分析一下，这个过程中可能存在的问题。首先，在不同的线程中，同时操作了同一个对象，按照Java内存模型来理解，各个线程中有自己的工作内存，并且该内存中有主存中的副本，这些副本之间不能直接进行通信，必须依靠主内存中的值来通信，所以会出现很多线程安全问题。

常见的线程安全问题

丢失put的修改

假设2个线程都同时在一个位置put相同的key，该key并不存在，所以2个线程中都会执行addEntry方法的new Entry (hash, key, value, e)，结果新的节点都指向了e，所以一个线程put后读取的时候可能读取的值并不相同。

put过程导致读取null值

若在put操作后导致了resize操作，在transfer中有一行代码src[j]=null，即把旧数组设置为null垃圾回收，在transfer执行结束前，另一线程读取的还是旧的数组，可能存在读取某个存在key为null

transfer导致死循环

下面举一个简单的例子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static void main(String[] args) {
      HashMap<Integer,String> map = new HashMap<Integer,String>(2，0.75f);
        map.put(5， "C");  
        new Thread("Thread1") {  
            public void run() {  
                map.put(7, "B");  
                System.out.println(map);  
            };  
        }.start();  
        new Thread("Thread2") {  
            public void run() {  
                map.put(3, "A);  
                System.out.println(map);  
            };  
        }.start();        
    }

map在存放第二个key的时候将会扩容，这将导致resize操作， 假设在两个线程resize前，数组内容如下：
img
第一个线程由于某个原因被挂起，第二个线程先transfer完成，现在第一个线程将要执行transfer操作
img
在第一个循环执行后，线程1的结构将会变成这样
img
然后继续执行一个循环后，如下所示
img
最后一个循环执行后，e将为null，此时的结构如下：
img
而此时map中entry数组的第三个位置出现了环，如果get方法调用是刚好定位到entry[3]如key为11时，将陷入无限循环。

Tips

使用Hashmap需要使用一种线程安全的方式使用，当前常见的方案有：
1.使用hashtable，但现在很少使用
2.使用Collections.synchronizedMap包装hashmap，在同步块synchronized或lock中使用map
3.使用ConcurrentHashMap，它实质是一种分段的hashtable，内部是一个segment数组，没一个segment类似一个hashtable，这样对每一个segment进行分段加锁，而且只有put操作是加锁的，get操作大部分情况下不加锁，除非读取到null，这样保证了map并发时的高效率。

谢谢大佬的打赏!