写点什么

源码分析 Vector 和 ArrayList

用户头像
张sir
关注
发布于: 2020 年 04 月 30 日

源码分析 Vector 和 ArrayList


每次我们会被问到这个问题,我们都知道 Vector 是线程安全的,而 ArrayList 是线程不安全的。今天想引申出几个问题。


  1. Vector 和 ArrayList 还有什么不同

  2. Vector 容器是如何实现线程安全的

  3. 如果在多线程环境下,有没有别的 List 容器推荐,分别使用在什么场景?


首先回答第一个问题 Vector 和 ArrayList 还有什么不同?


上图我们可以看到,Vetor 和 ArrayList 都继承自 AbstractList,所以大体上对外提供的接口大致相同,只是内部实现不同,底层都是基于数组加上扩容机制实现,除线程安全外 Vetor 和 ArrayList 最大的不同就是扩容方式不同,我们先给出结论,Vector 在扩容时是提高一倍容量,而 ArrayList 是 50%。下面我们可以具体分析一下扩容的源码。

Vector

初始化方法


/*  @param   initialCapacity     内部数组的初始容量,默认为0  @param   capacityIncrement   每次扩容的容量,如果不设置则成倍扩容 /public Vector(int initialCapacity, int capacityIncrement);
/* @param initialCapacity 初始容量 /public Vector(int initialCapacity);
/ 初始化一个 初始容量为10,每次扩容一倍的Vertor容器 */public Vertor();
复制代码


我们从 add(Object o)入手

public synchronized boolean add(E e) {    modCount++;    add(e, elementData, elementCount);    return true;}
复制代码

可以看到 add 方法是加了 synchronized 关键字,这就说明 Vector 的 add()方法在同一时刻只有一个线程能获取到锁,一目了然,Vector 是使用 synchronized 同步机制实现到线程安全,它的每一个对外提供的 api 上都加有 synchronized 关键字。


下面我们看一下 add(e, elementData, elementCount); 这个方法

private void add(E e, Object[] elementData, int s) {    if (s == elementData.length)        elementData = grow();    elementData[s] = e;    elementCount = s + 1;}
复制代码

其中 e 代表添加的元素,elementData 代表内部的数组,s 当前的容量。注意 elementData 数组的长度和 s 不是相同的,比如 Vector 初始化的时候, elementData 的初始化长度是 10,而 s=0。上面我们可以看到,如果当前容量 s = 内部数组的长度以后,就需要调用 grow() 方法获取一个新的 内部数组,扩容的逻辑就在 grow() 方法里面。


下面我们看一下 grow() 方法:

private Object[] grow() {    //elementCount代表内部数组的长度,比如初始化情况下是10。    return grow(elementCount + 1);}
//minCapacity 代表最少生成一个容量为minCapacity的数组private Object[] grow(int minCapacity) { //newCapacity(minCapacity) 方法会生成一个新的数组 return elementData = Arrays.copyOf(elementData, newCapacity(minCapacity));}
复制代码


来了来了,核心扩容逻辑来了 newCapacoty(int minCapacity)

private int newCapacity(int minCapacity) {    //获取当前数组的容量    int oldCapacity = elementData.length;    //获取扩容以后新数组的容量    //注意 capacityIncrement 是初始化 Vector 的时候可以自己设置的,表明每次扩容的大小    //如果没有设置capacityIncrement,我们可以看到 newCapacity = oldCapacity + oldCapacity    //也就是默认两倍扩容    int newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity);    //这里是一个极端的情况,我们都知道int类型都是有范围的,如果超过 2^31-1,就会变成负数,这个时候就说明,newCapacity 已经扩容到最大了,超纲了    if (newCapacity - minCapacity <= 0) {        //数组已满        if (minCapacity < 0) // overflow            throw new OutOfMemoryError();        return minCapacity;    }    //这个地方就是保证数据扩容不超过int范围,如果超过了就不扩容了    //内部数据的容量如果超过了就会OOM    return (newCapacity - MAXARRAYSIZE <= 0)        ? newCapacity        : hugeCapacity(minCapacity);}

private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) // overflow throw new OutOfMemoryError(); return (minCapacity > MAXARRAYSIZE) ? Integer.MAXVALUE : MAXARRAY_SIZE;}
复制代码


ArrayList

构造方法


/*  @param initialCapacity 初始容量,默认为10 */public ArrayList(int initialCapacity)
public ArrayList();
public ArrayList(Collection<? extends E> c);
复制代码


我们也从 add(Object o) 入手

public boolean add(E e) {    modCount++;    add(e, elementData, size);    return true;}
private void add(E e, Object[] elementData, int s) { if (s == elementData.length) elementData = grow(); elementData[s] = e; size = s + 1;}
private Object[] grow() { return grow(size + 1);}
private Object[] grow(int minCapacity) { return elementData = Arrays.copyOf(elementData, newCapacity(minCapacity));}
复制代码

我们可以看到,上面的方法,除了 add(E e) 方法没有 synchronized 关键字,基本都相同。


下面我们看一下 newCapacity(int minCapacity) 这个方法

    private int newCapacity(int minCapacity) {        //当前数组的容量        int oldCapacity = elementData.length;        //新数组的容量        int newCapacity = oldCapacity + (oldCapacity >> 1);        if (newCapacity - minCapacity <= 0) {            //newCapacity 超过2^31-1如何处理            if (elementData == DEFAULTCAPACITYEMPTYELEMENTDATA)                return Math.max(DEFAULTCAPACITY, minCapacity);            if (minCapacity < 0) // overflow                throw new OutOfMemoryError();            return minCapacity;        }        return (newCapacity - MAXARRAYSIZE <= 0)            ? newCapacity            : hugeCapacity(minCapacity);    }
private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) // overflow throw new OutOfMemoryError(); return (minCapacity > MAXARRAYSIZE) ? Integer.MAXVALUE : MAXARRAYSIZE; }
复制代码


ArrayList 线程安全处理

3.1 Collections.synchronizedList(new ArrayList);

3.2 CopyOnWriteArrayList() 容器,基于 ReadWriteLock 锁实现


用户头像

张sir

关注

路漫漫其修远兮 2018.10.09 加入

还未添加个人简介

评论

发布
暂无评论
源码分析 Vector 和 ArrayList