本人花费半年的时间总结的《Java面试指南》已拿腾讯等大厂offer，已开源在github ，欢迎star！
原文链接：blog.ouyangsihai.cn >> 菜鸡看不一样的Java集合源码-Vector源码分析
0 开篇
这篇文章应该是集合源码分析的开篇了，先从Vector开始主要是因为根据数据结构的顺序来的，大家也应该都知道，这也是集合中最简单的一种数据结构的实现了，因为Vetor的实现就是基于数组的，所以，对于大家都不陌生，从开始学习编程开始，最开始接触的应该就是数据这种最最简单的数据结构了。
因此，带着这种好奇心，看看最简单的数据结构，在Java的底层是怎么实现的呢？
1 问题
在开始之前， 我们可以想想几个关于数组的问题，看看Java是怎么解决的？
- 数组怎么实现的复制？
- 数组怎么实现的扩容？
这两个问题应该是在数组中经常都会遇到的，我们就带着这两个问题看看Java底层的实现。
2 菜菜源码分析
2.1 声明和属性
首先，我们看看Vetor这个类的声明，你可以先想想你理解的应该是怎么样的，是否跟Java底层的实现一样呢？
public class Vector<E>
extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
从这里可以发现，Vector集成自AbstractList，同时实现了List<E>, RandomAccess, Cloneable, java.io.Serializable这几个接口，同时，Vector也是用泛型来声明的。
我们看一下Vector的类图结构就更加的清楚了。
2.2 构造方法
public Vector(int initialCapacity, int capacityIncrement) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
this.capacityIncrement = capacityIncrement;
}
public Vector(int initialCapacity) {
this(initialCapacity, 0);
}
public Vector() {
this(10);
}
public Vector(Collection<? extends E> c) {
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，也可以传入带有初始大小的Vector，或者直接从其他集合复制数据到Vetor生成。
2.3 扩容
在看其他方法之前，我们先看看扩容机制，因为其他的很多方法都需要用到这个机制。
首先传入最小的容量，调用下面的方法；
public synchronized void ensureCapacity(int minCapacity) {
if (minCapacity > 0) {
modCount++;
ensureCapacityHelper(minCapacity);
}
}
接着调用下面的方法判断传入的扩容容量是否比目前的Vetor容量大，如果更大，使用grow方法扩容；
private void ensureCapacityHelper(int minCapacity) {
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
capacityIncrement字段是在创建Vetor对象的时候可以选择传入，表示扩容增加的容量，这里的扩容方法是：如果capacityIncrement大于0，就增加这个容量，否则，加上原来Vector的容量；
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
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;
}
扩容机制知道了之后，我们就可以看其他的方法了。
2.4 添加元素
public synchronized void addElement(E obj) {
//修改次数增加
modCount++;
//扩容
ensureCapacityHelper(elementCount + 1);
//添加元素
elementData[elementCount++] = obj;
}
- 添加元素到指定位置
public synchronized void insertElementAt(E obj, int index) {
modCount++;
if (index > elementCount) {
throw new ArrayIndexOutOfBoundsException(index
+ " > " + elementCount);
}
//扩容
ensureCapacityHelper(elementCount + 1);
//复制：将elementData中的数据从index位置开始复制到elementData中去，位置是index + elementCount - index，所以正好腾出index位置插入元素
System.arraycopy(elementData, index, elementData, index + 1, elementCount - index);
//插入元素
elementData[index] = obj;
elementCount++;
}
System.arraycopy方法在这里解释一下。
方法原型是这样的；
public static native void arraycopy(Object src, int srcPos,
Object dest, int destPos,
int length);
这是一个native方法，作用：将原数组src从srcPos位置开始复制length长度的元素复制到dest目标数组的destPos位置开始的数组中，感觉有点绕口，举一个简单的例子。
System.arraycopy(users, 0, target, 0, users.length);/
这个意思是：将users中的0位置开始元素复制到target中，复制的长度为users.length。
2.5 删除指定位置元素
public synchronized void removeElementAt(int index) {
modCount++;
if (index >= elementCount) {
throw new ArrayIndexOutOfBoundsException(index + " >= " +
elementCount);
}
else if (index < 0) {
throw new ArrayIndexOutOfBoundsException(index);
}
int j = elementCount - index - 1;
if (j > 0) {
//将原数组中的index + 1位置开始的元素复制到目标elementData中的index位置，长度为：j = elementCount - index - 1，说白了就是删除index位置的元素。
System.arraycopy(elementData, index + 1, elementData, index, j);
}
//数量减一，引用指向null，gc掉
elementCount--;
elementData[elementCount] = null; /* to let gc do its work */
}
知道这个方法之后，你就会发现，其他的删除的方法都是基于这个方法，所以这里就不再做介绍了。
2.6 查找元素
//从index位置开始查找元素
public synchronized int indexOf(Object o, int index) {
//如果元素为空，找到从index位置开始的第一个为null的元素的索引返回，如果不为空，找到第一个相等的元素的索引返回。
if (o == null) {
for (int i = index ; i < elementCount ; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = index ; i < elementCount ; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
知道这个方法之后，你就会发现，其他的查找的方法都是基于这个方法，所以这里就不再做介绍了。
3 小结
这里总结回到一下开篇的问题。
数组怎么实现的复制？
基本都是使用System.arraycopy方法实现。数组怎么实现的扩容？
如果capacityIncrement大于0，就增加这个容量，否则，加上原来Vector的容量。
4 Stack类简介
Stack是数据结构栈的实现的，因为是基于数组实现的，所以，在Java的集合中就是集成自Vetor类的，所以，Stack的实现就非常的简单了。
Stack类图
Stack类的方法
所以，下面我们简单的看一下这几个方法的实现。
Stack源码解析
- push方法
public E push(E item) {
addElement(item);
return item;
}
addElement方法继承自Vector类，这里就不再讲了。
- peek方法
```java
public synchronized E peek() {
int len = size();
if (len == 0)
throw new EmptyStackException();
return elementAt(len - 1);
}
- pop方法
```java
public synchronized E pop() {
E obj;
int len = size();
obj = peek();
removeElementAt(len - 1);
return obj;
}
removeElementAt方法集成自Vector类，上面已经讲过了。
stack比较简单，这里就将这么多！
