【線下技術(shù)沙龍】11月23日，多云時(shí)代開啟企業(yè)業(yè)務(wù)新高度，安全如何與時(shí)俱進(jìn)？
一、介紹
先回顧一下List的框架圖
由圖中的繼承關(guān)系，可以知道，ArrayList、LinkedList、Vector、Stack都是List的四個(gè)實(shí)現(xiàn)類。
AbstractList是一個(gè)抽象類，它繼承于AbstractCollection。AbstractList實(shí)現(xiàn)List接口中除size()、get(int location)之外的函數(shù)。
AbstractSequentialList 是一個(gè)抽象類，它繼承于AbstractList。AbstractSequentialList 實(shí)現(xiàn)了“鏈表中，根據(jù)index索引值操作鏈表的全部函數(shù)”。
ArrayList 是一個(gè)數(shù)組隊(duì)列，相當(dāng)于動(dòng)態(tài)數(shù)組。它由數(shù)組實(shí)現(xiàn)，隨機(jī)訪問效率高，隨機(jī)插入、隨機(jī)刪除效率低。
LinkedList 是一個(gè)雙向鏈表。它也可以被當(dāng)作堆棧、隊(duì)列或雙端隊(duì)列進(jìn)行操作。LinkedList隨機(jī)訪問效率低，但隨機(jī)插入、隨機(jī)刪除效率低。
Vector 是矢量隊(duì)列，和ArrayList一樣，它也是一個(gè)動(dòng)態(tài)數(shù)組，由數(shù)組實(shí)現(xiàn)。但是ArrayList是非線程安全的，而Vector是線程安全的。
Stack 是棧，它繼承于Vector。它的特性是：先進(jìn)后出(FILO, First In Last Out)。
二、性能測(cè)試
在對(duì)ArrayList、LinkedList、Vector、Stack進(jìn)行比較之前，我們先來對(duì)他們進(jìn)行一個(gè)性能測(cè)試，結(jié)合源碼和測(cè)試結(jié)果來對(duì)ArrayList、LinkedList、Vector、Stack進(jìn)行詳細(xì)的分析。
得到的結(jié)果如下
根據(jù)結(jié)果，可以很明顯的看出ArrayList、LinkedList、Vector、Stack的性能有很大的區(qū)別。
讀?。篈rrayList > Vector > Stack > LinkedList
插入：LinkedList > Vector > ArrayList > Stack
刪除：LinkedList > Vector > ArrayList > Stack
三、插入的分析
LinkedList
從中，我們可以看出：通過add(int index, E element)向LinkedList插入元素時(shí)。先是在雙向鏈表中找到要插入節(jié)點(diǎn)的位置index;找到之后，再插入一個(gè)新節(jié)點(diǎn)。
雙向鏈表查找index位置的節(jié)點(diǎn)時(shí)，有一個(gè)加速動(dòng)作：若index < 雙向鏈表長(zhǎng)度的1/2，則從前向后查找; 否則，從后向前查找。
ArrayList
在這里面有一個(gè)非常耗時(shí)的操作
System.arraycopy(elementData, index, elementData, index + 1, size - index);
該方法被標(biāo)記了native，調(diào)用了系統(tǒng)的C/C++代碼，在JDK中是看不到的，但在openJDK中可以看到其源碼。
該函數(shù)實(shí)際上最終調(diào)用了C語言的memmove()函數(shù)，因此它可以保證同一個(gè)數(shù)組內(nèi)元素的正確復(fù)制和移動(dòng)，比一般的復(fù)制方法的實(shí)現(xiàn)效率要高很多，很適合用來批量處理數(shù)組。Java強(qiáng)烈推薦在復(fù)制大量數(shù)組元素時(shí)用該方法，以取得更高的效率。
Vector
可以看到Vector和ArrayList是一樣的，都調(diào)用了System.arraycopy。由于Stack和繼承與Vector，就不仔細(xì)分析了。
四、查找的分析
LinkedList
從中，我們可以看出：通過get(int index)獲取LinkedList第index個(gè)元素時(shí)。先是在雙向鏈表中找到要index位置的元素;找到之后再返回。
雙向鏈表查找index位置的節(jié)點(diǎn)時(shí)，有一個(gè)加速動(dòng)作：若index < 雙向鏈表長(zhǎng)度的1/2，則從前向后查找; 否則，從后向前查找。
ArrayList
我們可以看到ArrayList直接返回?cái)?shù)組中index位置的元素，而不需要像LinkedList一樣進(jìn)行查找。
通過源碼發(fā)現(xiàn)Vector和Stack的操作方式和ArrayList一樣，這里就不詳細(xì)分析了。
五、刪除的分析
LinkedList
由于刪除了某一節(jié)點(diǎn)因此調(diào)整相應(yīng)節(jié)點(diǎn)的前后指針信息，如下：
清空預(yù)刪除節(jié)點(diǎn)：
交給gc完成資源回收，刪除操作結(jié)束。
與ArrayList比較而言，LinkedList的刪除動(dòng)作不需要“移動(dòng)”很多數(shù)據(jù)，從而效率更高。
ArrayList
恩，又是調(diào)用了System.arraycopy。
六、結(jié)論
操作ArrayListLinkedListVectorStack讀取O(1)O(n)O(1)O(1)插入O(n)O(1)O(n)O(n)刪除O(n)O(1)O(n)O(n)
ArrayList(實(shí)現(xiàn)動(dòng)態(tài)數(shù)組)，查詢快(隨意訪問或順序訪問)，增刪慢。整體清空快，線程不同步(非線程安全)。數(shù)組長(zhǎng)度是可變的百分之五十延長(zhǎng)
LinkedList(實(shí)現(xiàn)鏈表)，查詢慢，增刪快。
Vector(實(shí)現(xiàn)動(dòng)態(tài)數(shù)組)，都慢，被ArrayList替代。長(zhǎng)度任意延長(zhǎng)。線程安全(同步的類，函數(shù)都是synchronized)
Stack(實(shí)現(xiàn)堆棧)繼承于Vector，先進(jìn)后出。
所以，快速訪問ArrayList，快速增刪LinkedList，單線程都可以用，多線程只能用同步類Vector
【責(zé)任編輯：武曉燕 TEL：（010）68476606】