侧边栏壁纸
博主头像
孔子说JAVA博主等级

成功只是一只沦落在鸡窝里的鹰,成功永远属于自信且有毅力的人!

  • 累计撰写 292 篇文章
  • 累计创建 132 个标签
  • 累计收到 4 条评论

目 录CONTENT

文章目录

Java并发编程之ConcurrentHashMap原理及实战

孔子说JAVA
2022-06-29 / 0 评论 / 0 点赞 / 77 阅读 / 7,615 字 / 正在检测是否收录...

java.util.Map是使用最广泛的Java集合之一,其实现HashMap是线程不安全的,HashTable则是基于synchronized的线程安全(效率很低),另一个完全同步的Map是Collections.sychronizedMap,它也不是很高效。如果想要线程安全并且在高并发的情况下保持高吞吐量,就需要使用java.util.concurrent.ConcurrentMap,它是从java1.5开始新增的的Map实现。

1、ConcurrentMap接口

ConcurrentMap继承了java.util.Map接口,是一个能够支持并发访问的集合接口,它提供了一种代码结构,用来指引解决数据读写时的线程安全问题。ConcurrentMap重写了Map中的很多default方法,用来实现线程安全和内存一致性的原子操作。很多的默认实现被重写,不允许使用null作为key/value。

image-1656463700095

ConcurrentMap在原有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);
}
  1. putIfAbsent:与原有put方法不同的是,putIfAbsent方法中如果插入的key相同,则不替换原有的value值;
  2. remove:与原有remove方法不同的是,新remove方法中增加了对value的判断,如果要删除的key–value不能与Map中原有的key–value对应上,则不会删除该元素;
  3. replace(K,V,V):增加了对value值的判断,如果key–oldValue能与Map中原有的key–value对应上,才进行替换操作;
  4. replace(K,V):与上面的replace不同的是,此replace不会对Map中原有的key–value进行比较,如果key存在则直接替换;

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

2、ConcurrentHashMap

ConcurrentHashMap是一个开箱即用的ConcurrentMap的实现类,解决了使用hashMap线程不安全,使用HashTable低效的问题,是一个高效的高并发线程安全类。内部采用了分段锁的设计,有效地避免了锁的竞争压力。对于每个分段,ConcurrentHashmap采用final和内存可见修饰符volatile关键字实现。

为了获得更好的性能,它将数据分成多个bucket,放在一个数组里,数组是一张哈希表,就是以前的段,在更新的时候使用CAS(compareAndSwap)。

  • bucket是懒加载的,在第一次插入的时候。每个bucket都会被独立的锁上,锁住桶中的第一个node。读操作是不会被阻塞,并且更新的资源争夺也被限制了。

  • 段的数量是由访问表的线程决定的,所以段的更新,一次只有一个线程。

  • 在java8之前,段的数量是由访问的线程数量决定的,一个线程一个段。这就是为什么它的构造函数和HashMap比起来多了concurrencyLevel的参数,它就是估算的线程数量,另外两个参数和HashMap相同。从java8开始,构造函数只是为了和之前的版本兼容,保留了下来,他们只能影响初始的map的大小。

public ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel) 

2.1 分段锁

锁分段技术,就是将数据分成一段一段的存储,然后给每段数据都配一把锁,当一个线程占用锁访问其中一段数据的时候,其他段的数据也能被其他线程访问。有些方法需要跨段,比如size()和containsValue(),它们可能需要锁定整个表而而不仅仅是某个段,这就需要按顺序锁定所有段,操作完毕后,又按顺序释放所有段的锁。这里“按顺序”是很重要的,否则极有可能出现死锁,在ConcurrentHashMap内部,段数组是final的,并且其成员变量实际上也是final的,但是,仅仅是将数组声明为final的并不保证数组成员也是final的,这需要实现上的保证。这些设计可以确保不会出现死锁,因为获得锁的顺序是固定的。

  • HashTable在高并发环境下使用时会导致多个线程争抢一把锁,出现锁竞争激烈的情况,从而使得效率低下,而ConcurrentHashMap的解决方案则是将其内部使用段(segment)的概念,每个段都可以视为是一个hashTable,相当于有16把不同的锁,当多线程访问容器里不同数据段的数据时,线程间就不会存在锁竞争,从而可以有效的提高并发访问效率,这就是ConcurrentHashMap所使用的锁分段技术。

a237b17902602628b3ccde4cd557

2.2 数据结构

ConcurrentHashMap是由Segment数组结构和HashEntry数组结构组成。Segment是一种可重入锁ReentrantLock,在ConcurrentHashMap里扮演锁的角色,HashEntry则用于存储键值对数据。一个ConcurrentHashMap里包含一个Segment数组,Segment的结构和HashMap类似,是一种数组和链表结构, 一个Segment里包含一个HashEntry数组,每个HashEntry是一个链表结构的元素, 每个Segment守护者一个HashEntry数组里的元素,当对HashEntry数组的数据进行修改时,必须首先获得它对应的Segment锁。

两个线程给不同的区段Segment中添加元素,这种情况可以并发。所以ConcurrentHashMap可以保证线程安全(多个线程操作同一个Segment,则某个线程给此Segment加锁,另一个线程只能阻塞)并且在一定程度上提交线程并发执行效率。两个线程给同一个区段Segment中添加元素,这种情况不可以并发,在JDK1.8进行了改进。

  1. 底层结构依然是依靠数组+链表
  2. 默认初始容量是16,默认加载因子是0.75,默认扩容是增加1倍
  3. 底层采用了分桶锁(分段锁)机制保证并发性,在后续的版本中,在分段锁的基础上引入了读写锁的机制:
    • a.读锁:允许多个线程同时读,不允许线程写
    • b.写锁:允许一个线程写,不允许线程读
  4. 在JDK1.8中,采用了无锁算法CAS(Compare and Swap - 比较和交换)
  5. 在JDK1.8中,引入红黑树机制。当桶中的元素个数超过8个的时候,可能会扭转成一棵树,但实际上桶的容量大于64才转换;如果桶中元素个数不足7个,则会扭转回链表 - 扭转成红黑树的最小容量为64。
    • 解决问题:桶数越多,扩容的几率就越低,桶数越多,每一个桶中的元素个数越多,使用红黑树。

image-1656480584090

JDK1.8之后的ConcurrentHashMap

JDK8中ConcurrentHashMap参考了JDK8 HashMap的实现,采用了数组+链表+红黑树的实现方式来设计,内部大量采用CAS操作。并发控制使⽤synchronized 和 CAS 来操作。(JDK1.6 以后 对 synchronized 锁做了很多优化) 整个看起来就像是优化过且线程安全的 HashMap,虽然在 JDK1.8 中还能看到 Segment 的数据结构,但是已经简化了属性,只是为了兼容旧版本;

  • JDK1.8的Nod节点中value和next都用volatile修饰,保证并发的可见性。

  • synchronized 只锁定当前链表或红⿊⼆叉树的⾸节点,这样只要 hash 不冲突,就不会产⽣并发,效率⼜提升 N 倍。

image-1656498232232

2.3 和HashTable的区别

Hashtable 和 JDK1.8 之前的 HashMap 的底层数据结构类似都是采⽤ 数组+链表 的形式,数组是 HashMap 的主体,链表则是主要为了解决哈希冲突⽽存在的。

  • Hashtable(同⼀把锁) :使⽤ synchronized 来保证线程安全,效率⾮常低下。当⼀个线程访问同步⽅法时,其他线程也访问同步⽅法,可能会进⼊阻塞或轮询状态,如使⽤ put 添加元素,另⼀个线程不能使⽤ put 添加元素,也不能使⽤get,竞争会越来越激烈效率越低;
  • ConcurrentHashMap不论1.7还是1.8,他的执行效率都比HashTable要高的多,主要原因还是因为Hash Table使用了一种全表加锁的方式。

ConcurrentHashMap 是一个并发散列映射表,它允许完全并发的读取,并且支持给定数量的并发更新。

  • ConcurrentHashMap 是设计为非阻塞的。在更新时会局部锁住某部分数据,但不会把整个表都锁住。同步读取操作则是完全非阻塞的。好处是在保证合理的同步前提下,效率很高。坏处是严格来说读取操作不能保证反映最近的更新。例如线程A调用putAll写入大量数据,期间线程B调用get,则只能get到目前为止已经顺利插入的部分数据。

HashTable和同步包装器包装的 HashMap,使用一个全局的锁来同步不同线程间的并发访问,同一时间点,只能有一个线程持有锁,也就是说在同一时间点,只能有一个线程能访问容器,这虽然保证多线程间的安全并发访问,但同时也导致对容器的访问变成串行化的了。

  • Hashtable的任何操作都会把整个表锁住,是阻塞的。好处是总能获取最实时的更新,比如说线程A调用putAll写入大量数据,期间线程B调用get,线程B就会被阻塞,直到线程A完成putAll,因此线程B肯定能获取到线程A写入的完整数据。坏处是所有调用都要排队,效率较低。

我们需要根据具体的应用场景选择合适的HashMap。

2.4 主要方法

void clear()
从该映射中移除所有映射关系

boolean containsKey(Object key)
测试指定对象是否为此表中的键。

boolean containsValue(Object value)
如果此映射将一个或多个键映射到指定值,则返回 true。

Enumeration elements()
返回此表中值的枚举。

Set<Map.Entry<K,V>> entrySet()
返回此映射所包含的映射关系的 Set 视图。

V get(Object key)
返回指定键所映射到的值,如果此映射不包含该键的映射关系,则返回 null。

boolean isEmpty()
如果此映射不包含键-值映射关系,则返回 true。

Enumeration keys()
返回此表中键的枚举。

Set keySet()
返回此映射中包含的键的 Set 视图。

V put(K key, V value)
将指定键映射到此表中的指定值。

void putAll(Map<? extends K,? extends V> m)
将指定映射中所有映射关系复制到此映射中。

V putIfAbsent(K key, V value)
如果指定键已经不再与某个值相关联,则将它与给定值关联。

V remove(Object key)
从此映射中移除键(及其相应的值)。

boolean remove(Object key, Object value)
只有目前将键的条目映射到给定值时,才移除该键的条目。

V replace(K key, V value)
只有目前将键的条目映射到某一值时,才替换该键的条目。

boolean replace(K key, V oldValue, V newValue)
只有目前将键的条目映射到给定值时,才替换该键的条目。

int size()
返回此映射中的键-值映射关系数。

Collection values()
返回此映射中包含的值的 Collection 视图。

3、使用实例

示例1:

import java.util.Iterator;
import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;
 
public class ConcurrentHashMapMain {
     
    public static void main(String[] args) {
        Map<String, String> map = new ConcurrentHashMap<String, String>();
        map.put("1", "1");
        map.put("2", "2");
        map.put("3", "3");
        map.put("4", "4");
        // map.keySet().iterator();
        Iterator<String> it = map.keySet().iterator();
 
        while (it.hasNext()) {
            String key = it.next();
            System.out.println(key + ","+ map.get(key));
            if (key.equals("3")) {
                map.put(key + "key", "3");
            }
 
        }
    }
  
}

示例2:

import java.util.ConcurrentModificationException;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;
public class TestThread {
   public static void main(final String[] arguments) {
      Map<String,String> map = new ConcurrentHashMap<String, String>();
      map.put("1", "One");
      map.put("2", "Two");
      map.put("3", "Three");
      map.put("5", "Five");
      map.put("6", "Six");
      System.out.println("Initial ConcurrentHashMap: " + map);
      Iterator<String> iterator = map.keySet().iterator();
      try { 
         while(iterator.hasNext()) {
            String key = iterator.next();
            if(key.equals("3")) {
               map.put("4", "Four");
            }
         }
      } catch(ConcurrentModificationException cme) {
         cme.printStackTrace();
      }
      System.out.println("ConcurrentHashMap after modification: " + map);
      map = new HashMap<String, String>();
      map.put("1", "One");
      map.put("2", "Two");
      map.put("3", "Three");
      map.put("5", "Five");
      map.put("6", "Six");
      System.out.println("Initial HashMap: " + map);
      iterator = map.keySet().iterator();
      try {
         while(iterator.hasNext()) {
            String key = iterator.next();
            if(key.equals("3")) {
               map.put("4", "Four");
            }
         }
         System.out.println("HashMap after modification: " + map);
      } catch(ConcurrentModificationException cme) {
         cme.printStackTrace();
      }
   }  
}

程序执行结果

Initial ConcurrentHashMap: {1 = One, 2 = Two, 3 = Three, 5 = Five, 6 = Six}
ConcurrentHashMap after modification: {1 = One, 2 = Two, 3 = Three, 4 = Four, 5 = Five, 6 = Six}
Initial HashMap: {1 = One, 2 = Two, 3 = Three, 5 = Five, 6 = Six}
java.util.ConcurrentModificationException
	at java.util.HashMap$HashIterator.nextNode(Unknown Source)
	at java.util.HashMap$KeyIterator.next(Unknown Source)
	at TestThread.main(TestThread.java:48)
0

评论区