看了CopyOnWriteArrayList后自己实现了一个CopyOnWriteHashMap


在这里插入图片描述

引言

面试官: 小伙子你有点眼熟啊,是不是去年来这面试过啊。

二胖: 啊,没有啊我这是第一次来这。

面试官: 行,那我们开始今天的面试吧,刚开始我们先来点简单的吧,java里面的容器你知道哪些啊,跟我说一说吧。

二胖: 好的,java里面常见容器有ArrayList(线程非安全)、HashMap(线程非安全)、HashSet(线程非安全),ConcurrentHashMap(线程安全)。

面试官: ArrayList 既然线程非安全那有没有线程安全的ArrayList列?

二胖: 这个。。。 好像问到知识盲点了。

面试官: 那我们今天的面试就先到这了,我待会还有一个会,后续如有通知人事会联系你的。

以上故事纯属虚构如有雷同请以本文为主。

什么是COW

在java里面说到集合容器我们一般首先会想到的是HashMapArrayListHasHSet这几个容器也是平时开发中用的最多的。
这几个都是非线程安全的,如果我们有特定业务需要使用线程的安全容器列,

  • HashMap可以用ConcurrentHashMap代替。

  • ArrayList 可以使用Collections.synchronizedList()方法(list 每个方法都用synchronized修饰) 或者使用Vector(现在基本也不用了,每个方法都用synchronized修饰)
    或者使用CopyOnWriteArrayList 替代。

  • HasHSet 可以使用 Collections.synchronizedSet 或者使用CopyOnWriteArraySet来代替。(CopyOnWriteArraySet为什么不叫CopyOnWriteHashSet因为CopyOnWriteArraySet底层是采用CopyOnWriteArrayList来实现的)
    我们可以看到CopyOnWriteArrayList在线程安全的容器里面多次出现。
    首先我们来看看什么是CopyOnWriteCopy-On-Write简称COW,是一种用于程序设计中的优化策略。

    CopyOnWrite容器即写时复制的容器。通俗的理解是当我们往一个容器添加元素的时候,不直接往当前容器添加,而是先将当前容器进行Copy,复制出一个新的容器,然后新的容器里添加元素,添加完元素之后,再将原容器的引用指向新的容器。这样做的好处是我们可以对CopyOnWrite容器进行并发的读,而不需要加锁,因为当前容器不会添加任何元素。所以CopyOnWrite容器也是一种读写分离的思想,读和写不同的容器。

    为什么要引入COW

    防止ConcurrentModificationException异常

    在java里面我们如果采用不正确的循环姿势去遍历List时候,如果一边遍历一边修改抛出java.util.ConcurrentModificationException错误的。
    如果对ArrayList循环遍历不是很熟悉的可以建议看下这篇文章《ArrayList的删除姿势你都掌握了吗》

          List<String> list = new ArrayList<>();
          list.add("张三");
          list.add("java金融");
          list.add("javajr.cn");
          Iterator<String> iterator = list.iterator();
          while(iterator.hasNext()){
              String content = iterator.next();
              if("张三".equals(content)) {
                  list.remove(content);
              }
    
          }

    上面这个栗子是会发生java.util.ConcurrentModificationException异常的,如果把ArrayList改为CopyOnWriteArrayList 是不会发生生异常的。

    线程安全的容器

    我们再看下面一个栗子一个线程往List里面添加数据,一个线程循环list读数据。

      List<String> list = new ArrayList<>();
          list.add("张三");
          list.add("java金融");
          list.add("javajr.cn");
          Thread t = new Thread(new Runnable() {
              int count = 0;
              @Override
              public void run() {
                  while (true) {
                      list.add(count++ + "");
                  }
              }
          });
          t.start();
          Thread.sleep(10000);
          for (String s : list) {
              System.out.println(s);
          }

    我们运行上述代码也会发生ConcurrentModificationException异常,如果把ArrayList换成了CopyOnWriteArrayList就一切正常。

    CopyOnWriteArrayList的实现

    通过上面两个栗子我们可以发现CopyOnWriteArrayList是线程安全的,下面我们就来一起看看CopyOnWriteArrayList是如何实现线程安全的。

    public class CopyOnWriteArrayList<E>
      implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
      private static final long serialVersionUID = 8673264195747942595L;
    
      /** The lock protecting all mutators */
      final transient ReentrantLock lock = new ReentrantLock();
    
      /** The array, accessed only via getArray/setArray. */
      private transient volatile Object[] array;

    从源码中我们可以知道CopyOnWriteArrayList这和ArrayList底层实现都是通过一个Object的数组来实现的,只不过 CopyOnWriteArrayList的数组是通过volatile来修饰的,为什么需要volatile修饰建议可以看看《Java的synchronized 能防止指令重排序吗?》
    还有新增了ReentrantLock

    add方法:

      public boolean add(E e) {
          // 先获取锁
          final ReentrantLock lock = this.lock;
          lock.lock();
          try {
              Object[] elements = getArray();
              int len = elements.length;
              // 复制一个新的数组
              Object[] newElements = Arrays.copyOf(elements, len + 1);
              newElements[len] = e;
              // 把新数组的值 赋给原数组
              setArray(newElements);
              return true;
          } finally {
              // 释放锁
              lock.unlock();
          }
      }

    上述源码我们可以发现比较简单,有几个点需要稍微注意下

  • 增加数据的时候是通过ReentrantLock加锁操作来(在jdk11的时候采用了synchronized来替换ReentrantLock)保证多线程写的时候只有一个线程进行数组的复制,否则的话内存中会有多份被复制的数据,导致数据错乱。

  • 数组是通过volatile 修饰的,根据 volatilehappens-before 规则,写线程对数组引用的修改是可以立即对读线程是可见的。

  • 通过写时复制来保证读写实在两个不同的数据容器中进行操作。

    自己实现一个COW容器

    再Java并发包里提供了两个使用CopyOnWrite机制实现的并发容器,它们是CopyOnWriteArrayListCopyOnWriteArraySet,但是并没有CopyOnWriteHashMap我们可以按照他的思路自己来实现一个CopyOnWriteHashMap

    public class CopyOnWriteHashMap<K, V> implements Map<K, V>, Cloneable {
    
      final transient ReentrantLock lock = new ReentrantLock();
    
      private volatile Map<K, V> map;
    
    
public CopyOnWriteHashMap() {
    map = new HashMap<>();
}

@Override
public V put(K key, V value) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        Map<K, V> newMap = new HashMap<K, V>(map);
        V val = newMap.put(key, value);
        map = newMap;
        return val;
    } finally {
        lock.unlock();
    }
}

@Override
public V get(Object key) {
    return map.get(key);
}
@Override
public V remove(Object key) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        Map<K, V> newMap = new HashMap<K, V>(map);

        if (!newMap.containsKey(key)) {
            return null;
        }
        V v = newMap.get(key);
        newMap.remove(key);
        map = newMap;
        return v;
    }finally {
        lock.unlock();
    }
}
上述我们实现了一个简单的`CopyOnWriteHashMap`,只实现了`add、remove、get`方法其他剩余的方法可以自行去实现,涉及到只要数据变化的就要加锁,读无需加锁。
# 应用场景
`CopyOnWrite`并发容器适用于读多写少的并发场景,比如黑白名单、国家城市等基础数据缓存、系统配置等。这些基本都是只要想项目启动的时候初始化一次,变更频率非常的低。如果这种读多写少的场景采用 `Vector,Collections`包装的这些方式是不合理的,因为尽管多个读线程从同一个数据容器中读取数据,但是读线程对数据容器的数据并不会发生发生修改,所以并不需要读也加锁。
# CopyOnWrite缺点
CopyOnWriteArrayList虽然是一个线程安全版的ArrayList,但其每次修改数据时都会复制一份数据出来,所以CopyOnWriteArrayList只适用读多写少或无锁读场景。我们如果在实际业务中使用CopyOnWriteArrayList,一定是因为这个场景适合而非是为了炫技。
### 内存占用问题
因为CopyOnWrite的写时复制机制每次进行写操作的时候都会有两个数组对象的内存,如果这个数组对象占用的内存较大的话,如果频繁的进行写入就会造成频繁的Yong GC和Full GC。
### 数据一致性问题
CopyOnWrite容器只能保证数据的最终一致性,不能保证数据的实时一致性。读操作的线程可能不会立即读取到新修改的数据,因为修改操作发生在副本上。但最终修改操作会完成并更新容器所以这是最终一致性。
# CopyOnWriteArrayList和Collections.synchronizedList()
简单的测试了下CopyOnWriteArrayList  和  Collections.synchronizedList()的读和写发现:
- 在高并发的写时CopyOnWriteArray比同步Collections.synchronizedList慢百倍
- 在高并发的读性能时CopyOnWriteArray比同步Collections.synchronizedList快几十倍。
- 高并发写时,CopyOnWriteArrayList为何这么慢呢?因为其每次add时,都用Arrays.copyOf创建新数组,频繁add时内存申请释放性能消耗大。
- 高并发读的时候CopyOnWriteArray无锁,Collections.synchronizedList有锁所以读的效率比较低下。
# 总结
选择CopyOnWriteArrayList的时候一定是读远大于写。如果读写都差不多的话建议选择Collections.synchronizedList。
# 结束
- 由于自己才疏学浅,难免会有纰漏,假如你发现了错误的地方,还望留言给我指出来,我会对其加以修正。
- 如果你觉得文章还不错,你的转发、分享、赞赏、点赞、留言就是对我最大的鼓励。
- 感谢您的阅读,十分欢迎并感谢您的关注。

巨人肩膀摘苹果
http://ifeve.com/java-copy-on-write/

文章作者: java金融
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 java金融 !
 上一篇
几百本计算机书籍免费下载 几百本计算机书籍免费下载
古语有云:书中自有黄金屋,书中自有颜如玉。身为程序员的我们,阅读相关技术书籍是必不可少的,然而普通的一本技术类书籍,少说也得有两三厘米厚,天天那么带在身上也不方便。为了减轻广大小伙伴们的负担,节约寻找书籍的时间,我不辞辛劳,通宵达旦,花费洪
2021-01-05
下一篇 
天天写同步,5种SpringMvc异步请求了解下! 天天写同步,5种SpringMvc异步请求了解下!
微信搜一搜【java金融】回复【666】免费获取bat面试通关手册 引言说到异步大家肯定首先会先想到同步。我们先来看看什么是同步?所谓同步,就是发出一个功能调用时,在没有得到结果之前,该调用就不返回或继续执行后续操作。简单来说,同步就是
2021-01-03