一疤估、簡述
我們知道思灌，數(shù)據(jù)結(jié)構(gòu)中主要有兩種存儲(chǔ)結(jié)構(gòu)骑丸，分別是：順序存儲(chǔ)結(jié)構(gòu)（線性表）舌仍、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（鏈表），在Java中通危，對(duì)這兩種結(jié)構(gòu)分別進(jìn)行實(shí)現(xiàn)的類有：
- 順序存儲(chǔ)結(jié)構(gòu)：ArrayList铸豁、Vector、Stack
- 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：LinkedList菊碟、Queue
二节芥、歸納
- 繼承了AbstractList抽象類，實(shí)現(xiàn)了List接口逆害，實(shí)現(xiàn)了RandomAccess, Cloneable, java.io.Serializable接口头镊，所以支持快速訪問、復(fù)制(拷貝)魄幕、序列化相艇。
- 基于泛型的一維數(shù)組實(shí)現(xiàn)，有序纯陨，允許null存在坛芽，支持動(dòng)態(tài)擴(kuò)容，默認(rèn)容量為10翼抠，增長系數(shù)為0咙轩，兩個(gè)值都是可以通過構(gòu)造函數(shù)傳遞，擴(kuò)容時(shí)阴颖，如果增長系數(shù)大于0活喊，擴(kuò)容的大小為現(xiàn)有容量大小加上增長系數(shù)值，如果增長系數(shù)小于0量愧，則擴(kuò)容2倍钾菊，如果還是不夠則直接擴(kuò)容要其需求之。
- Vector的擴(kuò)容方式是直接創(chuàng)建一個(gè)新的數(shù)組侠畔，并將數(shù)據(jù)拷貝到新數(shù)組中结缚。
- 查和改操作速度非常快【時(shí)間復(fù)雜度：O(1)】,增和刪操作相對(duì)較慢【時(shí)間復(fù)雜度：最快O(1)最慢O(n)】软棺。
- Vector的操作單線安全红竭，加入了同步代碼塊，多線程安全（但不絕對(duì)），可以看成線程安全版本的ArrayList（其實(shí)也不絕對(duì)茵宪，在使用還是會(huì)加鎖操作）最冰。
- 相比于ArrayList其效率低，因?yàn)榧尤肓藄ynchronized操作稀火。
三暖哨、分析
1、接口
在分析Vector源碼之前凰狞，我們先來看看集合的接口--List篇裁。
public interface List<E> extends Collection<E> {
...
// 增
boolean add(E e);
void add(int index, E element);
// 刪
boolean remove(Object o);
E remove(int index);
// 改
E set(int index, E element);
// 查
E get(int index);
...
}
在上述接口中，我只抽取了比較重要的幾個(gè)方法赡若，然后以此為后續(xù)重點(diǎn)分析目標(biāo)达布，其List接口對(duì)應(yīng)的源碼中遠(yuǎn)不止上述幾個(gè)方法，有興趣的同學(xué)可以自行翻閱逾冬。
2黍聂、成員變量
在Vector的源碼中,其成員變量并不多,所以在此把它們都一一列出。
public class Vector<E> extends AbstractList<E> implements List<E>
, RandomAccess, Cloneable, java.io.Serializable {
// 序列化唯一表示UID
private static final long serialVersionUID = -2767605614048989439L;
// 保存Vector中數(shù)據(jù)的數(shù)組
protected Object[] elementData;
// 實(shí)際數(shù)據(jù)的數(shù)量
protected int elementCount;
// 容量增長系數(shù)
protected int capacityIncrement;
/**
* 最大容量身腻，也就是一維數(shù)組長度的最大值
* 為什么要“-8”操作产还？
* 因?yàn)樵谝峙涞臄?shù)組的最大大小時(shí)，vm會(huì)在一維數(shù)組中會(huì)保留一些嘀趟。
* 嘗試分配更大的數(shù)組可能會(huì)導(dǎo)致OutOfMemoryError:請(qǐng)求的數(shù)組大小超過VM限制
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
...
}
3脐区、構(gòu)造函數(shù)
構(gòu)造函數(shù)是一個(gè)類最常見的，同樣也是最常被使用到的去件，接著我們分析Vector的三個(gè)不同的構(gòu)造函數(shù)坡椒。
public class Vector<E> extends AbstractList<E> implements List<E>
, RandomAccess, Cloneable, java.io.Serializable {
...
/**
* 無參構(gòu)造函數(shù)
*/
public Vector() {
// 調(diào)用有一個(gè)參數(shù)傳值的有參構(gòu)造函數(shù)，默認(rèn)容量為10
this(10);
}
/**
* 有參構(gòu)造函數(shù)
*
* @param initialCapacity 數(shù)組容量
* @throws IllegalArgumentException 不合法的參數(shù)異常
*/
public Vector(int initialCapacity) {
this(initialCapacity, 0);
}
/**
* 有參構(gòu)造函數(shù)
*
* @param initialCapacity 數(shù)組容量
* @param capacityIncrement 增長系數(shù)
* @throws IllegalArgumentException 不合法的參數(shù)異常
*/
public Vector(int initialCapacity, int capacityIncrement) {
super();
// 如果initialCapacity不合法尤溜，拋出異常
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
// 設(shè)置新的數(shù)組，并且設(shè)置好數(shù)組容量
this.elementData = new Object[initialCapacity];
// 賦值增長系數(shù)
this.capacityIncrement = capacityIncrement;
}
/**
* 有參構(gòu)造函數(shù)
* 構(gòu)造包含指定元素的列表集合
*
* @param c 集合元素
* @throws NullPointerException 如果集合c為null汗唱，則拋出空指針異常
* @since 1.2
*/
public Vector(Collection<? extends E> c) {
// 將集合轉(zhuǎn)換為數(shù)組
elementData = c.toArray();
// 設(shè)置數(shù)組的真實(shí)長度
elementCount = elementData.length;
// 判斷其是不是Object對(duì)象宫莱，如果不是將其轉(zhuǎn)換為Object對(duì)象數(shù)組
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, elementCount, Object[].class);
}
...
}
4、增
ArrayList的增操作有兩種實(shí)現(xiàn)哩罪，分別為add(E e)和add(int index, E element)授霸，下面我們來分析其兩種實(shí)現(xiàn)。
public class Vector<E> extends AbstractList<E> implements List<E>
, RandomAccess, Cloneable, java.io.Serializable {
...
/**
* 將元素e添加到列表中
*
* @param e 元素e
* @return 返回true標(biāo)識(shí)添加成功
*/
public synchronized boolean add(E e) {
modCount++;
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = e;
return true;
}
/**
* 將元素element添加到指定的索引位置
*
* @param index 要插入指定元素的索引
* @param element 要插入的元素
* @throws IndexOutOfBoundsException 如果索引角標(biāo)不合法际插，則拋出索引越界異常
*/
public synchronized void add(int index, E element) {
insertElementAt(element, index);
}
/**
* 看是否需要進(jìn)行擴(kuò)容操作
*
* @param minCapacity 容積碘耳，其實(shí)就是數(shù)組的容量大小
*/
private void ensureCapacityHelper(int minCapacity) {
// 當(dāng)該if成立時(shí)，說明當(dāng)前數(shù)組(容器)的空間不夠了框弛，需要擴(kuò)容辛辨，所以調(diào)用grow()方法
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
/**
* 增加容量以確保它至少可以容納由最小容量參數(shù)指定的元素?cái)?shù)目
*
* @param minCapacity 容積，其實(shí)就是數(shù)組的容量大小
*/
private void grow(int minCapacity) {
// 獲取原始容積
int oldCapacity = elementData.length;
// 這里就是擴(kuò)容到原始容量的2倍
int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
capacityIncrement : oldCapacity);
// 如果擴(kuò)容2倍后還不滿足，則直接賦值到其所需的容量
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 如果擴(kuò)容的容量大于整型的最大值斗搞，則進(jìn)行異常處理或者賦值為整型最大值
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 調(diào)用Arrays.copyOf()創(chuàng)建一個(gè)新的數(shù)組并將數(shù)據(jù)拷貝到新數(shù)組中指攒，最后讓elementData進(jìn)行引用
elementData = Arrays.copyOf(elementData, newCapacity);
}
/**
* 判斷minCapacity是否溢出
*
* @param minCapacity 容積，其實(shí)就是數(shù)組的容量大小
*/
private static int hugeCapacity(int minCapacity) {
// 判斷minCapacity是否小于零僻焚，小于則拋出異常
if (minCapacity < 0) throw new OutOfMemoryError();
// 判斷minCapacity是否超過前邊設(shè)置的默認(rèn)成員變量的值允悦，超過整型的邊界值從而進(jìn)行賦值
return (minCapacity > MAX_ARRAY_SIZE) ?Integer.MAX_VALUE :MAX_ARRAY_SIZE;
}
...
}
5、刪
Vector的刪操作有兩種實(shí)現(xiàn)虑啤，分別是remove(int index)和remove(Object o)隙弛，下面我們來分析其兩種實(shí)現(xiàn)。
public class Vector<E> extends AbstractList<E> implements List<E>
, RandomAccess, Cloneable, java.io.Serializable {
...
/**
* 刪除索引為index的元素并返回
*
* @param index 要?jiǎng)h除的索引
* @return 返回刪除的元素
* @throws IndexOutOfBoundsException 拋出索引角標(biāo)越界異常
*/
public synchronized E remove(int index) {
// 這是Vector的父類AbstractList中定義了一個(gè)int型的屬性
// 在此用來記錄了Vector結(jié)構(gòu)性變化的次數(shù)
modCount++;
// 判斷索引是否合法性
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
// 獲取要?jiǎng)h除的元素
E oldValue = (E) elementData[index];
// 在執(zhí)行刪除操作時(shí)數(shù)組需要移動(dòng)的元素個(gè)數(shù)
int numMoved = size - index - 1;
// (numMoved > 0)成立則將數(shù)組進(jìn)行前移copy
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,numMoved);
// 因?yàn)閿?shù)組有可能進(jìn)行了整個(gè)前移1位狞山，所以將最后一個(gè)索引對(duì)應(yīng)的值置空全闷，從而降低GC
elementData[--size] = null;
// 返回要?jiǎng)h除的元素
return oldValue;
}
/**
* 刪除元素o，并且返回是否有效刪除
*
* @param o 元素將從此列表中刪除(如果存在)
* @return 如果存在該元素將其刪除并返回true铣墨，否則返回false
*/
public boolean remove(Object o) {
return removeElement(o);
}
/**
* 刪除元素obj室埋，并且返回是否有效刪除
*
* @param obj 元素將從此列表中刪除(如果存在)
* @return 如果存在該元素將其刪除并返回true，否則返回false
*/
public synchronized boolean removeElement(Object obj) {
// 用來記錄了Vector結(jié)構(gòu)性變化的次數(shù)
modCount++;
// 獲取當(dāng)前元素obj的索引位置
int i = indexOf(obj);
// 索引大于等于0代表該元素存在伊约，否則不存在
if (i >= 0) {
removeElementAt(i);
return true;
}
return false;
}
/**
* 檢索元素o的索引坐標(biāo)
*
* @param o 元素o
* @return 返回元素o的索引坐標(biāo)姚淆，如若不存在則返回-1
*/
public int indexOf(Object o) {
return indexOf(o, 0);
}
/**
* 檢索元素o的索引坐標(biāo)
*
* @param o 元素o
* @param index 從什么位置開始檢索
* @return 返回元素o的索引坐標(biāo)，如若不存在則返回-1
*/
public synchronized int indexOf(Object o, int index) {
// 這里把空和非空進(jìn)行區(qū)分屡律，空的話用“==”判斷腌逢，非空用“equals”判斷
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;
}
/**
* 刪除元素obj，并且返回是否有效刪除
*
* @param obj 元素將從此列表中刪除(如果存在)
* @return 如果存在該元素將其刪除并返回true超埋，否則返回false
*/
public synchronized void removeElementAt(int index) {
// 用來記錄Vector結(jié)構(gòu)性變化的次數(shù)
modCount++;
// 判斷索引位置是否合法搏讶，不合法拋出異常
if (index >= elementCount) {
throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount);
}else if (index < 0) {
throw new ArrayIndexOutOfBoundsException(index);
}
// 在執(zhí)行刪除操作時(shí)數(shù)組需要移動(dòng)的元素個(gè)數(shù)
int j = elementCount - index - 1;
if (j > 0) {
System.arraycopy(elementData, index + 1, elementData, index, j);
}
// 因?yàn)閿?shù)組有可能進(jìn)行了整個(gè)前移1位，所以將最后一個(gè)索引對(duì)應(yīng)的值置空霍殴，從而降低GC
elementCount--;
elementData[elementCount] = null;
}
...
}
6媒惕、改
Vector的改操作有一種實(shí)現(xiàn)，對(duì)應(yīng)的是set(int index, E element)来庭，下面我們來分析這種實(shí)現(xiàn)妒蔚。
public class Vector<E> extends AbstractList<E> implements List<E>
, RandomAccess, Cloneable, java.io.Serializable {
...
/**
* 修改索引角標(biāo)為index的元素值
*
* @param index 要修改的索引坐標(biāo)
* @param element 修改后存儲(chǔ)的元素值
* @return 返回修改前的元素值
* @throws IndexOutOfBoundsException 拋出索引角標(biāo)越界異常
*/
public synchronized E set(int index, E element) {
// 判斷索引是否合法性
if (index >= elementCount)
throw new ArrayIndexOutOfBoundsException(index);
// 獲取原本index的元素值
E oldValue = elementData(index);
// 將其替換成新的元素值
elementData[index] = element;
// 返回修改前的元素值
return oldValue;
}
...
}
7、查
Vector的查操作有一種實(shí)現(xiàn)月弛，對(duì)應(yīng)的是get(int index)肴盏，下面我們來分析這種實(shí)現(xiàn)。
public class Vector<E> extends AbstractList<E> implements List<E>
, RandomAccess, Cloneable, java.io.Serializable {
...
/**
* 查找索引角標(biāo)為index的元素值
*
* @param index 要修改的索引坐標(biāo)
* @return 返回查找到的索引為index的元素值
* @throws IndexOutOfBoundsException 拋出索引角標(biāo)越界異常
*/
public synchronized E get(int index) {
// 判斷索引是否合法性
if (index >= elementCount)
throw new ArrayIndexOutOfBoundsException(index);
// 返回查找到的索引為index的元素值
return elementData(index);
}
...
}
