Java集合源码:(三) 线程安全 List 分析(JDK8)

集合整体架构文章:

罗政:JAVA 集合整体架构


就List而言,据我所知线程安全的几个类为 Vector ,SynchronizedList , CopyOnWriteArrayList, 下面一一讲解下底层实现。

Vector 源码

重要成员

// 底层数组元素
protected Object[] elementData;
// 数组存储的元素大小
protected int elementCount;
// 扩容的大小,默认为0:扩容原来的一倍, 大于0的话扩容capacityIncrement
protected int capacityIncrement;
// 在父类 AbstractList里面,记录修改次数
 protected transient int modCount = 0;

构造函数

    public Vector() {
        this(10);
    }
    public Vector(int initialCapacity) {
        this(initialCapacity, 0);
    }
    public Vector(int initialCapacity, int capacityIncrement) {
        this.elementData = new Object[initialCapacity]; // 10 
        this.capacityIncrement = capacityIncrement;  // 0
    }

构造了一个Object[10] 空数组,虽然是空数组,但是会占空间的,占的具体内存大小请见我这篇文章的分析

new Object[1] 到底占用多少字节内存


add方法

    public synchronized boolean add(E e) {
        modCount++;
        ensureCapacityHelper(elementCount + 1);// 当前大小 + 1
        elementData[elementCount++] = e; // 把add的值set进数组
        return true;
    }
    private void ensureCapacityHelper(int minCapacity) {
        // 当前元素 + 1  大于了 数组的容量 => 代表存不下
        if (minCapacity - elementData.length > 0)
            grow(minCapacity); //扩容
    }
    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        // capacityIncrement 初始化为0了,所以扩容 oldCapacity
        int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                         capacityIncrement : oldCapacity);
        if (newCapacity - minCapacity < 0)// 确保扩容后能存的下
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0) // 判断minCapacity是否int溢出
            newCapacity = hugeCapacity(minCapacity);
        elementData = Arrays.copyOf(elementData, newCapacity);// System.arraycopy 底层拷贝
    }

方法加锁 synchronized ,效率极差。

add三步曲

  • 修改次数加加。
  • 判断扩容。当前要存的元素大小大于了容量要扩容,扩容根据capacityIncrement值来扩,capacityIncrement<=0时,扩大原来的一倍,否则扩大capacityIncrement。capacityIncrement可以在构造函数中传入。
  • 把add的具体值set到数组后面,然后当前元素个数标识elementCount 加加,完成add操作。

扩容时的数组拷贝底层jvm实现请看我这篇文章

Java集合:(一) ArrayList源码解析(JDK8)

get(int index) 源码解析

    public synchronized E get(int index) {
        if (index >= elementCount)  // 不能越界
            throw new ArrayIndexOutOfBoundsException(index);

        return elementData(index);  // 直接返回数组下标元素  复杂度O1
    }
    @SuppressWarnings("unchecked")
    E elementData(int index) {
        return (E) elementData[index];
    }

get很简单,但是为了线程安全加了方法锁, 也就是当一个线程ge时,其它线程也无法get或者 add 这个vector,你说效率差不差。


vector总结

vector其实已经是过时的类,也就是被jdk抛弃的类,我们不应该使用它。vector所有get()、set()方法都是synchronized,没有对同步进行细粒度控制,导致当多线程产生竞争vector时,效率极差。


SynchronizedList 源码

SynchronizedList是Collections工具类的内部类,我们无法直接构造,要这样:

public static void main(String[] args) throws IOException {
	List<Object> list = Collections.synchronizedList(new ArrayList<>());
}
public static <T> List<T> synchronizedList(List<T> list) {
        return (list instanceof RandomAccess ?
                new SynchronizedRandomAccessList<>(list) :
                new SynchronizedList<>(list));
}

SynchronizedList就是一个包装器,包装了线程不安全的list,包装后实现了线程安全功能。

SynchronizedList 几个重要成员变量:

 final List<E> list;
 final Collection<E> c; 
 final Object mutex;     // 锁监视器对象

构造函数

 SynchronizedList(List<E> list) {
            this.c = Objects.requireNonNull(c);
            mutex = this; // 锁监视器  就是 本身this
            this.list = 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);}
        }

CopyOnWriteArrayList源码

CopyOnWriteArrayList是线程安全list最佳使用对象,下面来看下底层源码实现。

几个重要成员

// lock锁 
final transient ReentrantLock lock = new ReentrantLock();
// 元素数组 注意是 volatile , 保证多线程看到的是主内存的array,数据一致
private transient volatile Object[] array;

构造函数

    public CopyOnWriteArrayList() {
        setArray(new Object[0]);
    }
    final void setArray(Object[] a) {
        array = a;
    }

构造了一个Object[0]数组。 没得啥将的。

add源码

    public boolean add(E e) {
        final ReentrantLock lock = this.lock;
        lock.lock(); // jvm应用层实现的lock
        try {
            Object[] elements = getArray();// 获取元素数组
            int len = elements.length;
            // 拷贝数组 ,大小扩为原来的大小 + 1
            Object[] newElements = Arrays.copyOf(elements, len + 1);
            newElements[len] = e; // 设置到数组尾部
            // 替换 到 全局的 array 
            setArray(newElements);
            return true;
        } finally {
            lock.unlock();
        }
    }

我们发现跟Arraylist的设计不同,Arraylist扩容都是将容量扩大原来的二分之一,CopyOnWriteArrayList 的容量就是数组存的元素大小。所以每次add时,都会涉及到数组拷贝,所以CopyOnWriteArrayList 应该用到读多写少场景。

额外说一句,lock底层实现请见:

AQS (1) ReentrantLock 的上锁 与 解锁 源码

get(int index) 源码

    public E get(int index) {
        return get(getArray(), index);
    }
    private E get(Object[] a, int index) {
        return (E) a[index];
    }

get没有加锁,就是普通的O1复杂度取数组。


总结CopyOnWriteArrayList

  • CopyOnWriteArrayList没有复杂的扩容操作,add数据时都是重新copy一个数组,将元素添加到copy数组的末尾(扩容一个位置),最后将copy数组赋值给全局的array变量。所以: add效率极差,而且内存开销翻倍
  • CopyOnWriteArrayList线程安全都是通过 ReentrantLock 锁来实现的,get查询操作是无锁实现。适合读多写少场景。
  • CopyOnWriteArrayList本质就是读写分离的思想,如果有线程修改时,另外线程读取都是读取的老数据。CopyOnWriteArrayListCopyOnWriteArrayList只能保证弱一致性。

为什么CopyOnWriteArrayList扩容不像ArrayList预扩大1.5倍,而是一个一个扩?

CopyOnWriteArrayList的add是copy了一份数组,然后将copy的数组的地址给到成员变量array,试想一下,你扩大原来的1.5倍有何意义,每次add都时,原来的数组都被丢弃了,不是浪费空间吗。


强烈推荐一个 进阶 JAVA架构师 的博客

Java架构师修炼

支付宝打赏 微信打赏

如果文章对您有帮助,您可以鼓励一下作者