java中CopyOnWriteArrayList源码解析

目录
  • 简介
  • 继承体系
  • 源码解析
    • 属性
    • 构造方法
    • add(Ee)方法
    • add(intindex,Eelement)方法
    • addIfAbsent(Ee)方法
    • get(intindex)
    • remove(intindex)方法
    • size()方法
  • 提问
  • 总结

简介

CopyOnWriteArrayList是ArrayList的线程安全版本,内部也是通过数组实现,每次对数组的修改都完全拷贝一份新的数组来修改,修改完了再替换掉老数组,这样保证了只阻塞写操作,不阻塞读操作,实现读写分离。

继承体系

public class CopyOnWriteArrayList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable
    {...}
  • CopyOnWriteArrayList实现了List,RandomAccess,Cloneable,java.io.Serializable等接口。
  • CopyOnWriteArrayList实现了List,提供了基础的添加、删除、遍历等操作。
  • CopyOnWriteArrayList实现了RandomAccess,提供了随机访问的能力。
  • CopyOnWriteArrayList实现了Cloneable,可以被克隆。
  • CopyOnWriteArrayList实现了Serializable,可以被序列化。

源码解析

属性

/** 用于修改时加锁 */
final transient ReentrantLock lock = new ReentrantLock();

/** 真正存储元素的地方,只能通过getArray()/setArray()访问 */
private transient volatile Object[] array;
  • lock:修改时加锁,使用transient修饰表示不自动序列化。
  • array:存储元素的地方,使用transient修饰表示不自动序列化,使用volatile修饰表示一个线程对这个字段的修改另外一个线程立即可见。

构造方法

创建空数组。

public CopyOnWriteArrayList() {
    // 所有对array的操作都是通过setArray()和getArray()进行
    setArray(new Object[0]);
}

final void setArray(Object[] a) {
    array = a;
}
public CopyOnWriteArrayList(Collection<? extends E> c) {
    Object[] elements;
    if (c.getClass() == CopyOnWriteArrayList.class)
        // 如果c也是CopyOnWriteArrayList类型
        // 那么直接把它的数组拿过来使用
        elements = ((CopyOnWriteArrayList<?>)c).getArray();
    else {
        // 否则调用其toArray()方法将集合元素转化为数组
        elements = c.toArray();
        // 这里c.toArray()返回的不一定是Object[]类型
        // 详细原因见ArrayList里面的分析
        if (elements.getClass() != Object[].class)
            elements = Arrays.copyOf(elements, elements.length, Object[].class);
    }
    setArray(elements);
}
  • 如果 c 是CopyOnWriteArrayList类型,直接把它的数组赋值给当前list的数组,注意这里是浅拷贝,两个集合共用同一个数组。
  • 如果 c 不是CopyOnWriteArrayList类型,则进行拷贝把c的元素全部拷贝到当前list的数组中。
public CopyOnWriteArrayList(E[] toCopyIn) {
    setArray(Arrays.copyOf(toCopyIn, toCopyIn.length, Object[].class));
}
  • 把toCopyIn的元素拷贝给当前list的数组。

add(E e)方法

添加一个元素到末尾。

public boolean add(E e) {
    final ReentrantLock lock = this.lock;
    // 加锁
    lock.lock();
    try {
        // 获取旧数组
        Object[] elements = getArray();
        int len = elements.length;
        // 将旧数组元素拷贝到新数组中
        // 新数组大小是旧数组大小加1
        Object[] newElements = Arrays.copyOf(elements, len + 1);
        // 将元素放在最后一位
        newElements[len] = e;
        setArray(newElements);
        return true;
    } finally {
        // 释放锁
        lock.unlock();
    }
}
  • 加锁;
  • 获取元素数组;
  • 新建一个数组,大小为原数组长度加1,并把原数组元素拷贝到新数组;
  • 把新添加的元素放到新数组的末尾;
  • 把新数组赋值给当前对象的array属性,覆盖原数组;
  • 解锁。

add(int index, E element)方法

添加一个元素在指定索引处。

public void add(int index, E element) {
    final ReentrantLock lock = this.lock;
    // 加锁
    lock.lock();
    try {
        // 获取旧数组
        Object[] elements = getArray();
        int len = elements.length;
        // 检查是否越界, 可以等于len
        if (index > len || index < 0)
            throw new IndexOutOfBoundsException("Index: "+index+
                                                ", Size: "+len);
        Object[] newElements;
        int numMoved = len - index;
        if (numMoved == 0)
            // 如果插入的位置是最后一位
            // 那么拷贝一个n+1的数组, 其前n个元素与旧数组一致
            newElements = Arrays.copyOf(elements, len + 1);
        else {
            // 如果插入的位置不是最后一位
            // 那么新建一个n+1的数组
            newElements = new Object[len + 1];
            // 拷贝旧数组前index的元素到新数组中
            System.arraycopy(elements, 0, newElements, 0, index);
            // 将index及其之后的元素往后挪一位拷贝到新数组中
            // 这样正好index位置是空出来的
            System.arraycopy(elements, index, newElements, index + 1,
                             numMoved);
        }
        // 将元素放置在index处
        newElements[index] = element;
        setArray(newElements);
    } finally {
        // 释放锁
        lock.unlock();
    }
}
  • 加锁;
  • 检查索引是否合法,如果不合法抛出IndexOutOfBoundsException异常,注意这里 index 等于 len 也是合法的;
  • 如果索引等于数组长度(也就是数组最后一位再加1),那就拷贝一个len+1的数组;
  • 如果索引不等于数组长度,那就新建一个len+1的数组,并按索引位置分成两部分,索引之前(不包含)的部分拷贝到新数组索引之前(不包含)的部分,索引之后(包含)的位置拷贝到新数组索引之后(不包含)的位置,索引所在位置留空;
  • 把索引位置赋值为待添加的元素;
  • 把新数组赋值给当前对象的array属性,覆盖原数组;
  • 解锁;

addIfAbsent(E e)方法

添加一个元素如果这个元素不存在于集合中。

public boolean addIfAbsent(E e) {
    // 获取元素数组, 取名为快照
    Object[] snapshot = getArray();
    // 检查如果元素不存在,直接返回false
    // 如果存在再调用addIfAbsent()方法添加元素
    return indexOf(e, snapshot, 0, snapshot.length) >= 0 ? false :
        addIfAbsent(e, snapshot);
}

private boolean addIfAbsent(E e, Object[] snapshot) {
    final ReentrantLock lock = this.lock;
    // 加锁
    lock.lock();
    try {
        // 重新获取旧数组
        Object[] current = getArray();
        int len = current.length;
        // 如果快照与刚获取的数组不一致
        // 说明有修改
        if (snapshot != current) {
            // 重新检查元素是否在刚获取的数组里
            int common = Math.min(snapshot.length, len);
            for (int i = 0; i < common; i++)
                // 到这个方法里面了, 说明元素不在快照里面
                if (current[i] != snapshot[i] && eq(e, current[i]))
                    return false;
            if (indexOf(e, current, common, len) >= 0)
                    return false;
        }
        // 拷贝一份n+1的数组
        Object[] newElements = Arrays.copyOf(current, len + 1);
        // 将元素放在最后一位
        newElements[len] = e;
        setArray(newElements);
        return true;
    } finally {
        // 释放锁
        lock.unlock();
    }
}
  • 检查这个元素是否存在于数组快照中;
  • 如果存在直接返回 false,如果不存在调用addIfAbsent(E e, Object[] snapshot)处理;
  • 加锁;
  • 如果当前数组不等于传入的快照,说明有修改,检查待添加的元素是否存在于当前数组中,如果存在直接返回false;
  • 拷贝一个新数组,长度等于原数组长度加1,并把原数组元素拷贝到新数组中;
  • 把新元素添加到数组最后一位;
  • 把新数组赋值给当前对象的array属性,覆盖原数组;
  • 解锁;

get(int index)

获取指定索引的元素,支持随机访问,时间复杂度为O(1)。

public E get(int index) {
    // 获取元素不需要加锁
    // 直接返回index位置的元素
    // 这里是没有做越界检查的, 因为数组本身会做越界检查
    return get(getArray(), index);
}

final Object[] getArray() {
    return array;
}

private E get(Object[] a, int index) {
    return (E) a[index];
}
  • 获取元素数组;
  • 返回数组指定索引位置的元素;

remove(int index)方法

删除指定索引位置的元素。

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)
            // 如果移除的是最后一位
            // 那么直接拷贝一份n-1的新数组, 最后一位就自动删除了
            setArray(Arrays.copyOf(elements, len - 1));
        else {
            // 如果移除的不是最后一位
            // 那么新建一个n-1的新数组
            Object[] newElements = new Object[len - 1];
            // 将前index的元素拷贝到新数组中
            System.arraycopy(elements, 0, newElements, 0, index);
            // 将index后面(不包含)的元素往前挪一位
            // 这样正好把index位置覆盖掉了, 相当于删除了
            System.arraycopy(elements, index + 1, newElements, index,
                             numMoved);
            setArray(newElements);
        }
        return oldValue;
    } finally {
        // 释放锁
        lock.unlock();
    }
}
  • 加锁;
  • 获取指定索引位置元素的旧值;
  • 如果移除的是最后一位元素,则把原数组的前len-1个元素拷贝到新数组中,并把新数组赋值给当前对象的数组属性;
  • 如果移除的不是最后一位元素,则新建一个len-1长度的数组,并把原数组除了指定索引位置的元素全部拷贝到新数组中,并把新数组赋值给当前对象的数组属性;
  • 解锁并返回旧值;

size()方法

返回数组的长度。

public int size() {
    // 获取元素个数不需要加锁
    // 直接返回数组的长度
    return getArray().length;
}

提问

为什么CopyOnWriteArrayList没有size属性?

因为每次修改都是拷贝一份正好可以存储目标个数元素的数组,所以不需要size属性了,数组的长度就是集合的大小,而不像ArrayList数组的长度实际是要大于集合的大小的。比如,add(E e)操作,先拷贝一份n+1个元素的数组,再把新元素放到新数组的最后一位,这时新数组的长度为len+1了,也就是集合的size了。

总结

  • CopyOnWriteArrayList使用ReentrantLock重入锁加锁,保证线程安全;
  • CopyOnWriteArrayList的写操作都要先拷贝一份新数组,在新数组中做修改,修改完了再用新数组替换老数组,所以空间复杂度是O(n),性能比较低下;
  • CopyOnWriteArrayList的读操作支持随机访问,时间复杂度为O(1);
  • CopyOnWriteArrayList采用读写分离的思想,读操作不加锁,写操作加锁,且写操作占用较大内存空间,所以适用于读多写少的场合;
  • CopyOnWriteArrayList只保证最终一致性,不保证实时一致性。

到此这篇关于java中CopyOnWriteArrayList源码解析的文章就介绍到这了,更多相关java中CopyOnWriteArrayList内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • java并发容器CopyOnWriteArrayList实现原理及源码分析

    CopyOnWriteArrayList是Java并发包中提供的一个并发容器,它是个线程安全且读操作无锁的ArrayList,写操作则通过创建底层数组的新副本来实现,是一种读写分离的并发策略,我们也可以称这种容器为"写时复制器",Java并发包中类似的容器还有CopyOnWriteSet.本文会对CopyOnWriteArrayList的实现原理及源码进行分析. 实现原理 我们都知道,集合框架中的ArrayList是非线程安全的,Vector虽是线程安全的,但由于简单粗暴的锁同步机制,

  • Java并发包之CopyOnWriteArrayList类的深入讲解

    前言 大家在学习Java的过程中,或者工作中,始终都绕不开集合.在单线程环境下,ArrayList就可以满足要求.多线程时,我们可以使用CopyOnWriteArrayList来保证数据安全.下面我们一起来看看CopyOnWriteArrayList类中的一些值得学习的方法. CopyOnWriteArrayList是一个线程安全的ArrayList,对其进行的修改操作都是在底层的一个复制的数组(快照)上进行的,也就是使用了写时复制策略实现的. 说明:代码部分,均基于JDK1.8 一.添加元素

  • Java concurrency集合之 CopyOnWriteArrayList_动力节点Java学院整理

    CopyOnWriteArrayList介绍 它相当于线程安全的ArrayList.和ArrayList一样,它是个可变数组:但是和ArrayList不同的时,它具有以下特性: 1. 它最适合于具有以下特征的应用程序:List 大小通常保持很小,只读操作远多于可变操作,需要在遍历期间防止线程间的冲突. 2. 它是线程安全的. 3. 因为通常需要复制整个基础数组,所以可变操作(add().set() 和 remove() 等等)的开销很大. 4. 迭代器支持hasNext(), next()等不可

  • Java源码解析CopyOnWriteArrayList的讲解

    本文基于jdk1.8进行分析. ArrayList和HashMap是我们经常使用的集合,它们不是线程安全的.我们一般都知道HashMap的线程安全版本为ConcurrentHashMap,那么ArrayList有没有类似的线程安全的版本呢?还真有,它就是CopyOnWriteArrayList. CopyOnWrite这个短语,还有一个专门的称谓COW. COW不仅仅是java实现集合框架时专用的机制,它在计算机中被广泛使用. 首先看一下什么是CopyOnWriteArrayList,它的类前面

  • java中CopyOnWriteArrayList源码解析

    目录 简介 继承体系 源码解析 属性 构造方法 add(Ee)方法 add(intindex,Eelement)方法 addIfAbsent(Ee)方法 get(intindex) remove(intindex)方法 size()方法 提问 总结 简介 CopyOnWriteArrayList是ArrayList的线程安全版本,内部也是通过数组实现,每次对数组的修改都完全拷贝一份新的数组来修改,修改完了再替换掉老数组,这样保证了只阻塞写操作,不阻塞读操作,实现读写分离. 继承体系 public

  • Java中LinkedHashMap源码解析

    概述: LinkedHashMap实现Map继承HashMap,基于Map的哈希表和链该列表实现,具有可预知的迭代顺序. LinedHashMap维护着一个运行于所有条目的双重链表结构,该链表定义了迭代顺序,可以是插入或者访问顺序. LintHashMap的节点对象继承HashMap的节点对象,并增加了前后指针 before after: /** * LinkedHashMap节点对象 */ static class Entry<K,V> extends HashMap.Node<K,V

  • Java Lambda 表达式源码解析

    Java Lambda 源码分析 问题: Lambda 表达式是什么?JVM 内部究竟是如何实现 Lambda 表达式的?为什么要这样实现? 一.基本概念 1.Lambda 表达式 下面的例子中,() -> System.out.println("1") 就是一个 Lambda 表达式.Java 8 中每一个 Lambda 表达式必须有一个函数式接口与之对应.Lambda 表达式就是函数式接口的一个实现. @Test public void test0() { Runnable

  • java 中Buffer源码的分析

    java 中Buffer源码的分析 Buffer Buffer的类图如下: 除了Boolean,其他基本数据类型都有对应的Buffer,但是只有ByteBuffer才能和Channel交互.只有ByteBuffer才能产生Direct的buffer,其他数据类型的Buffer只能产生Heap类型的Buffer.ByteBuffer可以产生其他数据类型的视图Buffer,如果ByteBuffer本身是Direct的,则产生的各视图Buffer也是Direct的. Direct和Heap类型Buff

  • Java 中模仿源码自定义ArrayList

    Java 中模仿源码自定义ArrayList 最近看了下ArrayList的源码,抽空根据ArrayList的底层结构写了一个功能简单无泛型的自定义ArrayLsit,帮助自己更好理解ArrayList:,其实现的底层数据结构为数Object组,代码如下: /** * 自己实现一个ArrayList * */ public class MyArrayList { private Object[] elementData; private int size; public int size(){

  • Java Spring AOP源码解析之事务实现原理

    目录 不用Spring管理事务? 编程式事务管理 使用PlatformTransactionManager 使用TransactionTemplate 声明式事务管理 使用@Transactional注解 源码解析 参考博客 总结 不用Spring管理事务? 让我们先来看一下不用spring管理事务时,各种框架是如何管理事务的 使用JDBC来管理事务 使用Hibernate来管理事务 业务逻辑和事务代码是耦合到一块的,并且和框架的具体api绑定了.当我们换一种框架来实现时,里面对事务控制的代码就

  • java集合类HashMap源码解析

    Map集合 Map集合存储的是键值对 Map集合的实现类: HashTable.LinkedHashMap.HashMap.TreeMap HashMap 基础了解: 1.键不可以重复,值可以重复: 2.底层使用哈希表实现: 3.线程不安全: 4.允许key为null,但只允许有一条记录为null,value也可以为null,允许多条记录为null: 源码分析 (一)以JDK1.7为例 1.存储结构 数据结构:数组+链表 首先hashmap内部有一个Entry类型的数组table: 通过Entr

  • java基础类型源码解析之多角度讲HashMap

    前言 终于来到比较复杂的HashMap,由于内部的变量,内部类,方法都比较多,没法像ArrayList那样直接平铺开来说,因此准备从几个具体的角度来切入. 桶结构 HashMap的每个存储位置,又叫做一个桶,当一个Key&Value进入map的时候,依据它的hash值分配一个桶来存储. 看一下桶的定义:table就是所谓的桶结构,说白了就是一个节点数组. transient Node<K,V>[] table; transient int size; 节点 HashMap是一个map结

  • Java并发编程之CountDownLatch源码解析

    一.前言 CountDownLatch维护了一个计数器(还是是state字段),调用countDown方法会将计数器减1,调用await方法会阻塞线程直到计数器变为0.可以用于实现一个线程等待所有子线程任务完成之后再继续执行的逻辑,也可以实现类似简易CyclicBarrier的功能,达到让多个线程等待同时开始执行某一段逻辑目的. 二.使用 一个线程等待其它线程执行完再继续执行 ...... CountDownLatch cdl = new CountDownLatch(10); Executor

  • java中break和continue源码解析

    在自己学习java语言的过程中,很容易把break和continue的用法混淆.为了便于以后快速查阅及温习,在此特留学习笔记一份. 简述 在任何迭代语句的主体部分,都可以用break和continue控制循环的流程.其中,break用于强行退出循环,不执行循环中剩余的语句.而continue则停止执行当前迭代,然后退回循环起始处,开始下一次迭代. 源码 下面这个程序向大家展示了break和continue在for和while循环中的例子: package com.mufeng.thefourth

随机推荐