Java中的List集合

gplane 發(fā)布于2019-08-19 11:14 / 2938人閱讀

摘要：接口的實現(xiàn)類表示有序的集合元素可以重復(fù)，根據(jù)索引來尋找元素，放入其中的元素的存儲順序和放入順序是一致的。包下的集合并發(fā)類與等方法裝飾的類有什么不同先講一下這個線程安全的類。

List接口的實現(xiàn)類

List表示有序的集合（元素可以重復(fù)），根據(jù)索引來尋找元素，放入其中的元素的存儲順序和放入順序是一致的。

ArrayList

0.繼承自AbstractList，擁有通用的方法如Iterator迭代器。實現(xiàn)了List接口。

1.底層是transient Object[] elementData 數(shù)組?？梢钥吹?strong>默認大小是10。

2.不同的初始化方式，有一點區(qū)別。

// 未指定,默認是10。構(gòu)造的數(shù)組大小為0，要等到放入第一個元素時才會擴容成10個。
List list1 = new ArrayList<>();

// 構(gòu)造的數(shù)組大小為0。
List list2 = new ArrayList<>(0);

// 構(gòu)造的數(shù)組大小為14
List list3 = new ArrayList<>(14);

3.數(shù)組擴容

默認初始化的內(nèi)部數(shù)組大小是10，當(dāng)放入第11個元素時會進行第一次擴容:newCapacity = oldCapacity + oldCapacity >> 1 ，也就是變成原來的1.5倍。（所以默認情況下，放入第11個元素時，擴容成15個；放入第16個元素時，擴容成22個；放入第23個元素時，擴容成33個。）

數(shù)組擴容的操作是進行數(shù)組的復(fù)制，所以擴容消耗資源，應(yīng)該盡量先指明所需的容量，來減少擴容操作。對于已經(jīng)存在的ArrayList，在放入大量元素前，可以手動進行擴容：ensureCapacity(capacity) 方法來重新設(shè)置內(nèi)部數(shù)組的大小。

4.有一個騷操作，把ArrayList轉(zhuǎn)化成對象數(shù)組：

// 調(diào)用toArray方法,傳入對象數(shù)組接收,返回Object[]數(shù)組
Object[] objects2 = appleList.toArray(new Apple[0]);
// 類型轉(zhuǎn)換
Apple[] apples3 = (Apple[]) objects2;

5.ArrayList的add(int index, Object obj)和remove(int index) / remove(Object obj)，即隨機的增加、刪除操作都會進行內(nèi)部數(shù)組的復(fù)制，所以ArrayList只適合順序插入、刪除，隨機訪問get(int index)，不適合隨機增加、刪除操作多的場景。

ArrayList總結(jié)

1.初始化時應(yīng)該指明容量，避免多次的擴容操作。如果已經(jīng)分配了容量但是不夠用，建議先手動擴容大小后再添加元素。

2.使用場景應(yīng)該是隨機查找比較多而隨機增加、刪除操作比較少的場景。

LinkedList

1.繼承自AbstractSequentialList，擁有通用的方法如iterator。實現(xiàn)List接口。實現(xiàn)Queue接口，擁有隊列的特性；實現(xiàn)Deque接口，擁有雙端隊列的特性。

2.LinkedList內(nèi)部的節(jié)點。擁有前后指針，實現(xiàn)的是雙端隊列的性質(zhì)。

內(nèi)部的私有屬性，存儲了鏈表的節(jié)點個數(shù)以及保存了鏈表的頭尾指針。

3.因為LinkedList實現(xiàn)了Queue接口、Deque接口，所以它既能作為隊列也能作為堆棧來使用。又因為實現(xiàn)了List接口，所以又是有序的Collection。這意味著它有3種數(shù)據(jù)結(jié)構(gòu)的作用，我們應(yīng)該在正確的場景下正確語義化使用，這表示我們要使用合適的接口來聲明LinedList。(注意雙端隊列Deque接口提供了傳統(tǒng)Stack的操作方法聲明，所以它可以作為堆棧Stack使用)

4.對于LinkedList的隨機訪問操作，它內(nèi)部有一個優(yōu)化。如果index<(size/2)，就從頭部開始查找；否則從尾部開始查找。

LinkedList總結(jié)

1.使用場景應(yīng)該是隨機增加、刪除操作多的情況，而隨機訪問操作少的情況。

2.LinkedList有3種數(shù)據(jù)結(jié)構(gòu)的身份，我們應(yīng)該在正確的場景下進行正確的接口聲明，并且使用與之對應(yīng)的語義化方法來操作LinkedList。我們在使用棧stack結(jié)構(gòu)的時候可以使用LinkedList，在使用隊列Queue的時候可以使用LinkedList，在使用有序集合（鏈表）的時候可以使用LinkedList。

Vector

vector作為古老的集合類，是jdk1.2之后才改為實現(xiàn)List接口的。它與ArrayList的性質(zhì)很像（2者的繼承圖是一樣的），但是其內(nèi)部方法都使用了synchronized修飾來保證線程安全，這使得對Vector的操作在多線程下變成了串行操作。要注意的是，它的實現(xiàn)是使用synchronized修飾整個方法，而不是方法內(nèi)部的某段代碼，這使得其鎖的粒度特別大，效率十分低！

Vector已經(jīng)不推薦使用了，單線程下我們建議選用ArrayList，多線程下我們建議選用java.util.concurrent包下的CopyOnWriteArray或使用Collections.synchronizedList(ArrayList list)修飾過的ArrayList。

列舉synchronized修飾的add、get操作：

1.默認初始化大小為10，擴容操作時，如果構(gòu)造時指明了增大的容量，則增加；否則默認變成原來的2倍。

Stack

Stack作為Vector的子類，可用于實現(xiàn)堆棧。但是不建議使用，而是使用Deque接口的實現(xiàn)類如LinkedList、ArrayList來替代堆棧結(jié)構(gòu)。

為什么不使用Stack，而推薦使用LinkedList呢？原因還是因為它繼承自Vector，所以它的棧相關(guān)的操作也是synchronized修飾的！所以單線程下，我們還是推薦使用LinkedList所能實現(xiàn)的棧結(jié)構(gòu)；多線程下則可以考慮java.util.concurrent包下的ConcurrentLinkedDeque所能實現(xiàn)的并發(fā)棧結(jié)構(gòu)或Collections.synchronizedList（LinkedList list）修飾的LinkedList。

當(dāng)然，我們也可以使用ArrayDeque類！

講講List集合對應(yīng)的并發(fā)類

ArrayList對應(yīng)的，java.util.concurrent.CopyOnWriteArrayList類和Collections.synchronizedList(ArrayList list)所修飾的類。

LinkedList對應(yīng)的，就是Collections.synchronizedList(LinkedList list)所修飾的類。

要注意的是，到了并發(fā)集合（java.util.concurrent包）這一塊，都是按照接口性質(zhì)設(shè)置的并發(fā)類。所以應(yīng)該講成List接口對應(yīng)的并發(fā)類是java.util.concurrent.CopyOnWriteArrayList類。

java.util.concurrent包下的集合并發(fā)類與Collections.synchronizedList()等方法裝飾的類有什么不同？

先講一下Vector這個線程安全的List類。其線程安全的實現(xiàn)方式是對所有操作都加上了synchronized關(guān)鍵字，其鎖的粒度是整個方法，這種方式嚴(yán)重影響效率，使得程序串行進行。

而Collections.synchronizedList等方法，是采用了裝飾器的模式來返回一個包裝類。以Collections.synchronizedList(ArrayList list)為例，返回的包裝類的部分操作如add、get、remove方法是在方法內(nèi)部的代碼塊加上了synchronized關(guān)鍵字，這使得鎖的粒度較?。?p>

而java.util.concurrent包下的CopyOnWriteArrayList，其寫操作是寫時復(fù)制（就和名字一樣），通過可重入鎖顯式加鎖來達到同步互斥的目的。而且每次新加入元素，都復(fù)制原數(shù)組一份，然后對新數(shù)組進行增加操作，然后在替換原引用，這就達到了寫入分離。（刪除操作同樣的道理）這里很重要，下面要講一下get方法！

get方法沒有任何加鎖同步操作！這里就很有趣了！根據(jù)對寫入操作的分析，如果并發(fā)時一個線程在寫入，另外一個線程在讀取，那么寫入未完成之前，讀取操作所讀到的數(shù)組是原先的數(shù)組！

所以，這正是CopyOnWrite容器的缺點：CopyOnWrite只能保證數(shù)據(jù)最終的一致性，不能保證數(shù)據(jù)的實時一致性。并發(fā)情況下，某個線程讀取到的數(shù)據(jù)可能是舊數(shù)據(jù)！

其次，對內(nèi)存有消耗，如果多個線程并發(fā)執(zhí)行，那么數(shù)組復(fù)制時需要新數(shù)組來保存，就占用了2份內(nèi)存！如果數(shù)組占用的內(nèi)存較大，就會引發(fā)頻繁的垃圾回收行為，降低性能。

所以對于CopyOnWrite容器來說，它適合讀操作頻繁，而寫操作少的并發(fā)場景，比如說數(shù)據(jù)的緩存！

List集合圖

下面對Collection集合下的List有序集合進行一個類圖的整合：

可以看到的是ArrayList和Vector的繼承圖是一致的！它們的區(qū)別就是內(nèi)部實現(xiàn)不同，所以我們可以大膽地放棄Vector類了。而LinkedList較之于ArrayList，多實現(xiàn)了Deque接口，這使得它不僅具備了List的特性，還擁有雙端隊列的特性，可以拿來做棧、隊列等結(jié)構(gòu)！

Collection接口繼承自Iterable，這意味著所有的集合類都可以返回迭代器進行遍歷。