Vector源码阅读

Posted1 by 呼延十 on December 23, 2018 Hot:

前言

前面已经学习过ArrayList和LinkedList的区别,今天再来学习一下List<E>接口的另一个实现类Vector.

Vector 可以实现可增长的对象数组。与数组一样,它包含可以使用整数索引进行访问的组件。不过,Vector 的大小是可以增加或者减小的,以便适应创建 Vector 后进行添加或者删除操作。

Vector与ArrayList没有太大区别,都具有List<E>的基础功能,重要的是:Vector是同步的.也就是说,Vector可以用于多线程环境下,但是性能相比Arraylist要低一些.

源码阅读

定义

首先看一下Vector类的定义.

public class Vector<E>
    extends AbstractList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{}

Vector 实现 List 接口,继承 AbstractList 类,所以我们可以将其看做列表,支持相关的添加、删除、修改、遍历等功能。

Vector 实现 RandomAccess 接口,即提供了随机访问功能,提供快速访问功能。在 Vector 我们可以直接访问元素。

Vector 实现了 Cloneable 接口,支持 clone() 方法,可以被克隆。

成员变量

protected Object[] elementData;

protected int elementCount;

protected int capacityIncrement;

elementData是保存数据的数组

elementCount是当前元素的数量

capacityIncrement是容量增量,当它小于或者等于0时,则每次需要增大容量时,向量的容量将增大一倍.

构造方法


    public Vector(int initialCapacity, int capacityIncrement) {

    }

    public Vector(int initialCapacity) {
    }


    public Vector() {
    }

    public Vector(Collection<? extends E> c) {

    }

Vector有四个构造方法,参数分别制定初始容量及初始增量.

默认的构造方法,初始容量为10,初始增量为0,即每次扩容时容量翻倍.

常用方法

###1.添加元素

/**
* 数组末尾添加一个元素
*/
public synchronized boolean add(E e) {
    modCount++;
    ensureCapacityHelper(elementCount + 1);
    elementData[elementCount++] = e;
    return true;
}
/**
* 设置某个index上的元素为传入值
*/
public synchronized E set(int index, E element) {
    if (index >= elementCount)
        throw new ArrayIndexOutOfBoundsException(index);

    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}
/**
* 在指定的index插入一个元素,后续元素向后顺移
*/
public void add(int index, E element) {
    insertElementAt(element, index);
}
public synchronized void insertElementAt(E obj, int index) {
    modCount++;
    if (index > elementCount) {
        throw new ArrayIndexOutOfBoundsException(index
                                                 + " > " + elementCount);
    }
    ensureCapacityHelper(elementCount + 1);
    System.arraycopy(elementData, index, elementData, index + 1, elementCount - index);
    elementData[index] = obj;
    elementCount++;
}

###2.获取元素

public synchronized E get(int index) {
    if (index >= elementCount)
        throw new ArrayIndexOutOfBoundsException(index);

    return elementData(index);
}

###3.移除元素

public boolean remove(Object o) {
    return removeElement(o);
}
public synchronized boolean removeElement(Object obj) {
    modCount++;
    int i = indexOf(obj);
    if (i >= 0) {
        removeElementAt(i);
        return true;
    }
    return false;
}

由于Vector内部使用数组实现,因此简单的增加删除获取元素都是对数组的简单操作,这里就不细讲了.

扩容

既然Vector是一个可以动态改变自己大小的数组,那么我们来看一下他是怎么实现动态扩容的.

public synchronized void ensureCapacity(int minCapacity) {
    if (minCapacity > 0) {
        modCount++;
        ensureCapacityHelper(minCapacity);
    }
}

private void ensureCapacityHelper(int minCapacity) {
    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    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);
}

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

这是和扩容相关的几个方法,前两个方法是用来检验当前是否需要扩容.

在添加元素时,会用当前数组中元素的个数+1进行检验,如当前个数+1 > 数组长度,则需要扩容,调用grow方法.

grow方法中:

  1. 旧的大小为当前数组长度
  2. 计算扩容后的大小,(oldCapacity+capacity/oldCapacity)
  3. 判断扩容后的size是否合法
  4. 调用Arrays.copy将当前所有值copy到新的数组.

后话

由于Vector内部使用数组实现,因此源码并不复杂.

同时,在学习源码的过程中我们可以发现,很多对数组进行操作的方法使用synchronized修饰,因此可以保证线程安全性,同时,synchronized会加锁,因此效率可能会相对于ArrayList低一些,在单线程的情况下建议还是使用ArrayList.

参考链接

http://wiki.jikexueyuan.com/project/java-enhancement/java-twentynine.html

完。





ChangeLog

2018-12-23 完成

以上皆为个人所思所得,如有错误欢迎评论区指正。

欢迎转载,烦请署名并保留原文链接。

联系邮箱:huyanshi2580@gmail.com

更多学习笔记见个人博客——>呼延十