ConcurrentMap

╰半夏微凉° 2024-04-28 13:04 107阅读 0赞

## ConcurrentMap详解 ##

##### ConcurrentMap #####

ConcurrentMap是一个线程安全的Map,可以防止多线程并发安全问题.
    
    HashTable也是线程安全的,但是ConcurrentMap性能要比HashTable好的多,所以推荐使用ConcurrentMap.
    
    ConcurrentMap，它是一个接口，是一个能够支持并发访问的java.util.map集合；

ConcurrentMap性能非常好的原因

1. 锁更加精细
    
    HashTable加锁是锁在整个HashTable上,一个线程操作时其他线程无法操作,性能比较低.
    
    ConcurrentMap加锁是 将锁加载数据分段(桶)上 只锁正在操作的部分数据 效率高.
    
    2. 引入了读写锁机制
    
    在多线程并发操作的过程中,多个并发的读其实不需要隔离,但只要有任意一个写操作,就必须隔离.
    
    HashTable没有考虑一点,无论什么类型的操作,直接在整个HashTable上加锁.
    
    ConcurrentMap则区分了读写操作,读的时候加读锁,写的时候加写锁,读锁和读锁可以共存,写锁和任意锁都不能共存,从而实现了在多个读的过程中不会隔离 提高了效率.

### ConcurrentMap的继承结构 ###

java.util.concurrent 接口 ConcurrentMap<K,V>

java.util.concurrent 类 ConcurrentHashMap<K,V>

在原有java.util.map接口基础上又新提供了4种方法，进一步扩展了原有Map的功能：

public interface ConcurrentMap<K, V> extends Map<K, V> {
        
    
        //插入元素
        V putIfAbsent(K key, V value);
    
        //移除元素
        boolean remove(Object key, Object value);
    
        //替换元素
        boolean replace(K key, V oldValue, V newValue);
    
        //替换元素
        V replace(K key, V value);
    }

\*\*putIfAbsent：\*\*与原有put方法不同的是，putIfAbsent方法中如果插入的key相同，则不替换原有的value值；

\*\*remove：\*\*与原有remove方法不同的是，新remove方法中增加了对value的判断，如果要删除的key–value不能与Map中原有的key–value对应上，则不会删除该元素;

\*\*replace(K,V,V)：\*\*增加了对value值的判断，如果key–oldValue能与Map中原有的key–value对应上，才进行替换操作；

\*\*replace(K,V)：\*\*与上面的replace不同的是，此replace不会对Map中原有的key–value进行比较，如果key存在则直接替换；

其实，对于ConcurrentMap来说，我们更关注Map本身的操作，在并发情况下是如何实现数据安全的。在java.util.concurrent包中，ConcurrentMap的实现类主要以ConcurrentHashMap为主。接下来，我们具体来看下。

##### ConcurrentHashMap #####

ConcurrentHashMap是一个线程安全，并且是一个高效的HashMap。
    
    但是，如果从线程安全的角度来说，HashTable已经是一个线程安全的HashMap，那推出ConcurrentHashMap的意义又是什么呢？
    
    说起ConcurrentHashMap，就不得不先提及下HashMap在线程不安全的表现，以及HashTable的效率！

*  HashMap

在多线程情况下HashMap的表现如何？

HashMap中添加元素的源码：（基于JDK1.7.0\_45）

public V put(K key, V value) {
        
        。。。忽略
        addEntry(hash, key, value, i);
        return null;
    }
    void addEntry(int hash, K key, V value, int bucketIndex) {
        
        。。。忽略
        createEntry(hash, key, value, bucketIndex);
    }
    //向链表头部插入元素：在数组的某一个角标下形成链表结构；
    void createEntry(int hash, K key, V value, int bucketIndex) {
        
        Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<>(hash, key, value, e);
        size++;
    }

在多线程情况下，同时A、B两个线程走到createEntry()方法中，并且这两个线程中插入的元素hash值相同，bucketIndex值也相同，那么无论A线程先执行，还是B线程先被执行，最终都会2个元素先后向链表的头部插入，导致互相覆盖，致使其中1个线程中的数据丢失。这样就造成了HashMap的线程不安全，数据的不一致；

更要命的是，HashMap在多线程情况下还会出现死循环的可能，造成CPU占用率升高，导致系统卡死。

举个简单的例子：

public class ConcurrentHashMapTest {
        
        public static void main(String[] agrs) throws InterruptedException {
        
    
            final HashMap<String,String> map = new HashMap<String,String>();
    
            Thread t = new Thread(new Runnable(){
        
                public  void run(){
        
                    
                    for(int x=0;x<10000;x++){
        
                        Thread tt = new Thread(new Runnable(){
        
                            public void run(){
        
                                map.put(UUID.randomUUID().toString(),"");
                            }
                        });
                        tt.start();
                        System.out.println(tt.getName());
                    }
                }
            });
            t.start();
            t.join();
        }
    }

在上面的例子中，我们利用for循环，启动了10000个线程，每个线程都向共享变量中添加一个元素。

测试结果：通过使用JDK自带的jconsole工具，可以看到HashMap内部形成了死循环，并且主要集中在两处代码上。

![img][]

![img][img 1]

那么，是什么原因造成了死循环？

**HashMap–put()494行：**（基于JDK1.7.0\_45）

public V put(K key, V value) {
        
        if (table == EMPTY_TABLE) {
        
            inflateTable(threshold);
        }
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key);
        int i = indexFor(hash, table.length);
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        ------**for循环494行**
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
        
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }

**HashMap–transfer()601行：**（基于JDK1.7.0\_45）

void transfer(Entry[] newTable, boolean rehash) {
        
        int newCapacity = newTable.length;
        for (Entry<K,V> e : table) {
        
            while(null != e) {
        
                Entry<K,V> next = e.next;
                if (rehash) {
        
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            }-----**while循环601行**
        }
    }

通过查看代码，可以看出，死循环的产生：主要因为在遍历数组角标下的链表时，没有了为null的元素，单向链表变成了循环链表，头尾相连了。

以上两点，就是HashMap在多线程情况下的表现。

*  HashTable
    
        说完了HashMap的线程不安全，接下来说下HashTable的效率！！
        
        HashTable与HashMap的结构一致，都是哈希表实现。
        
        与HashMap不同的是，在HashTable中，所有的方法都加上了synchronized锁，用锁来实现线程的安全性。由于synchronized锁加在了HashTable的每一个方法上，所以这个锁就是HashTable本身--this。那么，可想而知HashTable的效率是如何，安全是保证了，但是效率却损失了。
        
        无论执行哪个方法，整个哈希表都会被锁住，只有其中一个线程执行完毕，释放所，下一个线程才会执行。无论你是调用get方法，还是put方法皆是如此；
    
    HashTable部分源码：（基于JDK1.7.0\_45）

public class Hashtable<K,V> extends Dictionary<K,V> 
        implements Map<K,V>, Cloneable, java.io.Serializable {
        
        
        public synchronized int size() {
        ...}
    
        public synchronized boolean isEmpty() {
        ...}
    
        public synchronized V get(Object key) {
        ...}
    
        public synchronized V put(K key, V value) {
        ...}
    }

通过上述代码，可以清晰看出，在HashTable中的主要操作方法上都加了synchronized锁以来保证线程安全。

说完了HashMap和HashTable，下面我们就重点介绍下ConcurrentHashMap，看看ConcurrentHashMap是如何来解决上述的两个问题的！

#### 1.3 ConcurrentHashMap结构 ####

在说到ConcurrentHashMap源码之前，我们首先来了解下ConcurrentHashMap的整体结构，这样有利于我们快速理解源码。

不知道，大家还是否记得HashMap的整体结构呢？如果忘记的话，我们就在此进行回顾下！

![img][img 2]

HashMap底层使用数组和链表，实现哈希表结构。插入的元素通过散列的形式分布到数组的各个角标下；当有重复的散列值时，便将新增的元素插入在链表头部，使其形成链表结构，依次向后排列。

**下面是，ConcurrentHashMap的结构：**

![img][img 3]  
与HashMap不同的是，ConcurrentHashMap中多了一层数组结构，由Segment和HashEntry两个数组组成。其中Segment起到了加锁同步的作用，而HashEntry则起到了存储K.V键值对的作用。

在ConcurrentHashMap中，每一个ConcurrentHashMap都包含了一个Segment数组，在Segment数组中每一个Segment对象则又包含了一个HashEntry数组，而在HashEntry数组中，每一个HashEntry对象保存K-V数据的同时又形成了链表结构，此时与HashMap结构相同。

，由Segment和HashEntry两个数组组成。其中Segment起到了加锁同步的作用，而HashEntry则起到了存储K.V键值对的作用。

在多线程中，每一个Segment对象守护了一个HashEntry数组，当对ConcurrentHashMap中的元素修改时，在获取到对应的Segment数组角标后，都会对此Segment对象加锁，之后再去操作后面的HashEntry元素，这样每一个Segment对象下，都形成了一个小小的HashMap，在保证数据安全性的同时，又提高了同步的效率。只要不是操作同一个Segment对象的话，就不会出现线程等待的问题！

[img]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/28/d8d36885755042548471f1398a84fb3e.png
[img 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/28/43ec80aa8c544a63b9a61ac35e37ccde.png
[img 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/28/d20a4f3af6a9474f933bea560cd61c23.png
[img 3]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/28/3a200efa503d4a76931a498249159378.png