ArrayList原始碼決議
簡介
ArrayList是Java集合框架中非常常用的一種資料結構，繼承自AbstractList,實作了List介面，底層基于陣列來實作動態容量大小的控制，允許null值的存在，同時還實作了RandomAccess、Cloneable、Serializable介面，支持快速訪問、復制、序列化操作，
了解陣列
陣列簡單來說就是將所有的資料排成一排存放在系統分配的一個記憶體塊上，通過使用特定元素的索引作為陣列的下標，可以在常數時間內訪問陣列元素的這么一個結構；
陣列優缺點
優點
- 簡單方便已使用
- 訪問元素快
缺點
- 大小固定：陣列的大小是靜態的，在使用前必須確定好陣列的大小
- 分配一個連續空間塊：陣列初始分配空間時，有時候無法分配能存盤整個陣列的記憶體空間（當陣列規模太大時）；
- 基于位置的插入操作實作復雜：如果要在陣列中的給定位置插入元素，那么可能就會需要移動存盤在陣列中的其他元素，這樣才能騰出指定的位置來放插入的新元素；而如果在陣列的開始位置插入元素，那么這樣的移動操作開銷就會很大，
ArrayList決議
我們提到陣列的特點是大小固定，ArrayList的底層是基于陣列來實作容量的大小動態變化的，那我們一起來結合原始碼看看，是如何實作這一功能的，
我們找到java.util.ArrayList包查看代碼，并通過注釋的方式，一起來揭開面紗，
1、成員變數
// 默認的容量大小
private static final int DEFAULT_CAPACITY = 10;
// 空陣列物件Object
private static final Object[] EMPTY_ELEMENTDATA = https://www.cnblogs.com/wujiwen/archive/2021/04/15/{};
// 有一個空資料物件Object
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 默認修飾且不參與序列化的 陣列物件，也是實際存盤資料的地方
transient Object[] elementData; // non-private to simplify nested class access
// 實際大小容量
private int size;
我們發現有兩個一樣的空陣列物件，為什么要用兩個呢？源代碼中也進行來解釋 We distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when first element is added.
也就是說，這是一個共享的空陣列實體，通過與默認的空陣列區分開，好處是，添加元素時知道該 elementData 從空的建構式還是有參建構式被初始化的，以便確認如何擴容，
在AbstractList父類中還有一個變數
protected transient int modCount = 0;
用來記錄對List的操作次數，作用在使用Iterator時，防止在迭代程序中集合被修改，
2、建構式
無引數構造
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this.elementData = https://www.cnblogs.com/wujiwen/archive/2021/04/15/DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
默認的無引數構造中直接給elementData賦值來一個空的資料，但我們看到注釋上說初始容量為10的陣列，這好像不太對啊，其實這只是一個延后的操作，當第一次添加資料進去時，容量會擴容到10，好處是避免無用的ArrayList的出現，具體的實作我們接著往后看，
指定初始容量構造
public ArrayList(int initialCapacity) {
// 指定的容量大于0，直接new一個指定容量大小的陣列
if (initialCapacity > 0) {
this.elementData = https://www.cnblogs.com/wujiwen/archive/2021/04/15/new Object[initialCapacity];
// 指定容量等于0，那就賦值空陣列，
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
// 無效容量大小
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
這個還是比較清晰的，根據指定容量初始化一個陣列，加入了容量大小的判斷操作，
指定Collection集合構造
public ArrayList(Collection<? extends E> c) {
// 首先轉成陣列
Object[] a = c.toArray();
// 有效大小的陣列哈
if ((size = a.length) != 0) {
// 這里做了優化，如果也是一個ArrayList集合直接賦值即可
if (c.getClass() == ArrayList.class) {
elementData = https://www.cnblogs.com/wujiwen/archive/2021/04/15/a;
} else {
// 其他的型別就做拷貝啦
elementData = Arrays.copyOf(a, size, Object[].class);
}
} else {
// replace with empty array.
elementData = EMPTY_ELEMENTDATA;
}
}
簡單點說其實就是把集合轉成陣列，然后賦值給elementData，可能你看到的版本不一樣，主要是在
c.getClass() == ArrayList.class做了優化，如果也是ArrayList的集合，那就不用做陣列拷貝了，這個還是比較耗性能的，
主要操作函式決議
下面將主要的增刪改操作進行分析
添加元素操作
單元素添加
public boolean add(E e) {
// 我們需要添加 一個元素，則需要判斷+1后的容量是否需要擴容了，同時記錄modCount
ensureCapacityInternal(size + 1); // Increments modCount!!
// 接在index后添加元素，并且更新當前集合大小size
// 可以理解成 index =size+1;elementData[index];size++
elementData[size++] = e;
return true;
}
// 提取方法哈，比較計算，確定容量大小
//private static int calculateCapacity(Object[] elementData, int minCapacity) {
// if (elementData =https://www.cnblogs.com/wujiwen/archive/2021/04/15/= DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
// return Math.max(DEFAULT_CAPACITY, minCapacity);
// }
// return minCapacity;
//}
// 做了簡化，與calculateCapacity 一致
private void ensureCapacityInternal(int minCapacity) {
//ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
// 提取calculateCapacity方便可以做一個簡化，可能你的版本就是這樣
// 判斷是否是空陣列，如果是空陣列，那么minCapacity = 10
// 這樣就解答了我們前面提到的問題，在添加第一個元素時才將容量設定成10
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity)
}
// 記錄操作次數，然后判斷是否需要擴容
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
// 當添加一個元素后的容量大于當前元素個數，則需要擴容了
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
// 擴容方法，minCapacity 添加一個元素后的容量
private void grow(int minCapacity) {
// overflow-conscious code
// 先記錄當前容量，也就是元素的個數
int oldCapacity = elementData.length;
// 不管，先擴容1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 如果擴容后的大小小于添加元素后的容量，則沒必要了，直接用添加元素后的容量了
// 這里可以看到哈，如果是空構造，添加引數時，newCapacity是等于0的，然后再賦值了10，
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 有最大容量限制
if (newCapacity - MAX_ARRAY_SIZE > 0)
// 就是給一個最大的容量了
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
// 陣列拷貝 底層還是System.arraycopy
elementData = Arrays.copyOf(elementData, newCapacity);
}
指定index添加元素
public void add(int index, E element) {
// 檢查index
rangeCheckForAdd(index);
// 是否需要擴容操作，記錄modCount
ensureCapacityInternal(size + 1); // Increments modCount!!
// 進行陣列拷貝，給這個添加的元素騰出一個位置index
System.arraycopy(elementData, index, elementData, index + 1,size - index);
// 在這個位置index放置元素
elementData[index] = element;
size++;
}
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private String outOfBoundsMsg(int index) {
return "Index: "+index+", Size: "+size;
}
我們看到哈，在添加元素的方法中，原則是計算容量，判斷是否需要擴容，并記錄修改次數，這里有一個非常重要的方法就是陣列拷貝，擴容需要拷貝，在指定index中放入元素也需要拷貝哈，下面我們通過畫圖的方式來解釋一下System.arraycopy這個函式
System.arraycopy詳解
這是System類中的一個靜態方法，用來實作陣列之間的復制，具體的實作我們就不去了解，我們主要來看看他的用法，以及在ArrayList是怎么使用的
public static native void arraycopy(Object src, int srcPos,
Object dest, int destPos,
int length);
引數說明
src：the sourse arr源陣列srcPos：starting position in the source array.源陣列的起始位置dest：the destination array.目標陣列destPos：starting position in the destination data.目標陣列的起始位置length：the number of array elements to be copied.復制的長度
舉幾個例子
// 給定陣列
int[] src = https://www.cnblogs.com/wujiwen/archive/2021/04/15/{1,2,3,4,5};
// 給定目標陣列
int[] dest = new int[src.length]
// 要求1 將src 陣列全部復制到dest中
System.arraycopy(src,0,dest,0,src.length);
// 要求2 將src的前三位數復制到dest中的后三位
System.arraycopy(src,0,dest,2,src.length-2);
陣列拷貝圖解
grow擴容拷貝
假定當前我們的集合元素已經有10個了，此時還需要添加一個元素，會經歷這樣的操作，
1、判斷需要擴容，新的容量為15的陣列，
2、將源陣列拷貝到新的陣列中，重新復制給elementData;
3、在index=10的位置添加元素
add index 移動拷貝
在集合中已經有了5個元素了，現在需要在index=1的位置插入一個新的元素，可以理解成插隊，
1、判斷是否需要擴容，這里發現不需要
2、System.arraycopy(elementData, index, elementData, index + 1,size - index);
以圖中為例，我們需要將index 1、2、3、4 整體往后挪動，就像有人插隊一樣，插入的位置后面整體后移了一位，index=0的位置是不用動的，這里的寫法應該是
System.arraycopy(elementData, 1, elementData, 1 + 1,5 - 1);
3、將index=1的位置重新賦值，原來index=1的位置已經被移到現在的index=2的位置了，
詳細的流程可以通過代碼的方式觀察即可理解這個程序，
移除元素操作
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
// 指定index 洗掉其索引位置的元素并回傳
public E remove(int index) {
// 老規矩，檢查index的邊界
rangeCheck(index);
// 記錄操作次數
modCount++;
// 找到這個待洗掉的元素，主要用戶回傳
E oldValue = https://www.cnblogs.com/wujiwen/archive/2021/04/15/elementData(index);
// 需要移動的數量
int numMoved = size - index - 1;
// 如果需要移動 ，如果只從后面洗掉的話，例如 size=5 index = 4 ,那么numMoved=0
if (numMoved > 0)
// 進行陣列拷貝移動，填上那個空位置
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
// 然后把尾巴多出來的那個元素刪掉啦
elementData[--size] = null; // clear to let GC do its work
// 回傳
return oldValue;
}
// 洗掉指定的物件
public boolean remove(Object o) {
// ArrayList元素允許為空的
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
// 比較元素，然后找到其所在的index 交由fastRemove通過index移除，與remove(index)
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
// 快速洗掉 和remove(index) 基本一致 ，在陣列index的操作是高效，通過index去操作
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
}
// 全部洗掉了
public void clear() {
modCount++;
// clear to let GC do its work
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
這里我們會發現一個問題啊，我們在靜態的陣列中進行index所在資料的洗掉時，一般是直接對 arr[index] = 0; 直接對索引位置的元素進行null賦值，但在ArrayList中就不一定是這樣了，他一直都是對最后一位元素進行操作elementData[size—] = null; 我們來畫個圖看一下
例如我們要對上圖中index=1的位置元素進行remove操作，怎么做呢？
1、找到index 2、3、4、5需要移動的元素，
2、將他們整體往前移動一位，這個時候需要洗掉的元素已經被覆寫了
3、再將最后一個洗掉，（真正移除的那個元素其實和前面一位一樣哦）
整體下來發現和add(E e,int index)整個流程好像正好相反，哈哈！
修改元素操作
public E set(int index, E element) {
// index 檢查
rangeCheck(index);
// 找到舊元素
E oldValue = https://www.cnblogs.com/wujiwen/archive/2021/04/15/elementData(index);
// 替換所在位置的元素
elementData[index] = element;
return oldValue;
}
這個還是比較簡單的，可以理解成是一個替換的操作就可以了，
查詢操作
// 指定index 回傳其所在的元素
public E get(int index) {
// 邊界檢查
rangeCheck(index);
// 回傳，這個簡單，索引快速定位
return elementData(index);
}
// 從前往后查詢，第一次出現的位置index
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
// 從后往前查詢，第一次出現的位置index
public int lastIndexOf(Object o) {
if (o == null) {
for (int i = size-1; i >= 0; i--)
if (elementData[i]==null)
return i;
} else {
for (int i = size-1; i >= 0; i--)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
查詢操作就簡單了很多哈，基本上都是基于索引來訪問的，
到這里我們已經總結了很多常用的方法，在ArrayList中還有非常多的方法，例如迭代器Iterator、suList操作等等，這里就不過多進行決議了，不過后面會通過專門的篇幅來介紹迭代器Iterator和為什么不能在for遍歷集合時對集合進行remove操作，有時還會拋出例外ConcurrentModificationException，
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
這里有一個我們非常熟悉的變數modCount，詳細的后面在來決議把，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/276566.html
標籤：其他