转载

Vector 底层实现原理分析

Vector ，一个可变长的数组，底层实现与ArrayList 大同小异，但 Vector 是同步的（线程安全）， Vector 的很多方法之前都加了关键字 synchronized ，所以是线程安全的。

由于Vector的实现和ArrayList的实现大同小异，这里就不再逐一分析Vector中的方法，主要分析一下和ArrayList不同的方法。

首先我们还是来看以下Vector中定义的变量

public class Vector<E>
    extends AbstractList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    protected Object[] elementData;      // 存储Vector中元素
 
    protected int elementCount;          // Vector中的元素个数
    protected int capacityIncrement;     // Vector的增长系数
    private static final long serialVersionUID = -2767605614048989439L;     // Vector的序列版本号  
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;       // 能够分配元素数量的最大值
}

构造方法

Vector 有四个构造方法，其内部有两个重要的参数，一个是 elementCount 代表当前元素个数，一个是 capacityIncrement 代表当列表元素满了之后增加的容量。如果不设置 capacityIncrement ，那么 Vector 容量扩展时默认将扩展两倍，在ArrayList源码分析中，我们可以知道 ArrayList 在扩容时默认将扩展1.5倍。

ector 初始时容量为 10 ，而 ArrayList 初始容量为 0 。

// Vector构造函数。默认容量是10。    
public Vector() {    
    this(10);    
}    
// 指定Vector容量大小的构造函数    
public Vector(int initialCapacity) {    
    this(initialCapacity, 0);    
}    
// 指定Vector"容量大小"和"增长系数"的构造函数    
public Vector(int initialCapacity, int capacityIncrement) {    
    super();    
    if (initialCapacity < 0)    
        throw new IllegalArgumentException("Illegal Capacity: "+    
                                           initialCapacity);    
    // 新建一个数组，数组容量是initialCapacity    
    this.elementData = new Object[initialCapacity];    
    // 设置容量增长系数    
    this.capacityIncrement = capacityIncrement;    
}    
// 指定集合的Vector构造函数。    
public Vector(Collection<? extends E> c) {    
    // 获取“集合(c)”的数组，并将其赋值给elementData    
    elementData = c.toArray();    
    // 设置数组长度    
    elementCount = elementData.length;    
    // c.toArray might (incorrectly) not return Object[] (see 6260652)    
    if (elementData.getClass() != Object[].class)    
        elementData = Arrays.copyOf(elementData, elementCount, Object[].class);    
}

Vector 中的构造器和 ArrayList 中的基本相同，只不过 Vector 中多了一个可以自定义增长系数的构造器 public Vector(int initialCapacity, int capacityIncrement)

扩容机制

Vector 中的添加元素和 ArrayList 中的大同小异，这里不再具体分析，这里只分析下Vector的扩容机制

/**
 * 增加vector容量
 * 如果vector当前容量小于至少需要的容量，它的容量将增加。
 * 新的容量将在旧的容量的基础上加上capacityIncrement，除非capacityIncrement小于等于0，在这种情况下，容量将会增加一倍。
 * 增加后，如果新的容量还是小于至少需要的容量，那就将容量扩容至至少需要的容量。
 */
public synchronized void ensureCapacity(int minCapacity) {
    if (minCapacity > 0) {
        modCount++;
        ensureCapacityHelper(minCapacity);
    }
}
/**
 * ensureCapacity()方法的unsynchronized实现。
 * ensureCapacity()是同步的，它可以调用本方法来扩容，而不用承受同步带来的消耗
 */
private void ensureCapacityHelper(int minCapacity) {
    // 如果至少需要的容量 > 数组缓冲区当前的长度，就进行扩容
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}
/**
 * 分派给arrays的最大容量
 * 为什么要减去8呢？
 * 因为某些VM会在数组中保留一些头字，尝试分配这个最大存储容量，可能会导致array容量大于VM的limit，最终导致OutOfMemoryError。
 */
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
/**
* 扩容，保证vector至少能存储minCapacity个元素。
* 首次扩容时，newCapacity = oldCapacity + ((capacityIncrement > 0) ?capacityIncrement : oldCapacity);即如果capacityIncrement>0，就加capacityIncrement，如果不是就增加一倍。
* 如果第一次扩容后，容量还是小于minCapacity，就直接将容量增为minCapacity。
*/
private void grow(int minCapacity) {
    // 获取当前数组的容量
    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();
    //如果想要的容量大于MAX_ARRAY_SIZE，则分配Integer.MAX_VALUE，否则分配MAX_ARRAY_SIZE
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

其他方法

Vector 中添加一个枚举方法

// 返回一个枚举类型的对象
public Enumeration<E> elements() {
    return new Enumeration<E>() {
        int count = 0;
        public boolean hasMoreElements() {    // 判断后面是否还有数据
            return count < elementCount;
        }
        public E nextElement() {       // 返回一个数据
            synchronized (Vector.this) {
                if (count < elementCount) {
                    return elementData(count++);
                }
            }
            throw new NoSuchElementException("Vector Enumeration");
        }
    };
}

其他类同方法请参考ArrayList源码分析

Vector 与 ArrayList 的最大区别就是 Vector 是线程安全的，而 ArrayList 不是线程安全的。另外区别还有：

ArrayList 不可以设置扩展的容量，默认 1.5 倍； Vector 可以设置扩展的容量，如果没有设置，默认 2 倍
ArrayList 的无参构造方法中初始容量为 0 ，而 Vector 的无参构造方法中初始容量为 10 。

下面我们再来分析下Vector的子类Stack方法。

Stack

Stack类代表最先进先出（LIFO）堆栈的对象。它扩展了Vector五个操作，允许一个vector被视为堆栈。

五个方法分别是：

push() 添加元素到堆栈的顶部
pop() 删除堆栈顶部元素
peek() 查看堆栈顶部元素
empty() 判断堆栈是否为空
search() 返回元素所在位置

package java.util;
public
class Stack<E> extends Vector<E> {
    /**
     * Creates an empty Stack.
     */
    public Stack() {
    }
    public E push(E item) {
        addElement(item);
        // 调用vector中的方法在栈顶添加一个元素
        return item;
    }
    public synchronized E pop() {
        E       obj;
        int     len = size();
        obj = peek();
        removeElementAt(len - 1);
        // 调用vector中的方法删除栈顶的元素
        return obj;
    }
    public synchronized E peek() {
        int     len = size();
        // 返回栈顶元素
        if (len == 0)
            throw new EmptyStackException();
        return elementAt(len - 1);
    }
    public boolean empty() {
        return size() == 0;
    }
    public synchronized int search(Object o) {
        int i = lastIndexOf(o);
        // 因为LIFO  所以选择从后往前遍历
        if (i >= 0) {
            return size() - i;
        }
        return -1;
    }
    /** use serialVersionUID from JDK 1.0.2 for interoperability */
    private static final long serialVersionUID = 1224463164541339165L;
}

原文 https://gyl-coder.top/java/collection/Vector/

正文到此结束