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/

本站部分文章源于互联网,本着传播知识、有益学习和研究的目的进行的转载,为网友免费提供。如有著作权人或出版方提出异议,本站将立即删除。如果您对文章转载有任何疑问请告之我们,以便我们及时纠正。

PS:推荐一个微信公众号: askHarries 或者qq群:474807195,里面会分享一些资深架构师录制的视频录像:有Spring,MyBatis,Netty源码分析,高并发、高性能、分布式、微服务架构的原理,JVM性能优化这些成为架构师必备的知识体系。还能领取免费的学习资源,目前受益良多

转载请注明原文出处:Harries Blog™ » Vector 底层实现原理分析

赞 (0)
分享到:更多 ()

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址