本站消息

站长简介/公众号


站长简介:逗比程序员,理工宅男,前每日优鲜python全栈开发工程师,利用周末时间开发出本站,欢迎关注我的微信公众号:幽默盒子,一个专注于搞笑,分享快乐的公众号

  价值13000svip视频教程,java大神匠心打造,零基础java开发工程师视频教程全套,基础+进阶+项目实战,包含课件和源码

  出租广告位,需要合作请联系站长


+关注
已关注

分类  

暂无分类

标签  

暂无标签

日期归档  

2021-05(23)

2021-06(50)

2021-07(18)

一文必懂-深入理解ArrayList与CopyOnWriteList源码

发布于2021-06-12 16:18     阅读(31)     评论(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线程不安全的方法

  1. 使用new Vector<>();
  2. 使用Collections.synchronizedList(new ArrayList<>());转换成线程安全类
  3. 使用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();
        }
    }

特点:

  1. 写时复制:CopyOnWrite容器,即写时复制一个新的容器
  2. 往容器中添加元素时,不直接往当前容器中Object[]添加,而是先将当前Object[]进行复制,复制出一个新的容器Object[] new Elements,然后新的容器Object[] newElments里面添加元素,添加完后,再将原容器的引用指向新的容器setArray(new Elements);—>旧容器会被垃圾回收掉
  3. 这样做的好处是可以对CopyOnWrite容器进行并发的读,而不需要加锁,因为当前容器不会修改任何修改。
  4. 所以CopyOnWrite容器是一种读写分离的思想,读和写不同的容器。
  5. 保证数据的最终一致性,对数据一致性没有严格要求;同时进行读写操作,到底读在前,还是写操作在前,无法保证;
  6. 适合用于读多写少的情况;因为每次插入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个字符)