文章目錄
- 前言
- 一、List類圖
- 二、原始碼剖析
- 1. Vector（此篇詳解）
- 2. ArrayList
- 3. LinkedList
- 4. CopyOnWriteArrayList
- ~~ 碼上福利
前言
業精于勤荒于嬉，行成于思毀于隨；
在碼農的大道上，唯有自己強才是真正的強者，求人不如求己，靜下心來，開始思考…
今天一起來聊一聊 List集合，看到這里，筆者懂，大家莫慌，先來寶圖鎮樓 ~
年輕人，不講武德，敢偷襲我老同志，耗子尾汁…
咳咳… 相信大家滿腦子的ArrayList已被保國爺爺經典的畫面以及臺詞沖淡了，那么，目的已達到，那我們言歸正傳，對于螢屏前帥氣的猿友們來說，ArrayList，LinkedList，Vector，CopyOnWriteArrayList… 張口就來，閉眼能寫，但是呢，我相信大部分的猿友們并沒有刨根問底真正去看過其原始碼，此時，筆者帥氣的臉龐似有似無洋溢起一抹微笑，畢竟是查看過原始碼的猿，就是那么的不講武德，吃我一記閃電五連鞭，話不多說，來吧，展示…
一、List類圖
二、原始碼剖析
1. Vector（此篇詳解）
在講Vector集合之前呢，有必要囑咐螢屏前的猿友一聲，其實呢，Vector集合與ArrayList集合基本類似，但也存在差異，重點在于其對應構造以及新增、獲取、洗掉方法，一定要認真仔細觀閱，希望再文章末尾，猿友們已自行找出其兩者異同點；
- 建構式
// Vector底層為陣列
protected Object[] elementData;
// 自定義擴容增量
protected int capacityIncrement;
/**
* 無參構造
*/
public Vector() {
this(10);
}
/**
* 有參構造一
* @param initialCapacity：指定陣列初始容量
*/
public Vector(int initialCapacity) {
this(initialCapacity, 0);
}
/**
* 有參構造二
* @param initialCapacity
* @param capacityIncrement：指定自定義擴容增量，后續擴容中有具體體現
*/
public Vector(int initialCapacity, int capacityIncrement) {
// 父類AbstractList無參構造 - 無具體實作
super();
// 陣列初始容量校驗
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
// 初始化陣列 - length:10
this.elementData = new Object[initialCapacity];
// 設定自定義擴容增量
this.capacityIncrement = capacityIncrement;
}
從原始碼中可以看出，上述構造方法中，不論是無參構造方法，還是有參構造方法一最終都會呼叫有參構造方法二，其包含兩個引數（initialCapacity：陣列初始容量，capacityIncrement：自定義擴容增量）；
結論：
構造初始化物件，初始化陣列，默認length為10，自定義擴容增量默認為0；
- add() - 添加元素方法
// 記錄對Vector操作次數
protected transient int modCount = 0;
// 記錄陣列元素個數
protected int elementCount;
// Vector最大元素個數
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
/**
* 入口 - synchronized修飾：執行緒安全
*/
public synchronized boolean add(E e) {
// 操作次數++
modCount++;
// 對陣列進行擴容
ensureCapacityHelper(elementCount + 1);
// 陣列添加元素
elementData[elementCount++] = e;
return true;
}
// 判斷是否需要進行擴容 minCapacity：第一次add為(0+1)=1
private void ensureCapacityHelper(int minCapacity) {
// 最小容量-陣列長度>0：需要進行擴容
// 第1次add時：1-10 < 0，無需擴容
// 第11次add時：11-10 > 0，需進行擴容
if (minCapacity - elementData.length > 0) {
// 具體擴容方法
grow(minCapacity);
}
}
// 具體擴容方法
private void grow(int minCapacity) {
// 獲取陣列長度
int oldCapacity = elementData.length;
// 計算新的陣列容量；capacityIncrement：自定義擴容增量，用戶可通過有參構造自定義其值，默認為0
// 當用戶自定義capacityIncrement且值大于0，擴容后陣列容量為：陣列長度+capacityIncrement
// 反之(包含：用戶自定義但值<=0 或 用戶未定義)，擴容后陣列容量為：陣列長度+陣列長度，即擴容后為之前陣列長度的2倍
int newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity);
// 判斷如果擴容后長度-最小容量<0,擴容后的長度為最小容量，此判斷作用于第一次添加元素時
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 計算擴容后長度最大值，最大值為Integer的最大值(2^31-1)
if (newCapacity - MAX_ARRAY_SIZE > 0) {
if (minCapacity < 0)
throw new OutOfMemoryError();
newCapacity = (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}
// 使用 Arrays.copyOf 對我們陣列容量實作擴容
elementData = Arrays.copyOf(elementData, newCapacity);
}
從原始碼中可以看出，添加元素時且會對陣列進行擴容；
知識點：
第一次擴容是在第11次add時，此時分為兩種情況：
- 1.用戶自定義capacityIncrement且值大于0時：陣列長度擴容為(當前陣列長度+capacityIncrement)，之后每次擴容遵循此規則；
- 2.用戶未定義capacityIncrement(代表默認情況下) 或 用戶自定義capacityIncrement且值小于等于0時：陣列長度擴容為(當前陣列長度+當前陣列長度)，之后每次擴容遵循此規則；
結論：
默認情況下，每次擴容后為之前陣列長度的2倍；
最大值：Integer最大值(2^31-1)，最小值：10；
- get() - 獲取元素方法
/**
* 入口 - synchronized修飾：執行緒安全
*/
public synchronized E get(int index) {
// 校驗是否越界
if (index >= elementCount)
throw new ArrayIndexOutOfBoundsException(index);
// so easy：通過下標獲取元素
return elementData(index);
}
// 通過下標獲取元素
E elementData(int index) {
return (E) elementData[index];
}
從原始碼中可以看出，獲取元素時就是獲取陣列元素，通過下標直接獲取即可；
- remove() - 洗掉元素方法
/**
* 入口 - synchronized修飾：執行緒安全
*/
public synchronized E remove(int index) {
// 操作次數++
modCount++;
// 校驗下標是否越界
if (index >= elementCount)
throw new ArrayIndexOutOfBoundsException(index);
// 獲取要洗掉的元素
E oldValue = elementData(index);
/**
* public static native void arraycopy(Object src, int srcPos, Object dest, int destPos, int length);
* 說明此方法引數作用：
* src：源陣列
* srcPos：源陣列要復制的起始位置
* dest：目的陣列
* destPos：目的陣列放置的起始位置
* length：復制的長度
*/
// 對應引數中length
int numMoved = elementCount - index - 1;
// 洗掉元素其實就是一個陣列整體移動的程序，再將最后一個元素置空即可
if (numMoved > 0) {
// 此每個引數都需各位猿友細品下，慢慢來，只是一個程序... 如此如此，這般這般，暖男的我在下方提供圖，便于猿友們理解
System.arraycopy(elementData, index+1, elementData, index, numMoved);
}
// 將最后一個元素置空，如只有一個元素，置空即可，便于GC作業
elementData[--elementCount] = null; // Let gc do its work
// 回傳洗掉的元素值
return oldValue;
}
相信猿友們已經看出來了，Vector的洗掉元素方法與ArrayList的洗掉元素方法是一樣的，而且除了洗掉元素方法，其增加元素方法、獲取元素方法也都是很相似的；
從原始碼中可以看出，洗掉元素實則為陣列移動覆寫的程序，已下圖為例，便于大家理解：
- 源陣列：
- 目標陣列(洗掉元素后的陣列)：
- 洗掉下標為0的元素(不)
結合 arraycopy(Object src, int srcPos, Object dest, int destPos, int length)來講，可得知：
- src：為上述源陣列；
- srcPos：源陣列要復制的起始位置為(index+1 = 0+1 = 1)
- dest：為上述目標陣列
- destPos：目標陣列放置的起始位置為(index=0)；
- length：復制的長度為(size-index-1 = 4-0-1 = 3)
- 程序演示：
- 劃重點：
相信之前沒仔細研究過的猿友們，對Vector洗掉元素大概程序已有一些了解；
但對于有經驗的開發猿來說，筆者大概能猜到兩種，一種是一心追隨本心道心堅固的猿友，另一種呢就是追求大道審視局勢的猿友；
前者：看到這里，不論是從筆者的描述還是圖文結合的理解，貌似有一定的道理，但當時的我看并不是如此，既然是arraycopy，那就不應該是移動覆寫，而是重新復制一個新陣列，
后者：我當時查閱原始碼好像覺得也并不是這樣的，記得也是復制一個新陣列，而不是移動覆寫，但筆者描述確又很在理，難道…遺漏了什么？
邪魅一笑，嘴角微起，來吧，展示…
其實嘛，大家說的都沒錯，實際上確實是復制新的陣列，但Vector這里，源陣列和目標陣列是用一個呢.
哎…人生么，如此這般，細節決定成敗，
- Vector總結：
- 底層為陣列；
- 構造初始化，陣列為空陣列，集合size為0，陣列length為0；
第一次擴容也就是第11次add時：默認情況下，陣列長度length擴容為20，集合size為11；
默認情況下，之后每次擴容遵循此規則，oldCapacity + oldCapacity，故每次擴容為之前陣列長度的2倍；
最大值：Integer最大值2147483647(2^31-1)，最小值：10；- 通過下標去獲取元素，故查詢效率高，增刪效率低；
- 執行緒安全；
- 有modCount；
2. ArrayList
不講武德，一起聊聊List集合之ArrayList
3. LinkedList
不講武德，一起聊聊List集合之LinkedList
4. CopyOnWriteArrayList
不講武德，一起聊聊List集合之CopyOnWriteArrayList
~~ 碼上福利
大家好，我是猿醫生：
在碼農的大道上，唯有自己強才是真正的強者，求人不如求己，靜下心來，掃碼一起學習吧…
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/241886.html
標籤：其他