本站消息
一文必懂-深入理解ArrayList与CopyOnWriteList源码
发布于2021-06-12 16:18 阅读(131) 评论(0) 点赞(15) 收藏(0)
ArrayList
ArrayList是线程不安全，底层封装一个Object数组；
属性
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
private static final long serialVersionUID = 8683452581122892189L;
//ArrayList的默认容量为10；
private static final int DEFAULT_CAPACITY = 10;
//调用默认构造方法，会引用空的OBject[]数组。
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//我们的查询和插入数据，都是对elementData的操作；
transient Object[] elementData; // non-private to simplify nested class access
//数组容器的长度；
private int size;
//...
}
构造方法
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
//如果用户指定的长度大于0；就创建一个长度为initialCapacity的Object数组；
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
//如果用户指定的长度为0，就elementData引用的空Object数组EMPTY_ELEMENTDATA;
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
public ArrayList() {
//如果用户不指定长度，则elementData引用DEFAULTCAPACITY_EMPTY_ELEMENTDATA对象；（也是一个空的Object数组）
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
get()
public E get(int index) {
//会验证索引的合法性，如果大于等于容器的长度，则抛出索引越界异常；
rangeCheck(index);
//返回数组的index位置的数据；
return elementData(index);
}
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
add(E e)
添加一个元素
public boolean add(E e) {
//检查是否需要扩容，
ensureCapacityInternal(size + 1); // Increments modCount!!
//将传入的参数e插入在容器size+1的位置；
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
//如果使用默认构造方法new ArrayList()创建对象，且第一次调用add方法，
//则下面的判断成功，第一次调用会默认初始容量为10；
//DEFAULT_CAPACITY：10；
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
//第一种情况：第一次次调用add方法，minCapacity =10，length=0;
//第二种情况：当ArrayList对象的容量已经满了，再调用add方法，
//长度比容器的长度大1,
//以上条件成立，就会进行扩容；
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
//扩容前的容量oldCapacity;
int oldCapacity = elementData.length;
//扩容后的容量newCapacity
// >>位运算，相当于原来的长度/2；
// 扩容为原来的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
//如果是第一次add()，则oldCapacity为0，位运算后newCapacity也为0；
//第一次add()，minCapacity为10，newCapacity为0，下面条件判断成立；
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
//容器数组进行扩容，进行复制操作；
elementData = Arrays.copyOf(elementData, newCapacity);
}
问题
这些方法没有进行同步操作，在并发场景下，多线程同时对ArrayList对象进行读写，写写操作，将会出现并发修改错误java.util.ConcurrentModificationException.
解决ArrayList线程不安全的方法
- 使用new Vector<>();
- 使用Collections.synchronizedList(new ArrayList<>());转换成线程安全类
- 使用new Java.concurrent.CopyOnWriteArrayList<>();
Collections.synchronizedList(new ArrayList<>())
源码：
public static <T> List<T> synchronizedList(List<T> list) {
//传入ArrayList，则创建SynchronizedList对象；
return (list instanceof RandomAccess ?
new SynchronizedRandomAccessList<>(list) :
new SynchronizedList<>(list));
}
SynchronizedList内部封装了一个List链表对象，内部的操作都是使用了synchronized关键进行同步；性质和Vector差不多；
static class SynchronizedList<E>
extends SynchronizedCollection<E>
implements List<E> {
final List<E> list;
SynchronizedList(List<E> list) {
super(list);
this.list = list;
}
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);}
}
//...省略部分代码
}
CopyOnWriteList
public class ContainerNotSafeDemo {
/*
* 1 故障现象
* java.util.ConcurrentModificationException
*
* 2 导致原因
* 并发争抢修改导致，参考我们的花名册签名情况。
* 一个人正在写入，另一个同学过来抢夺，导致数据不一致异常。并发修改异常。
*
* 3 解决方案
* 3.1 new Vector<>();
* 3.2 集合工具类：Collections.synchronizedList(new ArrayList<>());
* 3.3 new CopyOnWriteArrayList<>()
* 写时复制：CopyOnWrite容器即写时复制的容器。
* 往一个容器添加元素的时候，不直接往当前容器Object[]添加，而是先将当前object[]进行Copy，
* 复制出一个新的容器Object[] newElements，然后新的容器Object[] newElements里添加元素，
* 添加完元素之后，再将原容器的引用指向新的容器setArray(newElements);
* 这样做的好处是可以对CopyOnWrite容器进行并发的读，而不需要加锁，因为当前容器不会添加任何元素。
* 所以CopyOnWrite容器也是一种读写分离的思想，读和写不同的容器。
*
* 4 优化建议（同样的错误不犯两次）
*
* */
public static void main(String[] args) {
listNotSafe();
}
private static void listNotSafe() {
List<String> list = new CopyOnWriteArrayList<>();
for (int i = 1; i <= 30; i++) {
new Thread(() -> {
list.add(UUID.randomUUID().toString().substring(0, 8));
System.out.println(Thread.currentThread().getName() + "\t" + list);
}, String.valueOf(i)).start();
}
}
}
数据结构
包含了一把可重入锁和数组容器；
public class CopyOnWriteArrayList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
//属性里封装一把可重入锁，用于同步操作
final transient ReentrantLock lock = new ReentrantLock();
//存储数据的数组容器；
private transient volatile Object[] array;
//...省略部分代码
}
get(int index)
获取链表index位置的数据；
public E get(int index) {
return get(getArray(), index);
}
final Object[] getArray() {
//返回容器数组；
return array;
}
private E get(Object[] a, int index) {
//获得容器中index处的数据；
return (E) a[index];
}
add(E 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);
//在len的位置插入数据e;
newElements[len] = e;
//将容器引用指向新的数组容器对象newElements；
setArray(newElements);
return true;
} finally {
//最后释放锁；让其他线程持有这个锁，进行插入数据操作；
lock.unlock();
}
}
特点：
- 写时复制：CopyOnWrite容器，即写时复制一个新的容器
- 往容器中添加元素时，不直接往当前容器中Object[]添加，而是先将当前Object[]进行复制，复制出一个新的容器Object[] new Elements,然后新的容器Object[] newElments里面添加元素，添加完后，再将原容器的引用指向新的容器setArray(new Elements);—>旧容器会被垃圾回收掉
- 这样做的好处是可以对CopyOnWrite容器进行并发的读，而不需要加锁，因为当前容器不会修改任何修改。
- 所以CopyOnWrite容器是一种读写分离的思想，读和写不同的容器。
- 保证数据的最终一致性，对数据一致性没有严格要求；同时进行读写操作，到底读在前，还是写操作在前，无法保证；
- 适合用于读多写少的情况；因为每次插入add操作都会临时创建一个新的容器对象，如果用在写多读少的情况，链表的长度太长，最后会导致频繁的Full GC；
再补充一点HashSet和CopyOnWriteHashSet
HashSet
线程不安全，无序；
public class ContainerNotSafeDemo {
public static void main(String[] args) {
setNoSafe();
}
private static void setNoSafe() {
Set<String> set=new HashSet<>();
for (int i = 1; i <= 30; i++) {
new Thread(() -> {
set.add(UUID.randomUUID().toString().substring(0, 8));
System.out.println(Thread.currentThread().getName() + "\t" + set);
}, String.valueOf(i)).start();
}
}
}
程序运行结果：
java.util.ConcurrentModificationException
HashSet构造方法
HashSet 的构造器：底层维护了一个负载因子为 0.75 的 HashMap
创建HashSet底层创建一个HashMap():其初始容量为16，负载因子为0.75；
private transient HashMap<E,Object> map;
private static final Object PRESENT = new Object();
public HashSet() {
map = new HashMap<>();
}
add(E e)
实际就是往HashMap中添加数据，value为对象的地址；
private static final Object PRESENT = new Object();
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
解决方法
解决 HashSet 线程不安全问题的方法：
1）Collections.synchronizedSet(new HashSet());
方法将 HashSet 转为线程安全版本
2)使用 CopyOnWriteArraySet 类：读写分离
CopyOnWriteArraySet
public static void safe(){
Set copyOnWriteArraySet=new CopyOnWriteArraySet();
for (int i=1;i<=10;i++){
final int index=i;
new Thread(new Runnable(){
@Override
public void run() {
for (int j=0;j<5;j++){
copyOnWriteArraySet.add(UUID.randomUUID().toString().substring(0,4));
System.out.println(copyOnWriteArraySet);
}
}
},String.valueOf(index)).start();
}
}
构造方法
CopyOnWriteArraySet 内部维护了一个 CopyOnWriteArrayList 实例，典型的挂羊皮卖狗肉
public class CopyOnWriteArraySet<E> extends AbstractSet<E>
implements java.io.Serializable {
private final CopyOnWriteArrayList<E> al;
public CopyOnWriteArraySet() {
al = new CopyOnWriteArrayList<E>();
}
add(E e)
调copyOnWriteArrayList.addIfAbsent()方法
public boolean add(E e) {
return al.addIfAbsent(e);
}
contains(Object o)
判断容器中是否包含了o对象；
public boolean contains(Object o) {
return al.contains(o);
}
原文链接:https://blog.csdn.net/yaoyaochengxian/article/details/117674813
所属网站分类: 技术文章 > 博客
作者：以天使的名义
链接：http://www.javaheidong.com/blog/article/222554/8126d29a8c89e31d90b6/
来源：java黑洞网
任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任
15
0
收藏该文
昵称:
评论内容：(最多支持255个字符)
---无人问津也好，技不如人也罢，你都要试着安静下来，去做自己该做的事，而不是让内心的烦躁、焦虑，坏掉你本来就不多的热情和定力
程序员的那些事(new)
更多>
电子书(new)
博客(new)
视频教程(new)
问答(new)
游戏(new)
其他资源(new)