Java中的List集合

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

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

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

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

ArrayList

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

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

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

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

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

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

3.數(shù)組擴(kuò)容

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

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

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

// 調(diào)用toArray方法,傳入對(duì)象數(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)，即隨機(jī)的增加、刪除操作都會(huì)進(jìn)行內(nèi)部數(shù)組的復(fù)制，所以ArrayList只適合順序插入、刪除，隨機(jī)訪問get(int index)，不適合隨機(jī)增加、刪除操作多的場(chǎng)景。

ArrayList總結(jié)

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

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

LinkedList

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

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

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

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

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

LinkedList總結(jié)

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

2.LinkedList有3種數(shù)據(jù)結(jié)構(gòu)的身份，我們應(yīng)該在正確的場(chǎng)景下進(jìn)行正確的接口聲明，并且使用與之對(duì)應(yīng)的語(yǔ)義化方法來(lái)操作LinkedList。我們?cè)谑褂脳tack結(jié)構(gòu)的時(shí)候可以使用LinkedList，在使用隊(duì)列Queue的時(shí)候可以使用LinkedList，在使用有序集合（鏈表）的時(shí)候可以使用LinkedList。

Vector

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

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

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

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

Stack

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

List集合圖

下面對(duì)Collection集合下的List有序集合進(jìn)行一個(gè)類圖的整合：

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

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