Overview
List族最重要的幾個(gè)特點(diǎn)：
- 有序
- 允許重復(fù)元素
- 支持add, remove, set, get
- 可以隨機(jī)訪問元素
Lis族集合類：
- List族中，最主要的三種集合是
ArrayList,Vector和LinkedList，后面將對(duì)這三種類進(jìn)行分析和比較。 - 可以簡(jiǎn)單對(duì)比一下List和Set
| List | Set | |
|---|---|---|
| 有序 | Y | N |
| 重復(fù)元素 | Y | N |
| 隨機(jī)訪問 | 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.)
- 可變長(zhǎng)數(shù)組
- 實(shí)現(xiàn)所有l(wèi)ist的操作
- 允許null
- 和Vector相似，但是unsynchronized
<span style="color:#ab4642">ArrayList是一種能夠自動(dòng)擴(kuò)充長(zhǎng)度的數(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>的性能，在隨機(jī)訪問性能好。增、刪操作性能差。
線程安全
<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進(jìn)行程序同步控制，應(yīng)該對(duì)ArrayList進(jìn)行包裝（
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>的。 - 擴(kuò)容機(jī)制不一樣，具體可以看后面的擴(kuò)容代碼解讀：
-
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.
性能：
- 具有鏈表的特點(diǎn)，對(duì)增加和刪除節(jié)點(diǎn)的操作效率高（特別是表頭或者表尾的操作）。但是，隨機(jī)訪問效率低。
同步：
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 |
幾個(gè)值得深入思考的問題
fail-fast
fail-fast 機(jī)制是java集合(Collection)中的一種錯(cuò)誤機(jī)制。ArrayList,Vector, LinkedList 都滿足fail-fast機(jī)制。官方文檔中對(duì)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)生的原因就在于程序在對(duì)collection（如: ArrayList）進(jìn)行迭代時(shí)，某個(gè)線程對(duì)該 collection 在結(jié)構(gòu)上對(duì)其做了修改，這時(shí)迭代器就會(huì)拋出
ConcurrentModificationException異常信息，從而產(chǎn)生 fail-fast
要了解fail-fast機(jī)制，我們首先要對(duì)ConcurrentModificationException 異常有所了解。當(dāng)方法檢測(cè)到對(duì)象的并發(fā)修改，但不允許這種修改時(shí)就拋出該異常。同時(shí)需要注意的是，該異常不會(huì)始終指出對(duì)象已經(jīng)由不同線程并發(fā)修改，如果單線程違反了規(guī)則，同樣也有可能會(huì)拋出改異常。
ConcurrentModificationException
- 容器使用迭代器來進(jìn)行統(tǒng)一個(gè)容器訪問操作。迭代器本質(zhì)上只是容器的一個(gè)視圖，迭代器里存放容器訪問的游標(biāo)，以及expectedModCount
-
expectedModCount是迭代器fail-fast機(jī)制的關(guān)鍵， - 迭代器在操作容器元素前，會(huì)
checkForComodification，其實(shí)就是檢查expectedModCount==modCount - 迭代器在對(duì)容器作結(jié)構(gòu)性后，會(huì)刷新
expectedModCount = modCount。 - 換言之，如果在迭代器同步到最新的modCount后，有其他操作修改了容器的modCount，那么
checkForComodification就會(huì)校驗(yàn)失敗，于是就拋出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();
}
}
}
值得一提的時(shí)候，當(dāng)不適用迭代器訪問和操作容器的時(shí)候，不會(huì)拋出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.
注意，迭代器的快速失敗行為無法得到保證，因?yàn)橐话銇碚f，不可能對(duì)是否出現(xiàn)不同步并發(fā)修改做出任何硬性保證?？焖偈〉鲿?huì)盡最大努力拋出 ConcurrentModificationException。因此，為提高這類迭代器的正確性而編寫一個(gè)依賴于此異常的程序是錯(cuò)誤的做法：迭代器的快速失敗行為應(yīng)該僅用于檢測(cè) bug。
- 不能依賴fail-fast機(jī)制來保證程序的正確性。
ConcurrentModificationException只適合用來查bug。
fast-fail的測(cè)試代碼
-
failFastWorkTest的Thread t1使用迭代器來訪問容器，在訪問過程中，Thread t2對(duì)容器調(diào)用了ArrayList.remove(element)操作，此后，當(dāng)t1迭代到下一個(gè)元素時(shí)候，（next()會(huì)檢查modCount, 即checkForComodification）這將引發(fā)fast-fail.
根據(jù)上面描述，我們可以寫個(gè)demo來測(cè)試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對(duì)容器調(diào)用了ArrayList.remove(element)操作。未使用迭代器，所以沒有modCount校驗(yàn)，所以不會(huì)發(fā)生fast-fail。當(dāng)實(shí)際上，這樣的程序是線程不安全的。
@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
另一個(gè)值得研究的知識(shí)點(diǎn)是List的自動(dòng)擴(kuò)容，主要是ArrayList和Vector。
ArrayList和Vector都是使用數(shù)組(Array)來控制集合中的對(duì)象。當(dāng)你向這兩種類型中增加元素的時(shí)候，如果元素的數(shù)目超出了內(nèi)部數(shù)組目前的長(zhǎng)度它們都需要擴(kuò)展內(nèi)部數(shù)組的長(zhǎng)度，Vector缺省情況下自動(dòng)增長(zhǎng)原來一倍的數(shù)組長(zhǎng)度，ArrayList是原來的50%,所以最后你獲得的這個(gè)集合所占的空間總是比你實(shí)際需要的要大。所以如果你要在集合中保存大量的數(shù)據(jù)那么使用Vector有一些優(yōu)勢(shì)，因?yàn)槟憧梢酝ㄟ^設(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);
}
所以，如果需要存儲(chǔ)的數(shù)據(jù)量比較大，可以使用Vector，以減少擴(kuò)容次數(shù)。另外，Vector可以設(shè)置capacityIncrement，來配置每次擴(kuò)容的增長(zhǎng)量，比較靈活。
參考鏈接
ArrayList
simpleJava
fail-fast
SynchronizedList和Vector的區(qū)別, by Hollis
