ArrayList与Vector

Vector作为JDK1.0开始就已经存在的元老级数据结构,在JDK的版本升级过程中可谓是修修补补,与JAVA1.2中新增的ArrayList这个后起之秀相比,Vector就显得有点赘余了。但是对于新手来说就很有可能将这两个类混淆使用,这里对这两个类进行区别(主要体现在扩容策略和线程安全上)。

#相同点

  1. 都使用数组实现,提供的操作也基本一致
    在ArrayList与Vector中都有一个Object[] elementData用来保存数据
    看看它们的方法:
    ArrayListVector
  2. 都实现了List接口
    对于ArrayList来说List接口仿佛就是为它而设计的,而Vector类完全是为了迎合JAVA1.2中出现的List接口而去实现的,这也导致了Vector中的很多方法功能上是重复的。
    1
    2
    3
    4
    5
    6
    7
    8
    boolean add(E e);   -->   void addElement(E obj);
    boolean remove(Object o); --> boolean removeElement(Object obj);
    void clear(); --> void removeAllElements();
    E get(int index); --> E elementAt(int index);
    E set(int index, E element); --> void setElementAt(E obj, int index);
    void add(int index, E element); --> void insertElementAt(E obj, int index);
    E remove(int index); --> void removeElementAt(int index);
    ListIterator<E> listIterator(); --> Enumeration<E> elements();

#不同点

#默认构造对象的初始容量不同

两个类都可以通过构造函数指定初始容量在ArrayList中也是很有讲究的,这个在扩容策略中讲。这里要说的是是无参构造函数函数调用时,创建的数据对象数组不相同。

  1. Vector默认初始容量为10
    1
    2
    3
    public Vector() {
    this(10);
    }
  2. ArrayList默认初始是空数组
    1
    2
    3
    4
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

#扩容策略

扩容策略主要表现grow这个方法上

  1. Vector的扩容策略
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    private void grow(int minCapacity) {
    int oldCapacity = elementData.length;

    // capacityIncrement这个变量在构造Vector对象的时候指定,默认为0
    // 如果指定了capacityIncrement变量,扩容方式就是:
    // newCapacity = oldCapacity + capacityIncrement;
    // 未指定capacityIncrement,扩容方式为:
    // newCapacity = oldCapacity * 2 ;
    int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
    capacityIncrement : oldCapacity);
    if (newCapacity - minCapacity < 0)
    newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
    newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
    }
    Vector可以通过构造方法来指定扩容增量(也可以叫扩容因子)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    public Vector(int initialCapacity, int capacityIncrement) {
    super();
    if (initialCapacity < 0)
    throw new IllegalArgumentException("Illegal Capacity: "+
    initialCapacity);
    this.elementData = new Object[initialCapacity];
    this.capacityIncrement = capacityIncrement;
    }
    // 默认扩容增量为0,也就是说上面的grow方法默认的扩容策略为:
    // newCapacity = oldCapacity * 2 ;
    public Vector(int initialCapacity) {
    this(initialCapacity, 0);
    }
  2. ArrayList的扩容策略
    在讲ArrayList的扩容策略之前,先说说两个常见的场景
  • 场景一
    1
    2
    3
    4
    ArrayList<Integer> list1 = new ArrayList<>();
    list1.add(1);
    list1.add(2);
    list1.add(3);
  • 场景二
    1
    2
    3
    4
    ArrayList<Integer> list2 = new ArrayList<>(0);
    list2.add(1);
    list2.add(2);
    list2.add(3);
    对于上面两种场景,ArrayList数组容量的扩容过程,每一步数组的大小是多少呢。带着这个问题看下面的代码可能效果会更好。
    首先来看看扩容的有效代码:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    private void grow(int minCapacity) {
    int oldCapacity = elementData.length;

    // ArrayList的扩容策略:newCapacity = oldCapacity * 3/2
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
    newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
    newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
    }
    但是对于初始容量为0的ArrayList对象来说,怎么办 0 * 3/2 永远都是0。 这就要说道ensureCapacityInternal方法了。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    private void ensureCapacityInternal(int minCapacity) {
    // 当发现初始数组是空数组,会取DEFAULT_CAPACITY和minCapacity之中的最大值,而DEFAULT_CAPACITY为10。
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
    minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    ensureExplicitCapacity(minCapacity);
    }
    private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // 容量不足,需要扩容
    if (minCapacity - elementData.length > 0)
    grow(minCapacity);
    }
    public boolean add(E e) {
    ensureCapacityInternal(size + 1); // 每次都会调用ensureCapacityInternal确保容量足够
    elementData[size++] = e;
    return true;
    }
    这段代码就解释了场景一的扩容过程。
    1
    2
    3
    4
    // 创建对象的时候,数组是DEFAULTCAPACITY_EMPTY_ELEMENTDATA
    ArrayList<Integer> list = new ArrayLis<>();
    list.add(1); // 添加第一个元素的时候会取10作为最小容量,从而数组容量直接从0跳到10
    list.add(2); // 添加第二个元素,容量足够,无需扩容,数组容量仍是10
    对于场景二的构造方法直接指定初始容量的构造方法
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
     public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
    this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
    // 这里的EMPTY_ELEMENTDATA也是空数组,
    // 但是和DEFAULTCAPACITY_EMPTY_ELEMENTDATA不是一个对象
    this.elementData = EMPTY_ELEMENTDATA;
    } else {
    throw new IllegalArgumentException("Illegal Capacity: "+
    initialCapacity);
    }
    }
  • *注意EMPTY_ELEMENTDATA和DEFAULTCAPACITY_EMPTY_ELEMENTDATA虽然都是空数组,但是并不是同一个对象**
    现在场景二就好理解了
    1
    2
    3
    4
    5
    6
    7
    // 这时创建对象,指定的数组是EMPTY_ELEMENTDATA这个空数组
    ArrayList<Integer> list2 = new ArrayList<>(0); // 容量为0
    list2.add(1); // 因为0*3/2 < 0+1 ,所以此时容量为1
    list2.add(2); // 1*3/2 < 1+1 ,所以此时容量为2
    list2.add(3); // 2*3/2 = 3 ,所以此时容量为3
    list2.add(4); // 3*3/2 = 4 ,此时容量为4
    list2.add(5); // 4*3/2 = 6 > 5 ,此时容量为6

    #Vector线程安全,ArrayList线程不安全

    Vector的大部分方法都是线程同步的,相应的Vector的效率也就不如ArrayList,因此Vector更适合多线程的应用场景;ArrayList线程不安全,多个线程同时操作可能会出现问题,在单线程的情况下效率会比Vector更高,在多线程情况下可以使用Collections.synchronizedList方法进行包装,从而达到线程安全的目的。

本作品采用 知识共享署名 4.0 国际许可协议 进行许可。

转载时请注明原文链接:https://blog.hufeifei.cn/2017/04/Java/ArrayList-Vector/

鼓励一下
支付宝微信