寫在前面
Java的集合框架完備而又牛叉墩虹，其實(shí)現(xiàn)值得我這樣的小白去一探究竟航厚。當(dāng)然了昆码，在這我暫時(shí)不會(huì)很深入的去閱讀整個(gè)集合框架，而是通過一兩個(gè)實(shí)現(xiàn)去摸一下他的套路邻储，希望最終我能摸到點(diǎn)集合框架的門路赋咽。在本文中，我將會(huì)帶你閱讀：
- ArrayList內(nèi)部的基本實(shí)現(xiàn)
- add()方法
- get()方法
是的吨娜，你沒看錯(cuò)脓匿，就看這三個(gè)……當(dāng)然了，ArrayList遠(yuǎn)不止如此宦赠，但現(xiàn)在我只會(huì)去探究一下其基本實(shí)現(xiàn)陪毡。
基本實(shí)現(xiàn)
首先回憶一下平時(shí)我們是如何初始化一個(gè)ArrayList的：
List<String> list = new ArrayList<>();
得益于Java的多態(tài)使得我們可以寫出如上的代碼，那么無參的ArrayList的構(gòu)造函數(shù)是啥樣的呢勾扭？
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
接下來看看他是怎么初始化的毡琉，左邊那個(gè)值是個(gè)什么東西，右邊那個(gè)值又是個(gè)什么東西妙色。
首先是左邊：
/**
* The array buffer into which the elements of the ArrayList are stored.
* The capacity of the ArrayList is the length of this array buffer. Any
* empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
* will be expanded to DEFAULT_CAPACITY when the first element is added.
*/
transient Object[] elementData;// non-private to simplify nested class access
如果用transient聲明一個(gè)實(shí)例變量桅滋，當(dāng)對(duì)象存儲(chǔ)時(shí)，它的值不需要位置身辨。換句話說就是丐谋，用transient關(guān)鍵字標(biāo)記的成員變量不參與序列化的過程。
回過頭來再看看煌珊，這是個(gè)Object的數(shù)組号俐，這就是ArrayList元素被存儲(chǔ)的地方。ArrayList的容量就是這個(gè)數(shù)組的長(zhǎng)度定庵。再來看看上面那個(gè)構(gòu)造函數(shù)的右邊具體是個(gè)什么東西：
/**
* Shared empty array instance used for default sized empty instances. We
* distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
* first element is added.
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
從上面的代碼可以看出來就是個(gè)空的Object數(shù)組吏饿，果然很符合空的ArrayList（笑）踪危。接下來解析代碼將會(huì)在我們調(diào)用了無參的構(gòu)造函數(shù)的基礎(chǔ)上去分析，那么讓我們通過幾個(gè)常用的方法去看看ArrayList內(nèi)部究竟是如何使用這個(gè)Object數(shù)組的找岖。
add()
/**
* Appends the specified element to the end of this list.
*
* @param e element to be appended to this list
* @return <tt>true</tt> (as specified by {@link Collection#add})
*/
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
向list的末尾追加一個(gè)指定的元素陨倡，第一行代碼看樣子和ArrayList的尺寸有點(diǎn)關(guān)系，第二句代碼很明顯就是追加元素的操作了许布。那么回過頭來兴革，看看第一句代碼究竟干了啥：
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
首先從名字上分析分析……確定內(nèi)部的容量，果然是和尺寸有關(guān)系的蜜唾≡忧看下具體的代碼，如果elementData等于DEFAULTCAPACITY_EMPTY_ELEMENTDATA袁余，那么會(huì)從minCapacity和DEFAULT_CAPACITY中比較大的值中挑一個(gè)出來賦給minCapacity擎勘，接著調(diào)用ensureExplicitCapacity方法
首先DEFAULTCAPACITY_EMPTY_ELEMENTDATA這個(gè)在前面的空構(gòu)造函數(shù)中已經(jīng)看到過了，如果你調(diào)用的是空的構(gòu)造函數(shù)颖榜，那么在這里elementData的值明顯是和這個(gè)值相等的棚饵。那么看看DEFAULT_CAPACITY是個(gè)啥東西：
/**
* Default initial capacity.
*/
private static final int DEFAULT_CAPACITY = 10;
很明顯就是個(gè)常數(shù)值，很明顯掩完，當(dāng)你調(diào)用空的構(gòu)造函數(shù)創(chuàng)建一個(gè)ArrayList時(shí)噪漾，其內(nèi)部Object數(shù)組是一個(gè)空值，當(dāng)你調(diào)用add()方法時(shí)(add(E e,int index)方法稍有不同)且蓬，他會(huì)先判斷你的ArrayList是否是一個(gè)空值欣硼，如果是的話，它會(huì)給minCapacity賦上10的值然后調(diào)用ensureExplicitCapacity()方法恶阴，那么來看看那個(gè)方法：
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
第一行代碼可以先拋開诈胜。if里判斷minCapacity的值是否大于elementData的長(zhǎng)度，那么看一下grow這個(gè)方法的代碼：
/**
* Increases the capacity to ensure that it can hold at least the
* number of elements specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity
*/
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
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:
elementData = Arrays.copyOf(elementData, newCapacity);
}
代碼不多冯事，一行一行看過來焦匈。第一行拿到內(nèi)部對(duì)象數(shù)組的長(zhǎng)度，第二行計(jì)算出新的容量昵仅。計(jì)算方式是：舊容量+舊容量/2括授，也就是每次擴(kuò)充當(dāng)前內(nèi)部對(duì)象數(shù)組長(zhǎng)度的一半。當(dāng)然了岩饼，如果剛開始你的內(nèi)部對(duì)象數(shù)組的長(zhǎng)度是0的話荚虚，那你得出的值也還是0。那么newCapacity-minCapacity的值將會(huì)小于0籍茧，那么nweCapacity的值將會(huì)是10版述。之后便是調(diào)用Arrays.copyOf方法，這個(gè)方法最終會(huì)調(diào)用一個(gè)native方法實(shí)現(xiàn)將指定的數(shù)組拷貝到一個(gè)擁有新的尺寸的數(shù)組中寞冯，那么整個(gè)ensureCapacityInternal方法咱就過了一遍了渴析。
在調(diào)用無參構(gòu)造函數(shù)的情況下晚伙，內(nèi)部的object數(shù)組尺寸是0，在調(diào)用了一系列方法之后構(gòu)造了一個(gè)值為10的數(shù)組出來俭茧，最終將值插入相應(yīng)的位置咆疗。
get()
/**
* Returns the element at the specified position in this list.
*
* @param index index of the element to return
* @return the element at the specified position in this list
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
老規(guī)矩，一行一行來看首先第一行：
private void rangeCheck(int index) {
if (index < 0 || index >= this.size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
邊界檢查母债，小于0或者大于內(nèi)部數(shù)組的長(zhǎng)度就報(bào)個(gè)越界的錯(cuò)誤午磁。
之后就是從數(shù)組取出這個(gè)下標(biāo)的值。毡们。沒啥好說的迅皇。。數(shù)組取個(gè)值衙熔。登颓。。
remove()
/**
* Removes the element at the specified position in this list.
* Shifts any subsequent elements to the left (subtracts one from their
* indices).
*
* @param index the index of the element to be removed
* @return the element that was removed from the list
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
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
return oldValue;
}
第一行仍舊是邊界檢查红氯。modCount++還是忽視……之后取出對(duì)應(yīng)下標(biāo)的元素框咙，拿到需要移動(dòng)的元數(shù)量，如果數(shù)量大于0痢甘，調(diào)用arraycopy將內(nèi)部數(shù)組elementData中index之后的元素統(tǒng)統(tǒng)向前移動(dòng)一個(gè)位置扁耐。之后將內(nèi)部數(shù)組的最后一個(gè)位置置空，方便gc去回收這塊內(nèi)存产阱。在Java中強(qiáng)引用的內(nèi)存無法被回收，所以需要我們手動(dòng)的將在邏輯上已刪除的元素置空块仆。
