文档章节

ArrayList的实现原理以及实现线程安全

一看就喷亏的小猿
 一看就喷亏的小猿
发布于 2018/12/18 00:33
字数 1490
阅读 109
收藏 0

一、ArrayList概述

  1. ArrayList是基于数组实现的,是一个动态的数字,可以自动扩容。
  2. ArrayList不是线程安全的,效率比较高,只能用于单线程的环境中,在多线程环境中可以使用Collections.synchronizedList(List list)函数返回一个线程安全的ArrayList集合,或者使用concurrent并发包下的CopyOnWriteArrayList的。
//使用Collections.synchronizedList(List list)方法实现线程安全
List<?> list=Collections.synchronizedList(new ArrayList<>());

二、通过源码解析Collections.synchronizedList(List list)方法如何实现线程安全?

public static List synchronizedList(List list1) {
	return ((List) ((list1 instanceof RandomAccess) ? new SynchronizedRandomAccessList(list1)
				: new SynchronizedList(list1)));
}

         通过判断传入的list类是否为RandomAccess类,如果是则实例化SynchronizedRandomAccessList,如果不是,则实例化SynchronizedList。如果你传入的list集合是ArrayList或者Vector。那么则是实例化SynchronizedRandomAccessList。我们从源码可以查看原因:

ArrayList集合源码

public class ArrayList extends AbstractList implements List, RandomAccess, Cloneable, Serializable {

Vector集合源码:

public class Vector extends AbstractList implements List, RandomAccess, Cloneable, Serializable {

        我们可以发现ArrayList和Vector集合两者都实现了List和RandomAccess接口。接下来看看SynchronizedRandomAccessList类的实现:

	static class SynchronizedRandomAccessList extends SynchronizedList implements RandomAccess {

		public List subList(int i, int j)
        {
            Object obj = mutex;
            return new SynchronizedRandomAccessList(list.subList(i, j), mutex);
        }

		private Object writeReplace() {
			return new SynchronizedList(list);
		}

		private static final long serialVersionUID = 1530674583602358482L;

		SynchronizedRandomAccessList(List list1) {
			super(list1);
		}

		SynchronizedRandomAccessList(List list1, Object obj) {
			super(list1, obj);
		}
	}

       因为SynchronizedRandomAccessList这个类继承自SynchronizedList,而大部分方法都在SynchronizedList中实现了,所以源码中只包含了很少的方法。我们来看看SynchronizedList的源码:

static class SynchronizedList<E>
    extends SynchronizedCollection<E>
    implements List<E> {
    private static final long serialVersionUID = -7754090372962971524L;

    final List<E> list;

    SynchronizedList(List<E> list) {
        super(list);
        this.list = list;
    }
    SynchronizedList(List<E> list, Object mutex) {
        super(list, mutex);
        this.list = list;
    }

    public boolean equals(Object o) {
        if (this == o)
            return true;
        synchronized (mutex) {return list.equals(o);}
    }
    public int hashCode() {
        synchronized (mutex) {return list.hashCode();}
    }

    public E get(int index) {
        synchronized (mutex) {return list.get(index);}
    }
    public E set(int index, E element) {
        synchronized (mutex) {return list.set(index, element);}
    }
    public void add(int index, E element) {
        synchronized (mutex) {list.add(index, element);}
    }
    public E remove(int index) {
        synchronized (mutex) {return list.remove(index);}
    }

    public int indexOf(Object o) {
        synchronized (mutex) {return list.indexOf(o);}
    }
    public int lastIndexOf(Object o) {
        synchronized (mutex) {return list.lastIndexOf(o);}
    }

    public boolean addAll(int index, Collection<? extends E> c) {
        synchronized (mutex) {return list.addAll(index, c);}
    }

    public ListIterator<E> listIterator() {
        return list.listIterator(); // Must be manually synched by user
    }

    public ListIterator<E> listIterator(int index) {
        return list.listIterator(index); // Must be manually synched by user
    }

    public List<E> subList(int fromIndex, int toIndex) {
        synchronized (mutex) {
            return new SynchronizedList<>(list.subList(fromIndex, toIndex),
                                        mutex);
        }
    }

    @Override
    public void replaceAll(UnaryOperator<E> operator) {
        synchronized (mutex) {list.replaceAll(operator);}
    }
    @Override
    public void sort(Comparator<? super E> c) {
        synchronized (mutex) {list.sort(c);}
    }
    ... ...
}

       可以发现SynchronizedList方法中地方都用到了同步锁,并且参数都是mutex。我们通过点击mutex字段进入到SynchronizedCollection类中,可以得知mutex是在SynchronizedCollection类中定义的。我们继续查看SynchronizedCollection部分源码:

static class SynchronizedCollection<E> implements Collection<E>, Serializable {  
    private static final long serialVersionUID = 3053995032091335093L;  
    final Collection<E> c;  // Backing Collection  
    final Object mutex;     // Object on which to synchronize  

    SynchronizedCollection(Collection<E> c) {  
            if (c==null)  
                throw new NullPointerException();  
        this.c = c;  
            mutex = this;  
        }  

    SynchronizedCollection(Collection<E> c, Object mutex) {  
        this.c = c;  
            this.mutex = mutex;  
        }  
}

        可以发现其实我们调用synchronizedList方法的使用,内部锁都是一样的,所以它可以实现线程的同步。

三、通过源码解析CopyOnWriteArrayList如何做到线程安全的?

CopyOnWriteArrayList使用了一种叫写时复制的方法,当有新元素添加到CopyOnWriteArrayList时,先从原有的数组中拷贝一份出来,然后在新的数组做写操作,写完之后,再将原来的数组引用指向到新数组。

当有新元素加入的时候,如下图,创建新数组,并往新数组中加入一个新元素,这个时候,array这个引用仍然是指向原数组的。

当元素在新数组添加成功后,将array这个引用指向新数组。

CopyOnWriteArrayList的整个add操作都是在锁的保护下进行的。 
这样做是为了避免在多线程并发add的时候,复制出多个副本出来,把数据搞乱了,导致最终的数组数据不是我们期望的。我们来看看
CopyOnWriteArrayList源码:

    transient final ReentrantLock lock = new ReentrantLock();  
  
    /** The array, accessed only via getArray/setArray. */  
    private volatile transient Object[] array;//保证了线程的可见性  
      
    public boolean add(E e) {  
        final ReentrantLock lock = this.lock;//ReentrantLock 保证了线程的可见性和顺序性,即保证了多线程安全。  
        //1、先加锁
        lock.lock();  
        try {  
           Object[] elements = getArray();  
           int len = elements.length;  
           Object[] newElements = Arrays.copyOf(elements, len + 1);////2、拷贝数组,在原先数组基础之上新建长度+1的数组,并将原先数组当中的内容拷贝到新数组当中。 
           
           //3、将元素加入到新数组中
           newElements[len] = e;
           //4、将array引用指向到新数组
           setArray(newElements);//对新数组进行赋值  
           return true;  
        } finally {  
           lock.unlock();  
        }  
    }

由于所有的写操作都是在新数组进行的,这个时候如果有线程并发的写,则通过锁来控制,如果有线程并发的读,则分几种情况: 
1、如果写操作未完成,那么直接读取原数组的数据; 
2、如果写操作完成,但是引用还未指向新数组,那么也是读取原数组数据; 
3、如果写操作完成,并且引用已经指向了新的数组,那么直接从新数组中读取数据。

可见,CopyOnWriteArrayList的读操作是可以不用加锁的。

四、Collections.synchronizedList & CopyOnWriteArrayList

       CopyOnWriteArrayList和Collections.synchronizedList是实现线程安全的列表的两种方式。两种实现方式分别针对不同情况有不同的性能表现,其中CopyOnWriteArrayList的写操作性能较差,而多线程的读操作性能较好。而Collections.synchronizedList的写操作性能比CopyOnWriteArrayList在多线程操作的情况下要好很多,而读操作因为是采用了synchronized关键字的方式,其读操作性能并不如CopyOnWriteArrayList。因此在不同的应用场景下,应该选择不同的多线程安全实现类。

 

© 著作权归作者所有

共有 人打赏支持
一看就喷亏的小猿
粉丝 1
博文 24
码字总数 47843
作品 0
揭阳
私信 提问
并发容器之写时拷贝的 List 和 Set

对于一个对象来说,我们为了保证它的并发性,通常会选择使用声明式加锁方式交由我们的 Java 虚拟机来完成自动的加锁和释放锁的操作,例如我们的 synchronized。也会选择使用显式锁机制来主动...

Single_YAM
2017/12/02
0
0
java.util包中集合详解

本文只是集合的概述,介绍集合之间的关系,以及各种集合的异同,不会深入介绍具体的实现,具体实现的介绍,可以参见文中提供的链接。 java集合概述 java集合整体分为collection和map两种,接...

jacksu在简书
2018/01/25
0
0
[收藏文章]Java岗位面试题

一、Java基础 1. String类为什么是final的。 final修饰的类不能被继承,即它不能拥有自己的子类,否在会在编译期间报错。 final修饰的方法不能被重写 final修饰的变量,无论是类属性、对象属...

vaneL
2018/01/05
0
0
java中List接口的实现类 ArrayList,LinkedList,Vector 的区别 list实现类源码分析

java面试中经常被问到list常用的类以及内部实现机制,平时开发也经常用到list集合类,因此做一个源码级别的分析和比较之间的差异。 首先看一下List接口的的继承关系: list接口继承Collectio...

分享达人
2016/03/13
0
0
3年Java开发经验面试题总结

前言 毕业转行做开发3年以来, 学到了很多, 加上自己的兴趣爱好, 个人认为已经成为了一个合格的程序员. 与刚开始找工作面试相同的是都会问一些相同的问题, 不同的是现在面试官会更注重为什么,...

java成功之路
2018/10/31
0
0

没有更多内容

加载失败,请刷新页面

加载更多

监听DOM上某一个元素是否发生变化,利用MutationObserver来监听元素变化

/** * 观察DOM是否发变化的事件 * @type {MutationObserver|*} */var MutationObserver = window.MutationObserver || window.WebKitMutationObserver || window.MozMutationObserv......

lwkai
18分钟前
1
0
遇到的问题

问题1:前两天在Nodepad++写了一个登录页面,但在Chrome中调试一直写不进Cookie。 解决办法:Chrome浏览器不支持本地静态js写Cookie。换用Edge调试即可。 内心:卧槽,浪费我这么多时间。 问...

akane_oimo
20分钟前
2
0
Oracle学习日志-6(聚合查询)

聚合函数 聚合函数可以对数据进行某种操作或者计算。比如几个常用的函数: COUNT:计算表中行数。 SUM:计算表中数据列中数据的合计值。 AVG:计算表中数据列中数据的平均值。 MAX:求出表中...

白话
22分钟前
1
0
Axure原型工具Axure RP9安装及Licensee

http://www.zhanshaoyi.com/9132.html

晚风0623
27分钟前
1
0
如何限制用户仅通过HTTPS方式访问OSS?

一、当前存在的问题 当前OSS支持用户使用HTTPS/HTTP协议访问Bucket。但由于HTTP存在安全漏洞。大型企业客户都要求使用HTTPS方式访问OSS,并且拒绝HTTP访问请求。 目前OSS可以通过RAM policy方...

阿里云官方博客
48分钟前
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部