閱讀優(yōu)秀的源碼是提升編程技巧的重要手段之一。
如有不對(duì)的地方带膜，歡迎指正~
轉(zhuǎn)載請(qǐng)注明出處https://blog.lzoro.com。
前言
當(dāng)你對(duì)某件事情很感興趣的時(shí)候，時(shí)間的流逝在感知中都模糊了（是不是很文藝烂完，繞口得都快聽不懂了），通俗來說诵棵，就是時(shí)間過得很快抠蚣。
而且，只有感興趣才能驅(qū)動(dòng)你繼續(xù)下去履澳，不然讀源碼嘶窄，寫解析博客這么高(Ku)大(Zao)上的事，是很難堅(jiān)持的距贷。
詳細(xì)地寫一篇源碼解析博客少則半天一天柄冲，比如本篇，多則幾天忠蝗，比如紅黑樹在Java - HashMap中的應(yīng)用现横，又要畫圖又要注釋，還要排版阁最，時(shí)不時(shí)要加點(diǎn)表情戒祠，開個(gè)車什么的，你說要是沒興趣速种，怎么堅(jiān)持呢姜盈，還不如吃個(gè)雞實(shí)在(啊，暴露了我是吃雞選手)配阵。
image
閑話少說馏颂，打開你的IDE，挽起袖子棋傍，開擼代碼救拉，加上注釋，總計(jì)1461行代碼瘫拣。
基本介紹
常量
相比HashMap來說亿絮，ArrayList的常量算是短小精悍了，只有幾個(gè)。
其中包含一個(gè)默認(rèn)容量和兩個(gè)空數(shù)組等壹无，如下葱绒。
/**
* 默認(rèn)初始化容量
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* 空數(shù)組共享實(shí)例
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* 缺省大小的空數(shù)組共享實(shí)例
* 與 EMPTY_ELEMENTDATA 區(qū)分開來，以便知道第一個(gè)元素添加時(shí)如何擴(kuò)容
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* 最大可分配大小
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
成員變量
成員變量也是簡單到令人發(fā)指斗锭，一個(gè)負(fù)責(zé)實(shí)際存儲(chǔ)的緩沖數(shù)組和一個(gè)表示大小的變量地淀。
/**
* 實(shí)際負(fù)責(zé)存儲(chǔ)的緩沖數(shù)組
* ArrayList的容量就是緩沖數(shù)組的長度
*
* 空的ArrayList(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)在第一個(gè)元素添加時(shí)將會(huì)以默認(rèn)容量擴(kuò)容
*/
transient Object[] elementData; // 非私有，以簡化嵌套類的訪問
/**
* 大小
*/
private int size;
構(gòu)造函數(shù)
三個(gè)構(gòu)造函數(shù)岖是，分別是利用默認(rèn)初始容量/給定初始容量/給定特定集合來構(gòu)造ArrayList帮毁。
/**
* 根據(jù)給定初始容量構(gòu)造一個(gè)空的list
*
* @param initialCapacity list的初始容量
* @throws IllegalArgumentException 當(dāng)給定的初始容量非負(fù)時(shí)拋異常
*/
public ArrayList(int initialCapacity) {
//判斷給定初始化容量是否合法
if (initialCapacity > 0) {
//創(chuàng)建數(shù)組
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
/**
* 按默認(rèn)初始容量(10)構(gòu)造一個(gè)空的list
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/**
* 根據(jù)給定集合構(gòu)造一個(gè)list，將按集合迭代的順序存儲(chǔ)
*
* @param c 集合
* @throws NullPointerException 集合為null時(shí)拋異常
*/
public ArrayList(Collection<? extends E> c) {
//集合轉(zhuǎn)數(shù)組后賦值給緩沖數(shù)組
elementData = c.toArray();
//判斷大小
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
//c.toArray方法可能不會(huì)返回Object[]形式的數(shù)組
//下面做一層判斷
if (elementData.getClass() != Object[].class)
//做拷貝操作
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
//如果是空集合豺撑，則替換成共享空數(shù)組實(shí)例
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
功能
看完了基本介紹烈疚，應(yīng)該會(huì)覺得Just so so。
接下來就要逐一介紹各個(gè)功能的具體實(shí)現(xiàn)了聪轿。
ArrayList中爷肝，我們常用的功能有add/remove/get等。
無外乎增刪改查陆错，下面一一介紹~
add
在ArrayList中灯抛，添加操作還分為幾種
- 從尾部添加元素
- 指定位置添加元素
- 從尾部添加集合
- 從指定位置添加集合
/**
* 從尾部添加指定元素
*
* @param e 元素
* @return <tt>true</tt> (as specified by {@link Collection#add})
*/
public boolean add(E e) {
//確保內(nèi)部容量，有一系統(tǒng)調(diào)用鏈但不復(fù)雜音瓷，下面分析
ensureCapacityInternal(size + 1); // Increments modCount!!
//存儲(chǔ)元素
elementData[size++] = e;
return true;
}
/**
* 在指定位置插入元素
* 移動(dòng)當(dāng)前位置的元素 (如果存在) 和后繼元素到右邊
*
* @param index index at which the specified element is to be inserted
* @param element element to be inserted
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public void add(int index, E element) {
//判斷邊界对嚼，可能會(huì)產(chǎn)生數(shù)組越界
rangeCheckForAdd(index);
//確保內(nèi)部容量，同上
ensureCapacityInternal(size + 1); // Increments modCount!!
//調(diào)用效率較高的System.arraycopy進(jìn)行數(shù)組復(fù)制
//目的是為了空出指定位置
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
//指定位置上放入指定元素
elementData[index] = element;
//容量+1
size++;
}
在添加的元素的時(shí)候绳慎，有一個(gè)關(guān)鍵方法ensureCapacityInternal是來確保內(nèi)部緩存數(shù)組的容量纵竖，當(dāng)容量不夠時(shí)進(jìn)行擴(kuò)容，下面具體看下這個(gè)方法的調(diào)用鏈
/**
* 私有方法
*/
private void ensureCapacityInternal(int minCapacity) {
//判斷是否是默認(rèn)空實(shí)例杏愤，如果是的話靡砌，計(jì)算擴(kuò)容容量
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
//調(diào)用ensureExplicitCapacity
ensureExplicitCapacity(minCapacity);
}
...
private void ensureExplicitCapacity(int minCapacity) {
//操作計(jì)算+1
modCount++;
// overflow-conscious code
//只有當(dāng)容量不夠時(shí)才擴(kuò)容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
/**
* 緩沖數(shù)組擴(kuò)容以確保能夠存儲(chǔ)給定元素
*
* @param minCapacity 期望的最小容量
*/
private void grow(int minCapacity) {
// overflow-conscious code
//現(xiàn)有元素長度
int oldCapacity = elementData.length;
//新容量為 舊容量 + 舊容量的一半
//如 10 + 5 = 15
int newCapacity = oldCapacity + (oldCapacity >> 1);
//如果計(jì)算的新容量比期望的最小容量小，則采用期望的最小容量作為擴(kuò)容參數(shù)
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//判斷是否超過最大數(shù)組容量
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
//最小擴(kuò)容容量通常是接近size的声邦，所以這是一場(chǎng)勝利
//這么臭美的嗎
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;
}
set
這里的set其實(shí)可以理解為修改乏奥，將指定位置的元素替換為新元素摆舟。
/**
* 修改指定位置的元素
*
* @param index index of the element to replace
* @param element element to be stored at the specified position
* @return the element previously at the specified position
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E set(int index, E element) {
//范圍檢查
rangeCheck(index);
//取出舊值用以返回
E oldValue = elementData(index);
//放入新的值
elementData[index] = element;
return oldValue;
}
remove
數(shù)組的移除和添加一樣亥曹，也分為幾種方式
- 根據(jù)下標(biāo)移除
- 根據(jù)對(duì)象移除
- 根據(jù)集合移除
- 根據(jù)過濾器移除
- 根據(jù)范圍移除(受保護(hù)的方法)
/**
* 刪除指定位置的元素，后繼元素左移(前移)
*
* @param index 下標(biāo)
* @return the 被移除的元素
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E remove(int index) {
//下標(biāo)檢查
rangeCheck(index);
//操作計(jì)數(shù) + 1
modCount++;
//獲取指定位置的元素(用以返回)
E oldValue = elementData(index);
int numMoved = size - index - 1;
//用system.arraycopy的方式移動(dòng)元素
//相當(dāng)于是index位置后的元素前移
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
//最后一個(gè)數(shù)組元素引用置為null恨诱，方便GC
elementData[--size] = null; // clear to let GC do its work
//返回
return oldValue;
}
/**
* 當(dāng)元素存在的時(shí)候媳瞪，刪除第一個(gè)找到的指定元素
*
* 如果元素不存在，則list不會(huì)變動(dòng)
*
* @param o element to be removed from this list, if present
* @return <tt>true</tt> if this list contained the specified element
*/
public boolean remove(Object o) {
//o是否是null元素(數(shù)組允許存儲(chǔ)null)
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
//調(diào)用內(nèi)部的fastRemove方法照宝，后面分析
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
//這里跟上面不一樣的是蛇受，是用equals來比較，而不是比較地址
if (o.equals(elementData[index])) {
//同上
fastRemove(index);
return true;
}
}
return false;
}
/**
* 根據(jù)給定的集合厕鹃，將list中與集合相同的元素全部刪除
*
* @param c collection containing elements to be removed from this list
* @return {@code true} if this list changed as a result of the call
* @throws ClassCastException if the class of an element of this list
* is incompatible with the specified collection
* (<a href="Collection.html#optional-restrictions">optional</a>)
* @throws NullPointerException if this list contains a null element and the
* specified collection does not permit null elements
* (<a href="Collection.html#optional-restrictions">optional</a>),
* or if the specified collection is null
* @see Collection#contains(Object)
*/
public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c);
//調(diào)用批量刪除兢仰，后續(xù)分析
return batchRemove(c, false);
}
/**
* 通過一個(gè)過濾器接口實(shí)現(xiàn)乍丈，來實(shí)現(xiàn)刪除
*/
@Override
public boolean removeIf(Predicate<? super E> filter) {
Objects.requireNonNull(filter);
// figure out which elements are to be removed
// any exception thrown from the filter predicate at this stage
// will leave the collection unmodified
int removeCount = 0;
//用bitset來存儲(chǔ)哪些下標(biāo)對(duì)應(yīng)的元素要?jiǎng)h除，哪些下標(biāo)對(duì)應(yīng)的元素要保存
//這里不清楚BitSet的用法的把将，可以先行了解一下
final BitSet removeSet = new BitSet(size);
//判斷并發(fā)修改用
final int expectedModCount = modCount;
final int size = this.size;
//按順序遍歷且沒有并發(fā)修改
for (int i=0; modCount == expectedModCount && i < size; i++) {
@SuppressWarnings("unchecked")
final E element = (E) elementData[i];
//利用過濾器匹配元素轻专，如果匹配，則刪除計(jì)數(shù)+1察蹲，并將下標(biāo)進(jìn)行存儲(chǔ)
if (filter.test(element)) {
removeSet.set(i);
removeCount++;
}
}
//判斷是否存在并發(fā)修改
if (modCount != expectedModCount) {
//拋出并發(fā)修改異常
throw new ConcurrentModificationException();
}
// shift surviving elements left over the spaces left by removed elements
//判斷是否有要?jiǎng)h除的元素
final boolean anyToRemove = removeCount > 0;
if (anyToRemove) {
final int newSize = size - removeCount;
for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) {
//下一個(gè)要保存的元素
i = removeSet.nextClearBit(i);
//存放到新數(shù)組
elementData[j] = elementData[i];
}
//把實(shí)際要保存的元素之后的全部置為null请垛，用以GC
//實(shí)際上，上面的操作已經(jīng)將要保留的元素全部前移了洽议，后面的元素都是不保留的宗收，所以要置為null來幫助gc
for (int k=newSize; k < size; k++) {
elementData[k] = null; // Let gc do its work
}
//設(shè)置size
this.size = newSize;
//判斷是否并發(fā)修改
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
modCount++;
}
return anyToRemove;
}
/**
* 刪除list中指定范圍的元素
*
* Shifts any succeeding elements to the left (reduces their index).
* This call shortens the list by {@code (toIndex - fromIndex)} elements.
* (If {@code toIndex==fromIndex}, this operation has no effect.)
*
* @throws IndexOutOfBoundsException if {@code fromIndex} or
* {@code toIndex} is out of range
* ({@code fromIndex < 0 ||
* fromIndex >= size() ||
* toIndex > size() ||
* toIndex < fromIndex})
*/
protected void removeRange(int fromIndex, int toIndex) {
modCount++;
//范圍刪除時(shí)，其實(shí)數(shù)組被分成三個(gè)部分
//分別為[保留區(qū) - 刪除區(qū) - 保留區(qū)]
//實(shí)際操作亚兄，則是計(jì)算出最后那部分保留區(qū)的長度
//利用arraycopy拷貝到第一個(gè)保留區(qū)的后面
//然后置空多余部分混稽，幫助GC
int numMoved = size - toIndex;
System.arraycopy(elementData, toIndex, elementData, fromIndex,
numMoved);
// clear to let GC do its work
int newSize = size - (toIndex-fromIndex);
for (int i = newSize; i < size; i++) {
elementData[i] = null;
}
size = newSize;
}
//最后，來看一下批量刪除這個(gè)私有方法
/**
* 批量刪除
*/
private boolean batchRemove(Collection<?> c, boolean complement) {
final Object[] elementData = this.elementData;
int r = 0, w = 0;
boolean modified = false;
try {
for (; r < size; r++)
//這里其實(shí)有可能拋異常的
//complement
//為false時(shí)审胚，則證明下標(biāo)r的元素不在刪除集合c中荚坞，所以這個(gè)時(shí)候存儲(chǔ)的是不刪除的元素
//為true時(shí)，則證明下標(biāo)r的元素在刪除集合c中菲盾，所以這個(gè)時(shí)候存儲(chǔ)的是要?jiǎng)h除的元素
//這個(gè)布爾值的設(shè)計(jì)很巧妙颓影。所以本方法可以供removeAll、retainAll兩個(gè)方法來調(diào)用
if (c.contains(elementData[r]) == complement)
elementData[w++] = elementData[r];
} finally {
// Preserve behavioral compatibility with AbstractCollection,
// even if c.contains() throws.
//所以這里要實(shí)際進(jìn)行判斷循環(huán)是否正常
if (r != size) {
//如果不正常的話懒鉴，需要挪動(dòng)元素
System.arraycopy(elementData, r,
elementData, w,
size - r);
w += size - r;
}
//如果有需要?jiǎng)h除的元素的話诡挂，則證明有一部分位置需要只為null，來幫助GC
//并且設(shè)置是否有修改的標(biāo)志為true
if (w != size) {
// clear to let GC do its work
for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size - w;
size = w;
modified = true;
}
}
return modified;
}
至此临谱，刪除相關(guān)的方法都已經(jīng)分析完畢璃俗。
有幾個(gè)比較有意思的應(yīng)用
- BitSet 標(biāo)志哪些下標(biāo)要?jiǎng)h除，哪些不刪除
- batchRemove 方法中的布爾值很巧妙
get
作為數(shù)組型的list悉默，獲取方法時(shí)比較簡單的城豁，只需要根據(jù)給定下標(biāo)，讀取指定下標(biāo)的數(shù)組元素即可抄课。
public E get(int index) {
//范圍檢查
rangeCheck(index);
return elementData(index);
}
contains
當(dāng)前l(fā)ist是否包含指定元素
/**
* 返回布爾值表示是否包含
*/
public boolean contains(Object o) {
//實(shí)際上是判斷下標(biāo)是否存在
return indexOf(o) >= 0;
}
/**
* 指定元素在list中首次出現(xiàn)的下標(biāo)唱星，不存在則返回-1
*/
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;
}
//另外，還有一個(gè)跟磨，最后一次出現(xiàn)的下標(biāo)
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;
}
clear
清空緩沖數(shù)組。
public void clear() {
//修改計(jì)數(shù) + 1
modCount++;
// clear to let GC do its work
//全部置為null抵拘，幫助GC
for (int i = 0; i < size; i++)
elementData[i] = null;
//size設(shè)置為0
size = 0;
}
以上相關(guān)方法基本都已經(jīng)介紹完畢哎榴。
總結(jié)
Array相比其他集合框架，如Map、Set之類的尚蝌，還是比較簡單的迎变。
只需要了解相關(guān)方法的應(yīng)用和原理，注意下標(biāo)越界問題飘言，以及內(nèi)部的緩沖數(shù)組是如何擴(kuò)容的氏豌，基本上就OK了。
溜了溜了热凹。有幫助的話給格子點(diǎn)個(gè)贊唄~3Q
我的博客即將入駐“云棲社區(qū)”泵喘，誠邀技術(shù)同仁一同入駐。
