`

CopyOnWriteArrayList 解读

阅读更多

一、 核心思想:

CopyOnWriteArrayList的核心思想是利用高并发往往是读多写少的特性,对读操作不加锁,对写操作,先复制一份新的集合,在新的集合上面修改,然后将新集合赋值给旧的引用,并通过volatile 保证其可见性,当然写操作的锁是必不可少的了。

二、类图预览:


 方法基本分为CopyOnWriteArrayList、indexOf、contains、get、set、add、remove、addIfAbsent和iterator几类:

1、CopyOnWriteArrayList  构造方法:

基本使用Arrays.copyOf 方法,将参数的集合类设置到array属性上。

2、indexOf方法:

 简单的通过循环,对比找到所在的位置,核心代码:

 for (int i = index; i < fence; i++)
                if (o.equals(elements[i]))
                    return i;

 

值得注意有两点,一是支持NULL对象、二是lastIndexOf从后面往前,提高性能

3、 contains方法:

该方法使用indexOf方法,避免代码重复。containsAll方法也是简单的循环判断是否包含单个元素。

4、get方法:

直接返回对应下标元素

5、set方法:

 

  public E set(int index, E element) {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            Object[] elements = getArray();
            E oldValue = get(elements, index);

            if (oldValue != element) {
                int len = elements.length;
                Object[] newElements = Arrays.copyOf(elements, len);
                newElements[index] = element;
                setArray(newElements);
            } else {
                // Not quite a no-op; ensures volatile write semantics
                setArray(elements);
            }
            return oldValue;
        } finally {
            lock.unlock();
        }
    }

 

 

可以看到该法使用ReentrantLock锁, Arrays.copyOf创建一个新的数组是核心思想体现,oldValue != element这个判断更是尽可能的提高性能的努力。

而在esle里面,明明没有任何修改,为什么还要条用set方法,并且在addAllAbsent 方法里面有没有使用,以及那句注释(Not quite a no-op; ensures volatile write semantics),有几封邮件讨论这个问题。

大意是说:为了确保 voliatile 的语义,任何一个读操作都应该是写操作的结构,所以尽管写操作没有改变数据,还是调用set方法,当然这仅仅是语义的说明,去掉也是可以的。而对于 addIfAbsent方法为什么没有使用set方法,那是因为该方法本身的语义就是写或者不写,不写故不需要保持语义。

参考如下:

 

http://cs.oswego.edu/pipermail/concurrency-interest/2010-February/006886.html

http://cs.oswego.edu/pipermail/concurrency-interest/2010-February/006887.html

http://cs.oswego.edu/pipermail/concurrency-interest/2010-February/006888.html

http://en.usenet.digipedia.org/thread/13652/1242/

 

6、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();
        }
    }

 

 同样很简单,遵循,使用锁,Arrays.copyOf copy新数组、新增一个元素、set回去步骤。

另外一个重载的指定位置add元素的核心代码如下:

 

  newElements = new Object[len + 1];
  System.arraycopy(elements, 0, newElements, 0, index);
  System.arraycopy(elements, index, newElements, index + 1,  numMoved);

主要使用System.arraycopy方法copy到一个新的数组

 

 7、remove方法:

public E remove(int index) {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            Object[] elements = getArray();
            int len = elements.length;
            E oldValue = get(elements, index);
            int numMoved = len - index - 1;
            if (numMoved == 0)
                setArray(Arrays.copyOf(elements, len - 1));
            else {
                Object[] newElements = new Object[len - 1];
                System.arraycopy(elements, 0, newElements, 0, index);
                System.arraycopy(elements, index + 1, newElements, index,
                                 numMoved);
                setArray(newElements);
            }
            return oldValue;
        } finally {
            lock.unlock();
        }
    }

 

同样很简单,使用 System.arraycopy、Arrays.copyOf移动元素

移除指定元素方法的核心代码:通过双重循环,比较移动。

                 for (int i = 0; i < newlen; ++i) {
                    if (eq(o, elements[i])) {
                        // found one;  copy remaining and exit
                        for (int k = i + 1; k < len; ++k)
                            newElements[k-1] = elements[k];
                        setArray(newElements);
                        return true;
                    } else
                        newElements[i] = elements[i];
                }

 移除指定集合内方法核心代码:

                for (int i = 0; i < len; ++i) {
                    Object element = elements[i];
                    if (!c.contains(element))
                        temp[newlen++] = element;
                }
                if (newlen != len) {
                    setArray(Arrays.copyOf(temp, newlen));
                    return true;
                }
           

8、addIfAbsent  方法:

 public boolean addIfAbsent(E e) {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            // Copy while checking if already present.
            // This wins in the most common case where it is not present
            Object[] elements = getArray();
            int len = elements.length;
            Object[] newElements = new Object[len + 1];
            for (int i = 0; i < len; ++i) {
                if (eq(e, elements[i]))
                    return false; // exit, throwing away copy
                else
                    newElements[i] = elements[i];
            }
            newElements[len] = e;
            setArray(newElements);
            return true;
        } finally {
            lock.unlock();
        }
    }

 

这里可以看到没有又相同的元素之间return了,没有调用set方法;

9、retainAll 方法:

                Object[] temp = new Object[len];
                for (int i = 0; i < len; ++i) {
                    Object element = elements[i];
                    if (c.contains(element))
                        temp[newlen++] = element;
                } 

基本是removeAll的翻版,只是 if (c.contains(element)) 这个是否定罢了。

10、writeObject、readObject方法:

 private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException{
        s.defaultWriteObject();
        Object[] elements = getArray();
        // Write out array length
        s.writeInt(elements.length);
        // Write out all elements in the proper order.
        for (Object element : elements)
            s.writeObject(element);
    }
 
    private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {
        s.defaultReadObject();
        // bind to new lock
        resetLock();
        // Read in array length and allocate array
        int len = s.readInt();
        Object[] elements = new Object[len];

        // Read in all elements in the proper order.
        for (int i = 0; i < len; i++)
            elements[i] = s.readObject();
        setArray(elements);
    }

 

虽然CopyOnWriteArrayList 类实现了 序列化接口,但是变量数组确有transient关键字通过实现这两个方法。将快照序列化

11、iterator  方法:

 

public void remove() {
            throw new UnsupportedOperationException();
        }

 

 

针对iterator使用了一个叫COWIterator的阉割版迭代器,因为不支持写操作 ,如上面add、set、remove都会跑出异常,当获取CopyOnWriteArrayList的迭代器时,是将迭代器里的数据引用指向当前引用指向的数据对象,无论未来发生什么写操作,都不会再更改迭代器里的数据对象引用,所以迭代器也很安全。

 

 

综上:

 

在CopyOnWriteArrayList里处理写操作(包括add、remove、set等)是先将原始的数据通过Arrays.copyof()来生成一份新的数组,然后在新的数据对象上进行写,写完后再将原来的引用指向到当前这个数据对象,并且加锁。

 

读操作是在引用的当前对象上进行读(包括get,iterator等),不存在加锁和阻塞。

 

因为每次使用CopyOnWriteArrayList.add都要引起数组拷贝, 所以应该避免在循环中使用CopyOnWriteArrayList.add。可以在初始化完成后设置到CopyOnWriteArrayList中,或者使用CopyOnWriteArrayList.addAll方法

 

 

CopyOnWriteArrayList采用“写入时复制”策略,对容器的写操作将导致的容器中基本数组的复制,性能开销较大。所以在有写操作的情况下,CopyOnWriteArrayList性能不佳,而且如果容器容量较大的话容易造成溢出。

 

 

本站支持 pay for your wishes

  • 大小: 109.7 KB
分享到:
评论
2 楼 _神谕_ 2016-07-17  
1 楼 accphc 2015-03-13  

相关推荐

    run_ver3.zip

    由于这个标签并不常见,我们暂时无法进一步解读。 压缩文件内部包含了一个名为"run_ver3.txt"的文本文件。这通常表示这是一个纯文本文件,可能包含了日志信息、配置设置、代码片段或者是程序的说明文档。如果这是...

    JUC最详细思维导图,一次了解读写锁,可重入锁,Cas原理,volatile 关键字原理

    `CopyOnWriteArrayList`是线程安全的动态数组,适用于读多写少的情况,通过复制底层数组实现并发访问,保证了读操作的高性能。 阻塞队列`BlockingQueue`是一个接口,提供了一种在队列为空或已满时线程等待的机制。...

    javaforkjoin源码-gitbook-BAT-interview:本文综合自己在一线互联网工作感悟,经验。记录开源框架的源码解读,数据

    java forkjoin 源码 -- -- geomesa -- spring -- 算法 -- hbase -- 数据库 -- 高并发 [Java Memory Modle内存模型] ...[乐观锁&悲观锁,重入锁&非重入锁,公平锁&非公平锁,锁粒度] ...CopyOnWriteArrayList源码]

    Java高并发程序设计视频

    以下是对课程内容的详细解读: 1. 内存模型与线程安全: - Java内存模型(JMM)定义了共享变量如何在多线程环境中被访问和更新的规则。理解JMM有助于避免数据竞争和保证线程间同步。 - 线程安全意味着对象或方法...

    ArrayList源码分析

    如果需要线程安全的列表,应使用`CopyOnWriteArrayList`。 7. **ArrayList与LinkedList的比较** - ArrayList更适合于随机访问,插入和删除在中间位置较慢。 - LinkedList适合于频繁的插入和删除,但随机访问性能...

    java8源码-JavaRobot:Java学习笔记,JavaLearningNote

    CopyOnWriteArrayList Vector Map源码系列 HashMap LinkedHashMap ConcurrentHashMap TreeMap Hashtable Set源码系列 HashSet LinkedHashSet TreeSet HashSet Concurrent源码系列 待完善 JVM(Java虚拟机) 类加载 ...

    java并发编程的艺术

    以下是对该书内容的详细解读: 1. **并发基础** - 并发与并行的区别:并发是指多个任务交替执行,而并行则是指多个任务在同一时刻执行。 - Java中的线程:Java通过`Thread`类提供了线程支持,开发者可以通过创建`...

    toBeBetterJavaer-master.zip

    以下是对其中各个模块的详细解读: 1. **Java基础**:这部分内容通常包括Java语法基础,如变量、数据类型、控制结构(如if-else、switch-case、for、while)、类与对象、封装、继承、多态等概念。此外,还有异常...

    龙果学院java并发编程完整视频

    由于提供的链接和代码片段无法直接访问或解读具体内容,本篇将基于标题、描述以及标签所暗示的内容来构建相关的知识点。 ### Java并发编程概述 Java并发编程是Java语言中的一个高级特性,它允许程序在多线程环境中...

    Java并发编程原理与实战

    并发容器CopyOnWriteArrayList原理与使用.mp4 并发容器ConcurrentLinkedQueue原理与使用.mp4 Java中的阻塞队列原理与使用.mp4 实战:简单实现消息队列.mp4 并发容器ConcurrentHashMap原理与使用.mp4 线程池的原理与...

    Java面试-一线大厂面试真题

    以下是对这些知识点的详细解读: 1. **Java基础语法**:这是所有Java开发者必须掌握的基本技能,包括变量、数据类型、运算符、控制结构(如if语句、switch、for、while循环)、方法、类和对象、继承、接口、异常...

    2018 Java面试题总结

    以下是对这些主题的详细解读: 1. **数据库篇**: - SQL基础:了解SQL语言的基本语法,如SELECT、INSERT、UPDATE、DELETE操作,以及JOIN、子查询、索引和事务处理。 - 数据库设计:理解关系型数据库的概念,包括...

    java_util_concurrent中文版pdf

    3. **并发集合**:并发集合包括ConcurrentHashMap、CopyOnWriteArrayList、CopyOnWriteArraySet等,它们在并发环境下提供了高效且线程安全的数据结构。例如,ConcurrentHashMap使用分段锁技术,允许多个线程同时进行...

    Java并发编程实践

    以下是对该书内容的详细解读。 首先,我们要明白Java并发编程的基础——线程。线程是操作系统分配CPU时间的基本单位,Java通过`Thread`类提供了对线程的支持。创建线程主要有两种方式:继承`Thread`类和实现`...

    java并发编程实践中文版和英文版

    以下是对该书内容的详细解读: 1. **并发编程基础**:书中首先介绍了并发编程的基本概念,包括线程、进程以及并发与并行的区别。同时,讨论了Java中的线程模型,如Java虚拟机(JVM)如何管理线程,以及线程的创建、...

    Java并发编程实践.rar

    以下是对该书内容的详细解读: 第一章:并发编程简介 本章介绍了并发编程的基本概念,包括进程、线程、同步与异步执行,以及为什么在Java中需要进行并发编程。同时,讲解了Java中实现并发的基石——JVM内存模型,...

    2023年Java 面试题.zip

    以下是对这些文件内容的详细解读和相关知识点的扩展: 1. **Java基础**:这部分内容通常会涉及Java的基本数据类型、变量、运算符、流程控制语句、类与对象、封装、继承、多态等概念。例如,深入理解面向对象的三大...

    Java并发编程设计原则与模式.pdf

    以下是对书中核心知识点的详细解读: 1. **并发基础**:首先,书中会介绍并发编程的基本概念,包括线程、进程、同步与通信。理解这些基础是进一步学习并发编程的前提。 2. **Java并发API**:Java提供了丰富的并发...

    Java 并发编程实战

    以下是对该书内容的详细解读: 1. **并发基础** - **线程与进程**:首先,书中会介绍线程与进程的基本概念,以及它们在操作系统中的角色,包括线程的创建、销毁、同步与通信。 - **Java线程API**:讲解Java提供的...

    [Java并发编程实践].(Java.Concurrency.in.Practice).Brian.Goetz.文字版(1)

    以下是对本书核心知识点的详细解读: 1. **并发基础**:书中首先介绍了并发的基本概念,包括线程、进程以及并发与并行的区别。同时,讨论了Java中的Thread类和Runnable接口,以及如何创建和管理线程。 2. **同步...

Global site tag (gtag.js) - Google Analytics