转载

jdk1.8集合源码分析系列-4-Vector和Stack

为什么要把vector和stack一起来分析，因为在jdk容器的源码来说，stack是继承vector，并且代码也比较少，所以vector和stack一起来看一下。

接口继承图

在分析vector之前，我们先来看下vector的接口继承图：

看到这个图是不是非常熟悉，和之前分析的arraylist一模一样。arraylist的接口继承图如下：

那具体的接口分析我们就不用做了，看之前ArrayList的分析就可以了。

Vector源码分析

vector数据结构

public class Vector<E>
    extends AbstractList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
   
    //存放元素的数组
    protected Object[] elementData;

    //vector的长度，这里并没有叫size，但是和size功能是一样的
    //可以看到size方法返回的就是这个值
    protected int elementCount;
    
    //size方法
    public synchronized int size() {
        return elementCount;
    }
    
    //如果想指定动态扩容时，扩容多少size，那么就设置这个值。
    protected int capacityIncrement;
}
复制代码

初始化逻辑

//构造方法暴露了两个参数，一个是初始容量，一个是动态扩容容量参数
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，它会走默认的扩容逻辑。
public Vector(int initialCapacity) {
    this(initialCapacity, 0);
}

//如果初始化容量都不指定，那么初始化容量默认为10
public Vector() {
    this(10);
}
复制代码

add和remove方法分析

这里我们就分析一下add和remove方法，其他方法都比较简单，但是这里需要提的一点是，vector对父类所有的提供的方法全部加了synchronized关键字，这个关键字能够保证并发安全的，也就是常说的保证可见性，保证原子性，禁止指令重排序。但是由于这么做，vector的性能也是不如ArrayList的，由于锁粒度比较粗，实际业务中使用的非常少。

public synchronized boolean add(E e) {
    // 结构性修改次数增加，为了实现fast-fail的机制
    modCount++;
    // 确认容量是否达到上限，如果达到则需要扩容
    ensureCapacityHelper(elementCount + 1);
    // 把元素加到最后一位
    elementData[elementCount++] = e;
    return true;
}

public synchronized E remove(int index) {
    // 结构性修改次数增加，为了实现fast-fail的机制
    modCount++;
    // 边界检查
    if (index >= elementCount)
        throw new ArrayIndexOutOfBoundsException(index);
        
    // 获取即将remove的value用于结果返回
    E oldValue = elementData(index);

    // 计算需要数字移动次数，为什么要计算这个，arraylist分析中介绍了线性表的删除过程。
    int numMoved = elementCount - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    // 把最后一个index位置的值删除
    elementData[--elementCount] = null; // Let gc do its work

    return oldValue;
}
复制代码

扩容方法分析

// add方法
public synchronized boolean add(E e) {
    modCount++;
    ensureCapacityHelper(elementCount + 1);
    elementData[elementCount++] = e;
    return true;
}

// 确认容量是否达到上限
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;
    
    // 如果设置了动态扩容size，每次扩容都按照capacityIncrement来扩容。
    // 否则按照容量 * 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的代码并不复杂，我们就介绍到这里了。下面我们看一下Stack的源码，看源码之前，我们必须要了解一下数据结构-堆栈。

数据结构-堆栈

堆栈是一个先进后出的队列，堆栈最常见的操作就是两个，一个pop出栈操作，一个push入栈操作。

Stack源码

由于stack是继承Vector的，所以我们只需要看下它新增的接口部分，总共才5个方法：

push 入栈操作，把元素压到栈的顶部
pop 出栈操作，把栈顶元素删除。
peek 取出栈顶元素但是不删除。
empty 判断是否栈为空
search 在堆栈中搜索指定元素

扩容策略和出入栈代码分析

// 没有调用Vector的构造器，完全创造一个空栈
public Stack() {
}

// push的时候，容量会自动 + 1
public E push(E item) {
    addElement(item);

    return item;
}

// 添加容量的具体逻辑在这里。
public synchronized void addElement(E obj) {
    modCount++;
    //每次add增加1的容量
    ensureCapacityHelper(elementCount + 1);
    elementData[elementCount++] = obj;
}

// pop方法类似，取出栈顶元素后，容量自动减1
public synchronized E pop() {
    E       obj;
    int     len = size();

    obj = peek();
    //容量自动减1
    removeElementAt(len - 1);
    return obj;
}
复制代码

Stack源码非常简单，就分析到这里了。

原文 https://juejin.im/post/5f0a8afd5188252e98364bc2

正文到此结束