分析目的
? ? ? ? 接觸了 java 兩年，雖然在2015年閱讀了一遍 Collection 接口下面的各種實(shí)現(xiàn)。但是最近還是想重溫一下 jdk 的源代碼，同時也想用筆記的方式記錄和分享一下學(xué)習(xí)歷程。
? ? ? ? 目前初步想把 Collection 和 Map 的源代碼都重新閱讀分析一遍，以便加深印象理解。其實(shí)這也是面試中最常見的問題之一，例如ArratList是如何實(shí)現(xiàn)的，ArrayList 和 LinkedList 有什么區(qū)別，常見數(shù)組擴(kuò)容的深拷貝和淺拷貝等知識點(diǎn)。本文先講 ArrayList ，主要圍繞著實(shí)現(xiàn)原理，然后從構(gòu)造函數(shù)，到增刪是如何實(shí)現(xiàn)的。
簡介：
????1. ArrayList 是基于數(shù)組實(shí)現(xiàn)的一個隊(duì)列，因?yàn)榛跀?shù)組，但是相對來說，他比數(shù)組更為靈活，因?yàn)榭梢詣討B(tài)擴(kuò)容，但是效率不如數(shù)組（知識點(diǎn)）。
????2. ArrayList 實(shí)現(xiàn)了 RandmoAccess 接口，即提供了隨機(jī)訪問功能。RandmoAccess 是 java 中用來被List 實(shí)現(xiàn)，為 List 提供快速訪問功能的。在 ArrayList 中，我們即可以通過元素的序號快速獲取元素對象，這就是快速隨機(jī)訪問。其實(shí)就是快速從索引來訪問。
? ? 3.ArrayList 實(shí)現(xiàn)了Cloneable接口，即覆蓋了函數(shù)clone()，能被克隆。注意：這里有個知識點(diǎn)是java的深拷貝和淺拷貝，這里需要追蹤到Arrays.copy方法。不過這個方法是個native的，需要最終到c++的實(shí)現(xiàn)。這點(diǎn)應(yīng)該也是大廠的面試題之一（知識點(diǎn)）。
? ? 4.ArrayList 實(shí)現(xiàn)java.io.Serializable接口，這意味著ArrayList支持序列化，能通過序列化去傳輸。
? ? 5.ArrayList是線程不安全的，這里經(jīng)常有對比的就是同一家族下的vector（知識點(diǎn)）。
? ? ? ? 首先看結(jié)構(gòu)：
構(gòu)造函數(shù)
1.無參構(gòu)造
????public ArrayList() {
????????????this.elementData =DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
? ? ? ?}
? ? ????這里說明，默認(rèn)構(gòu)造容量為10的一個arraylist,但是要注意，實(shí)際上這里的長度是空的，繼續(xù)往下看，稍后分析。
2.初始化指定容量的List
首先如果制定的長度大于0，那么初始化一個指定構(gòu)造函數(shù)內(nèi)，參數(shù)大小容量的 object 數(shù)組。
如果參數(shù)為0，那么設(shè)置list置為長度為0的 object 數(shù)組。
如果指定長度小于0，那么 new IllegalArgumentException（）異常。
3.接收一個 Collection 作為參數(shù)，構(gòu)造一個List（），這里也說明，只要實(shí)現(xiàn)了 Collection 接口的容器，都可以作為參數(shù)，傳遞給 ArrayList() ;
如果當(dāng)前集合長度不為0，那么調(diào)用 Arrays.copyOf（）方法，將參數(shù)，復(fù)制給當(dāng)前數(shù)組。
否則，將當(dāng)前數(shù)組賦值為空的 object 數(shù)組。
這是基礎(chǔ)的三個構(gòu)造函數(shù)。
add方法
? ? ? ? add 方法，共有兩個 public 方法，供我們調(diào)用。方法一接受指定類型的一個元素，方法二在指定的元素索引處增加元素，然后后續(xù)的元素索引分別增加1。
方法1
????????首先分析方法1，增加一個指定類型的元素。（這里也可以稱為范型，是 jdk1.5 新增加的特性）。
????????這里調(diào)用私有的 private add（）方法，首先判斷當(dāng)前的size，和 List 內(nèi)的元素長度是否相等，這里假如是第一次添加時，如果條件成立那么進(jìn)行擴(kuò)容，或者說是容器的長度存儲到數(shù)組容量的當(dāng)前最大索引數(shù)時。
接下來看擴(kuò)容操作，grow（）方法做了哪些事情。
? ? 首先當(dāng)前容器的 size 增加1。
然后進(jìn)行數(shù)組的 copy 方法，
但是 copy 方法要注意的就是另一個方法，newCapacity（），
????????這里照應(yīng)了，第一個無參的構(gòu)造函數(shù)，是在添加元素時，才會選擇初始化10個長度的數(shù)組，這也是優(yōu)化代碼的一個小技巧。同時 newCapacity（）方法，返回新的數(shù)組長度。
????下面的return之前會判斷長度是否為數(shù)組的最大長度-8，這里以前的jdk是沒有-8操作的，后續(xù)可以解釋這里為什么-8，當(dāng)然也可以百度這個問題。最主要的就是要記住，ArrayList的最大長度就是Integer.MAX_VALUE-8，就是整型最大長度-8。
再擴(kuò)容完之后，接下來介紹 Arrays.copyOf（）方法。? ??
最終會跟到 native 方法，arraycopy（）
arraycopy,共需要五個參數(shù)
Object src : 原數(shù)組
int srcPos : 從元數(shù)據(jù)的起始位置開始
Object dest : 目標(biāo)數(shù)組
int destPos : 目標(biāo)數(shù)組的開始起始位置
int length? : 要copy的數(shù)組的長度
例如 ：
有一個數(shù)組數(shù)據(jù) byte[] ?srcBytes = new byte[]{1,2,3,4,5,6,7,8,9,10}; ?// 源數(shù)組
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? byte[] destBytes = new byte[5]; // 目標(biāo)數(shù)組
我們使用 System.arraycopy 進(jìn)行轉(zhuǎn)換 (copy) ，System.arrayCopy(srcBytes,0,destBytes?,0,5)
上面這段代碼就是 : 創(chuàng)建一個一維空數(shù)組,數(shù)組的總長度為 10位,然后將srcBytes源數(shù)組中 從0位 到 第5位之間的數(shù)值 copy 到 destBytes 目標(biāo)數(shù)組中,在目標(biāo)數(shù)組的第0位開始放置.
那么這行代碼的運(yùn)行效果應(yīng)該是 1,2,3,4,5 。
注意：這里 ArrayList 中目標(biāo)數(shù)組的長度的長度，是永遠(yuǎn)大于源數(shù)組的，因?yàn)樾枰獙⒃磾?shù)組的所有元素copy到目標(biāo)數(shù)組中，然后返回新的數(shù)組。
接下來，將新的元素填充返回新的數(shù)組結(jié)構(gòu)中,然后 size+1 。如果添加中沒有任何異常發(fā)生，則默認(rèn)返回boolean 為 true 的結(jié)果。
方法2
????????方法2為，添加元素在數(shù)組的指定索引位置。共有兩個參數(shù)，參數(shù)1，int 值為 List 的索引，參數(shù)二，為需要添加的元素。
????????這里可以理解為插隊(duì)。比如你去火車站排隊(duì)，假如你的車要走了，你很急需要插隊(duì)。這時候你可以直接跑到隊(duì)伍前面，這時候后面的所有人就都要往后排一個人出去。
首先這里判斷數(shù)組內(nèi)的實(shí)際元素數(shù)量，和數(shù)組容量的size是否相等。如果相等，則進(jìn)行擴(kuò)容操作。和上面講解的擴(kuò)容操作，做了一件事情。
這里注意一點(diǎn)就是不要把，size 和 this.elementData.length 混淆。
比如：new object（）[10]?
那么 size 為10，但是假如你add 5個元素之后，this.elementData.length 為5
????????在前面的基礎(chǔ)一些校驗(yàn)和判斷相關(guān)操作完成后，開始真的數(shù)組添加操作，實(shí)際上就是這一句話做了實(shí)際的事情。
? ?????這里的 arraycopy 就是說的插隊(duì)操作，每個元素，從 elementData 的 index 需要插入的位置開始截取，然后從 index+1 處開始復(fù)制。在復(fù)制完之后，將新的元素插入到 index。
remove方法
? ? 方法1? ??
????????首先 Objects.checkIndex(index, size); 這里要校驗(yàn)，刪除的index是否合法，例如數(shù)組長度為10，你要刪除的 index 為12，這里就會拋出異常。
然后將要刪除的元素保存起來。在刪除成功之后，會把舊的 value return 回去。
開始真正的刪除動作
????????這里繼續(xù)調(diào)用 System.arraycopy（）方法，從原來需要刪除的 index+1 開始截取，復(fù)制到原來 index的位置。通俗點(diǎn)理解，就是排隊(duì)時候，前面有一個人因?yàn)橛惺虑樽吡耍@樣你們后面每個人則可以向前多走一個人的距離，然后隊(duì)伍最后面設(shè)置為 null 。就完成了刪除操作。
?方法2
? ? ? ? 刪除容器內(nèi)指定的元素,
????????????首先這里 remove 的元素是否為空，如果為空。則找到數(shù)組內(nèi)為空的元素，并且 beak 出去，，同時i變量記錄下了索引。注意：這里也說明，ArrayList 是可以存儲 null 的。其實(shí)在數(shù)組沒有填充滿時，存儲的就是 null ，這里只是加以說明一下。此時，else 內(nèi)只是找到相同的元素，同樣返回索引。然后進(jìn)行刪除。
接下來看具體的刪除操作
這里的 fastRemove（快速刪除），是怎樣快速刪除的呢？具體看代碼來分析。
????????其實(shí)是同樣的 System.arraycopy() 方法,將當(dāng)前元素的后面所有元素，從當(dāng)前指定索引數(shù)開始復(fù)制。并將最后一個元素內(nèi)從置為null。
總結(jié)：
????????ArrayList 大部分都圍繞著 arraycopy 方法來實(shí)現(xiàn)。其實(shí)就是對數(shù)組的一種快速操作的方法。只要圍繞著這一點(diǎn)，理解 ArrayList 其實(shí)還是不難的，只要對方法進(jìn)行足夠細(xì)致的拆分。這樣就像堆積木一樣，得以足夠的復(fù)用。這里我也只是做到拋磚引玉的作用，因?yàn)檫€有很多的方法沒有講解到，但是道理都是相似的。一切都是圍繞著一個主題，就是數(shù)組的快速操作，這樣理解起來就不難了。
? ? ? ? 想要學(xué)習(xí)的透徹，一定要自己動手根據(jù)理解寫一份代碼出來?。。?/p>
附注：
? ? ? ? 我一直覺得自己是個小白，從自己的角度盡可能細(xì)致的去分析。希望能給大家還有我自己帶來一些收獲。
