Overview
List族最重要的幾個特點：
- 有序
- 允許重復(fù)元素
- 支持add, remove, set, get
- 可以隨機訪問元素
Lis族集合類：
- List族中玄渗，最主要的三種集合是
ArrayList,Vector和LinkedList概漱，后面將對這三種類進行分析和比較陌宿。 - 可以簡單對比一下List和Set
| List | Set | |
|---|---|---|
| 有序 | Y | N |
| 重復(fù)元素 | Y | N |
| 隨機訪問 | Y | N |
ArrayList
Java Platform SE 8的描述：
Resizable-array implementation of the List interface. Implements all optional list operations, and permits all elements, including null. In addition to implementing the List interface, this class provides methods to manipulate the size of the array that is used internally to store the list. (This class is roughly equivalent to Vector, except that it is unsynchronized.)
- 可變長數(shù)組
- 實現(xiàn)所有l(wèi)ist的操作
- 允許null
- 和Vector相似贡未，但是unsynchronized
<span style="color:#ab4642">ArrayList是一種能夠自動擴充長度的數(shù)組宏多。</span>
性能
The size, isEmpty, get, set, iterator, and listIterator operations run in constant time.
The add operation runs in amortized constant time, that is, adding n elements requires O(n) time.
- ArrayList的性能可以類比<span style="color:#ab4642">數(shù)組</span>的性能瑞凑，在隨機訪問性能好。增、刪操作性能差玩郊。
線程安全
<span style="color:#ab4642">Note that this implementation is not synchronized...</span>
Collections.synchronizedList:
Returns a synchronized (thread-safe) list backed by the specified list. In order to guarantee serial access, it is critical that all access to the backing list is accomplished through the returned list.*
- 不能依賴fail-fast進行程序同步控制肢执，應(yīng)該對ArrayList進行包裝（
Collections.synchronizedList），合法的ArrayList同步操作demo：
List list = Collections.synchronizedList(new ArrayList());
...
synchronized (list) {
Iterator i = list.iterator(); // Must be in synchronized block
while (i.hasNext())
foo(i.next());
}
Vector
The Vector class implements a growable array of objects. Like an array, it contains components that can be accessed using an integer index.
The iterators returned by this class's iterator and listIterator methods are fail-fast:...
..., If a thread-safe implementation is not needed, it is recommended to use ArrayList in place of Vector.
- Vector和ArrayList的性能相似译红，最重要的<span style="color:#ab4642">區(qū)別:</span>是:
-
Vector是<span style="color:#ab4642">線程安全</span>的预茄。 - 擴容機制不一樣，具體可以看后面的擴容代碼解讀：
-
LinkedList
Doubly-linked list implementation of the List and Deque interfaces. Implements all optional list operations, and permits all elements (including null).
All of the operations perform as could be expected for a doubly-linked list. Operations that index into the list will traverse the list from the beginning or the end, whichever is closer to the specified index.
性能：
- 具有鏈表的特點侦厚，對增加和刪除節(jié)點的操作效率高（特別是表頭或者表尾的操作）耻陕。但是，隨機訪問效率低刨沦。
同步：
The iterators returned by this class's iterator and listIterator methods are fail-fast
- LinkedList是線程不安全的诗宣，需要包裝：
List list = Collections.synchronizedList(new LinkedList(...));
ArrayList vs Vector vs LinkedList
| ArrayList | Vector | LinkedList | |
|---|---|---|---|
| list接口 | Y | Y | Y |
| deque接口 | N | N | Y |
| elements 允許null | Y | Y | Y |
| growable | Y | Y | N |
| get | O(1) | O(1) | O(n) |
| set | O(1) | O(1) | O(n) |
| remove | O(n) | O(n) | O(1) |
| add | O(n) | O(n) | O(1) |
| synchronized | N | Y | N |
| synchronized | N | Y | N |
| fail-fast | Y | Y | Y |
幾個值得深入思考的問題
fail-fast
fail-fast 機制是java集合(Collection)中的一種錯誤機制。ArrayList,Vector, LinkedList 都滿足fail-fast機制想诅。官方文檔中對fail-fast的解釋如下：
fail-fast: if the list is structurally modified at any time after the iterator is created, in any way except through the iterator's own remove or add methods, the iterator will throw a
ConcurrentModificationException. Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future.
- fail-fast產(chǎn)生的原因就在于程序在對collection（如: ArrayList）進行迭代時梧田，某個線程對該 collection 在結(jié)構(gòu)上對其做了修改，這時迭代器就會拋出
ConcurrentModificationException異常信息侧蘸，從而產(chǎn)生 fail-fast
要了解fail-fast機制，我們首先要對ConcurrentModificationException 異常有所了解鹉梨。當方法檢測到對象的并發(fā)修改讳癌，但不允許這種修改時就拋出該異常。同時需要注意的是存皂，該異常不會始終指出對象已經(jīng)由不同線程并發(fā)修改晌坤，如果單線程違反了規(guī)則，同樣也有可能會拋出改異常旦袋。
ConcurrentModificationException
- 容器使用迭代器來進行統(tǒng)一個容器訪問操作骤菠。迭代器本質(zhì)上只是容器的一個視圖，迭代器里存放容器訪問的游標疤孕，以及expectedModCount
-
expectedModCount是迭代器fail-fast機制的關(guān)鍵商乎， - 迭代器在操作容器元素前，會
checkForComodification祭阀，其實就是檢查expectedModCount==modCount - 迭代器在對容器作結(jié)構(gòu)性后鹉戚，會刷新
expectedModCount = modCount。 - 換言之专控，如果在迭代器同步到最新的modCount后抹凳，有其他操作修改了容器的modCount，那么
checkForComodification就會校驗失敗伦腐，于是就拋出ConcurrentModificationException
private class Itr implements Iterator<E> {
/**
* Index of element to be returned by subsequent call to next.
*/
int cursor = 0;
/**
* Index of element returned by most recent call to next or
* previous. Reset to -1 if this element is deleted by a call
* to remove.
*/
int lastRet = -1;
/**
* The modCount value that the iterator believes that the backing
* List should have. If this expectation is violated, the iterator
* has detected concurrent modification.
*/
int expectedModCount = modCount;
public boolean hasNext() {
return cursor != size();
}
public E next() {
checkForComodification();
try {
int i = cursor;
E next = get(i);
lastRet = i;
cursor = i + 1;
return next;
} catch (IndexOutOfBoundsException e) {
checkForComodification();
throw new NoSuchElementException();
}
}
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
AbstractList.this.remove(lastRet);
if (lastRet < cursor)
cursor--;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException e) {
throw new ConcurrentModificationException();
}
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
private class ListItr extends Itr implements ListIterator<E> {
ListItr(int index) {
cursor = index;
}
public boolean hasPrevious() {
return cursor != 0;
}
public E previous() {
checkForComodification();
try {
int i = cursor - 1;
E previous = get(i);
lastRet = cursor = i;
return previous;
} catch (IndexOutOfBoundsException e) {
checkForComodification();
throw new NoSuchElementException();
}
}
public int nextIndex() {
return cursor;
}
public int previousIndex() {
return cursor-1;
}
public void set(E e) {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
AbstractList.this.set(lastRet, e);
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
public void add(E e) {
checkForComodification();
try {
int i = cursor;
AbstractList.this.add(i, e);
lastRet = -1;
cursor = i + 1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
}
值得一提的時候赢底，當不適用迭代器訪問和操作容器的時候，不會拋出ConcurrentModificationException，但是并不意味著程序正確幸冻。即使粹庞，是迭代器訪問的程序，也有恰好未發(fā)生ConcurrentModificationException的情況嘁扼。
Note that the fail-fast behavior of an iterator cannot be guaranteed as it is, generally speaking, impossible to make any hard guarantees in the presence of unsynchronized concurrent modification. Fail-fast iterators throw ConcurrentModificationException on a best-effort basis. Therefore, it would be wrong to write a program that depended on this exception for its correctness: the fail-fast behavior of iterators should be used only to detect bugs.
注意信粮，迭代器的快速失敗行為無法得到保證，因為一般來說趁啸，不可能對是否出現(xiàn)不同步并發(fā)修改做出任何硬性保證强缘。快速失敗迭代器會盡最大努力拋出 ConcurrentModificationException不傅。因此旅掂，為提高這類迭代器的正確性而編寫一個依賴于此異常的程序是錯誤的做法：迭代器的快速失敗行為應(yīng)該僅用于檢測 bug。
- 不能依賴fail-fast機制來保證程序的正確性访娶。
ConcurrentModificationException只適合用來查bug商虐。
fast-fail的測試代碼
-
failFastWorkTest的Thread t1使用迭代器來訪問容器，在訪問過程中崖疤，Thread t2對容器調(diào)用了ArrayList.remove(element)操作秘车，此后，當t1迭代到下一個元素時候劫哼，（next()會檢查modCount, 即checkForComodification）這將引發(fā)fast-fail.
根據(jù)上面描述叮趴，我們可以寫個demo來測試ArrayList的fast-fail：
@Test
public void failFastWorkTest() throws InterruptedException, ConcurrentModificationException {
Thread t1 = new Thread(new Runnable() {
@Override
public void run() {
Iterator<Integer> iterator = arrayList.iterator();
while(iterator.hasNext()) {
int i = iterator.next();
logger.info("thread t1 get item : {}", i);
try {
Thread.sleep(10);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
});
Thread t2 = new Thread(new Runnable() {
@Override
public void run() {
for (int i = 0; i < 10; i++) {
if (i == 3) {
// arrayList.remove(i);
arrayList.add(i);
}
}
}
});
runThreads(t1, t2);
}
private void runThreads(Thread t1, Thread t2) throws InterruptedException {
logger.info("start thread 1 ");
t1.start();
logger.info("start thread 2 ");
t2.start();
t1.join();
logger.info("end thread1 ");
t2.join();
logger.info("end thread2 ");
logger.info("fail fast test done");
logger.info("finnal array List", arrayList);
}
-
failFastNoWorkTest的Thread t1使用直接通過ArrayList.get()來訪問容器，在訪問過程中权烧，Thread t2對容器調(diào)用了ArrayList.remove(element)操作眯亦。未使用迭代器，所以沒有modCount校驗般码，所以不會發(fā)生fast-fail妻率。當實際上，這樣的程序是線程不安全的板祝。
@Test
public void failFastNoWorkTest() throws InterruptedException {
Thread t1 = new Thread(new Runnable() {
@Override
public void run() {
int size = arrayList.size();
for (int i = 0; i < size; i++) {
int value = arrayList.get(i);
logger.info("thread 1 run : {}", value);
printPrivateField(AbstractList.class, "modCount", arrayList);
try {
Thread.sleep(10);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
});
Thread t2 = new Thread(new Runnable() {
@Override
public void run() {
for (int i = 0; i < RUN_TIMES; i++) {
if (i == 3) {
arrayList.remove(3);
}
printPrivateField(AbstractList.class, "modCount", arrayList);
addElementByList(arrayList, 100);
}
}
});
logger.info("before start thread ... ");
printPrivateField(AbstractList.class, "modCount", arrayList);
new ListTest().runThreads(t1, t2);
}
capacity
另一個值得研究的知識點是List的自動擴容宫静，主要是ArrayList和Vector。
ArrayList和Vector都是使用數(shù)組(Array)來控制集合中的對象扔字。當你向這兩種類型中增加元素的時候囊嘉，如果元素的數(shù)目超出了內(nèi)部數(shù)組目前的長度它們都需要擴展內(nèi)部數(shù)組的長度，Vector缺省情況下自動增長原來一倍的數(shù)組長度革为，ArrayList是原來的50%,所以最后你獲得的這個集合所占的空間總是比你實際需要的要大扭粱。所以如果你要在集合中保存大量的數(shù)據(jù)那么使用Vector有一些優(yōu)勢，因為你可以通過設(shè)置集合的初始化大小來避免不必要的資源開銷震檩。
Vector
/**
* This implements the unsynchronized semantics of ensureCapacity.
* Synchronized methods in this class can internally call this
* method for ensuring capacity without incurring the cost of an
* extra synchronization.
*
* @see #ensureCapacity(int)
*/
private void ensureCapacityHelper(int minCapacity) {
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
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);
}
ArrayList:
/**
* Increases the capacity to ensure that it can hold at least the
* number of elements specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity
*/
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);
}
所以琢蛤，如果需要存儲的數(shù)據(jù)量比較大蜓堕，可以使用Vector，以減少擴容次數(shù)博其。另外套才，Vector可以設(shè)置capacityIncrement，來配置每次擴容的增長量慕淡，比較靈活背伴。
參考鏈接
ArrayList
simpleJava
fail-fast
SynchronizedList和Vector的區(qū)別, by Hollis
