一個(gè) List 是一個(gè)元素有序的、可以重復(fù)矩乐、可以為 null 的集合花嘶。
Java 集合框架中最常使用的幾種 List 實(shí)現(xiàn)類是 ArrayList，LinkedList 和 Vector柿菩。
在各種 List 中，最好的做法是以 ArrayList 作為默認(rèn)選擇雨涛。 當(dāng)插入枢舶、刪除頻繁時(shí)，使用 LinkedList替久，Vector 總是比 ArrayList 慢凉泄，所以要盡量避免使用它，具體實(shí)現(xiàn)后續(xù)文章介紹蚯根。
ArrayList
ArrayList應(yīng)該是接觸集合框架的人第一個(gè)遇到的數(shù)據(jù)結(jié)構(gòu)后众，記得老師當(dāng)年把它叫做可變長(zhǎng)度的數(shù)組，接下來(lái)就布置了作業(yè)，讓大家自己實(shí)現(xiàn)可擴(kuò)展長(zhǎng)度的數(shù)組型數(shù)據(jù)結(jié)構(gòu)蒂誉。
當(dāng)時(shí)的我是這么做的：
首先需要幾個(gè)標(biāo)記：總長(zhǎng)度totalNum教藻，當(dāng)前長(zhǎng)度currentNum。然后總長(zhǎng)度總要比實(shí)際長(zhǎng)度的最大值大于一右锨，當(dāng)?shù)扔?時(shí)自動(dòng)擴(kuò)容（其實(shí)就是new一個(gè)新的數(shù)組并拷貝）括堤。作為課代表的自己覺(jué)得也是有點(diǎn)穩(wěn)。
今天我們來(lái)看看ArrayList是怎么實(shí)現(xiàn)的绍移。
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
構(gòu)造函數(shù)中悄窃，將elementData初始化為空，這個(gè)elementData就是其中的一個(gè)數(shù)組了object[] elementData>蹂窖，無(wú)參構(gòu)造方法構(gòu)造的ArrayList的容量默認(rèn)為10轧抗。
private static final int DEFAULT_CAPACITY = 10
接下來(lái)我們直接看add()方法.
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
在執(zhí)行add方法時(shí), 首先調(diào)用了ensureCapacityInternal方法, 我們可以猜到這個(gè)方法是用于數(shù)組的擴(kuò)充的, 接下來(lái)才將傳入的元素放到size處。
跟進(jìn)ensureCapacityInternal恼策，在方法中有各種的判斷鸦致，最后我們可以看到這樣的代碼
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);
}
這里的grow函數(shù)就是實(shí)現(xiàn)數(shù)組擴(kuò)容的方法。
我們看到涣楷，每當(dāng)向數(shù)組中添加元素時(shí)分唾，都要去檢查添加后元素的個(gè)數(shù)是否會(huì)超出當(dāng)前數(shù)組的長(zhǎng)度，如果超出狮斗，數(shù)組將會(huì)進(jìn)行擴(kuò)容绽乔，以滿足添加數(shù)據(jù)的需求，擴(kuò)容數(shù)量為oldCapacity的0.5倍碳褒，即右移1位折砸。數(shù)組擴(kuò)容通過(guò)一個(gè)公開(kāi)的方法ensureCapacity(int minCapacity)來(lái)實(shí)現(xiàn)。在實(shí)際添加大量元素前沙峻，我也可以使用ensureCapacity來(lái)手動(dòng)增加ArrayList實(shí)例的容量睦授，以減少遞增式再分配的數(shù)量。
這里的Arrays.copyOf()是復(fù)制數(shù)組的操作, 會(huì)消耗較多的時(shí)間
此外ArrayList還給我們提供了將底層數(shù)組的容量調(diào)整為當(dāng)前列表保存的實(shí)際元素的大小的功能摔寨。它可以通過(guò)trimToSize方法來(lái)實(shí)現(xiàn)去枷。代碼如下：
public void trimToSize() {
modCount++;
int oldCapacity = elementData.length;
if (size < oldCapacity) {
elementData = Arrays.copyOf(elementData, size);
}
}
由于elementData的長(zhǎng)度會(huì)被拓展，size標(biāo)記的是其中包含的元素的個(gè)數(shù)是复。所以會(huì)出現(xiàn)size很小但elementData.length很大的情況删顶，將出現(xiàn)空間的浪費(fèi)。trimToSize將返回一個(gè)新的數(shù)組給elementData淑廊，元素內(nèi)容保持不變逗余，length和size相同，節(jié)省空間季惩。
Vector
和ArrayList不同录粱，Vector中的操作是線程安全的腻格。其方法大多數(shù)都含有synchronized 關(guān)鍵字, 在多編程操作是建議使用，但是開(kāi)銷略大
來(lái)看看vector的add方法中的增長(zhǎng)方式
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
capacityIncrement : oldCapacity);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}
這里的capacityIncrement 為增長(zhǎng)因子 , 當(dāng)增長(zhǎng)因子大于0時(shí) , 每次擴(kuò)充的長(zhǎng)度為增長(zhǎng)因子 , 當(dāng)為0是 , 默認(rèn)擴(kuò)充為原數(shù)組的2倍.
LinkedList
LinkedList 是一個(gè)雙鏈表,在添加和刪除元素時(shí)具有比ArrayList更好的性能.但在get與set方面弱于ArrayList.當(dāng)然,這些對(duì)比都是指數(shù)據(jù)量很大或者操作很頻繁的情況下的對(duì)比啥繁。
雙鏈表的插入操作和刪除操作, 相對(duì)于數(shù)組來(lái)說(shuō)要簡(jiǎn)單的多 , 只需要挪動(dòng)兩個(gè)指針即可荒叶，但是改數(shù)據(jù)結(jié)構(gòu)相比于ArrayList更占用內(nèi)存，因?yàn)樾枰喑鰞蓚€(gè)指針來(lái)作為前指針和后指針來(lái)維持?jǐn)?shù)據(jù)結(jié)構(gòu)
它還實(shí)現(xiàn)了 Queue 接口,該接口比List提供了更多的方法,包括 offer(),peek(),poll()等方法.
當(dāng)多個(gè)線程對(duì)同一個(gè)集合進(jìn)行操作的時(shí)候输虱，某線程訪問(wèn)集合的過(guò)程中，該集合的內(nèi)容被其他線程所改變(即其它線程通過(guò)add脂凶、remove宪睹、clear等方法，改變了modCount的值)蚕钦；這時(shí)亭病，就會(huì)拋出ConcurrentModificationException異常，產(chǎn)生fail-fast事件嘶居。
這種情況經(jīng)常發(fā)生在請(qǐng)求數(shù)據(jù)之后 , 對(duì)數(shù)據(jù)本身進(jìn)行新一輪的操作. 如果線程沒(méi)有主意好的話 , 會(huì)拋出異常: ConcurrentModificationException. 以前我直接會(huì)在一開(kāi)始就將數(shù)據(jù)結(jié)構(gòu)選擇為CopyOnWriteArrayList , 待會(huì)來(lái)看看這個(gè)數(shù)據(jù)結(jié)構(gòu)到底是什么罪帖。
CopyOnWriteArrayList
CopyOnWrite容器即寫(xiě)時(shí)復(fù)制的容器。
通俗的理解是當(dāng)我們往一個(gè)容器添加元素的時(shí)候邮屁，不直接往當(dāng)前容器添加整袁，而是先將當(dāng)前容器進(jìn)行Copy，復(fù)制出一個(gè)新的容器佑吝，然后新的容器里添加元素坐昙，添加完元素之后，再將原容器的引用指向新的容器芋忿。這樣做的好處是我們可以對(duì)CopyOnWrite容器進(jìn)行并發(fā)的讀炸客，而不需要加鎖，因?yàn)楫?dāng)前容器不會(huì)添加任何元素戈钢。所以CopyOnWrite容器也是一種讀寫(xiě)分離的思想痹仙，讀和寫(xiě)不同的容器。
既然是在增刪是不會(huì)拋出異常殉了，我們來(lái)看看它的add方法以及其它會(huì)引起數(shù)組長(zhǎng)度變化的方法都做了什么
public boolean add(E e) {
synchronized (lock) {
Object[] elements = getArray();
int len = elements.length;
Object[] newElements = Arrays.copyOf(elements, len + 1);
newElements[len] = e;
setArray(newElements);
return true;
}
}
public E remove(int index) {
synchronized (lock) {
Object[] elements = getArray();
int len = elements.length;
E oldValue = get(elements, index);
int numMoved = len - index - 1;
if (numMoved == 0)
setArray(Arrays.copyOf(elements, len - 1));
else {
Object[] newElements = new Object[len - 1];
System.arraycopy(elements, 0, newElements, 0, index);
System.arraycopy(elements, index + 1, newElements, index,
numMoved);
setArray(newElements);
}
return oldValue;
}
}
我們可以看到开仰，在添加與移除的方法體中都是用到了synchronized關(guān)鍵字， 也就是同一時(shí)間宣渗，只允許持有鎖的線程去執(zhí)行這段代碼抖所，其他線程會(huì)被阻塞，這樣就達(dá)到了線程安全讀寫(xiě)List痕囱。
在添加的最后都有setArray()方法:
final void setArray(Object[] a) {
elements = a;
}
add函數(shù)中拷貝了原來(lái)的數(shù)組并在最后加上了新元素田轧，并調(diào)用setArray函數(shù)將引用鏈接到新數(shù)組.
其它用法與ArrayList類似，畢竟都是List的實(shí)現(xiàn)類鞍恢。
- 缺點(diǎn)
- 內(nèi)存占用問(wèn)題傻粘。因?yàn)镃opyOnWrite的寫(xiě)時(shí)復(fù)制機(jī)制每窖，所以在進(jìn)行寫(xiě)操作的時(shí)候，內(nèi)存里會(huì)同時(shí)駐扎兩個(gè)對(duì)象的內(nèi)存弦悉，舊的對(duì)象和新寫(xiě)入的對(duì)象（注意:在復(fù)制的時(shí)候只是復(fù)制容器里的引用窒典，只是在寫(xiě)的時(shí)候會(huì)創(chuàng)建新對(duì)象添加到新容器里，而舊容器的對(duì)象還在使用稽莉，所以有兩份對(duì)象內(nèi)存）瀑志。如果這些對(duì)象占用的內(nèi)存比較大，比如說(shuō)200M左右污秆，那么再寫(xiě)入100M數(shù)據(jù)進(jìn)去劈猪，內(nèi)存就會(huì)占用300M，那么這個(gè)時(shí)候很有可能造成頻繁的Yong GC和Full GC良拼。之前我們系統(tǒng)中使用了一個(gè)服務(wù)由于每晚使用CopyOnWrite機(jī)制更新大對(duì)象战得，造成了每晚15秒的Full GC，應(yīng)用響應(yīng)時(shí)間也隨之變長(zhǎng)庸推。
- 數(shù)據(jù)一致性問(wèn)題常侦。CopyOnWrite容器只能保證數(shù)據(jù)的最終一致性，不能保證數(shù)據(jù)的實(shí)時(shí)一致性贬媒。所以如果你希望寫(xiě)入的的數(shù)據(jù)聋亡，馬上能讀到，請(qǐng)不要使用CopyOnWrite容器掖蛤。
