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;

returntrue;

}

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;

returntrue;

}

// 确认容量是否达到上限

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源码非常简单,就分析到这里了。

以上是 jdk1.8集合源码分析系列-4-Vector和Stack 的全部内容, 来源链接: utcz.com/a/31813.html

回到顶部