List接口和實現(xiàn)類
list<E>接口繼承自Collection接口，主要處理有序集合，所謂有序，就是存放在此數(shù)據(jù)結構的數(shù)據(jù)會排序。
arrayList
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
arraylist 繼承自AbstractList<E>,底層數(shù)組實現(xiàn)谢鹊。
/**
* The array buffer into which the elements of the ArrayList are stored.
* The capacity of the ArrayList is the length of this array buffer. Any
* empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
* will be expanded to DEFAULT_CAPACITY when the first element is added.
*/
transient Object[] elementData; // non-private to simplify nested class access
空構造器，默認初始大小為10
/**
* Shared empty array instance used for default sized empty instances. We
* distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
* first element is added.
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; //這里雖然復賦值為null數(shù)組留凭，在第一次往里面添加元素時會擴大至容量10
}
有參構造
// initialCapacity表示list的初始容量
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
添加和移除操作：add() ,remove()
public void add(int index, E e) {
rangeCheckForAdd(index);
checkForComodification();
parent.add(parentOffset + index, e);
this.modCount = parent.modCount;
this.size++;
}
public E remove(int index) {
rangeCheck(index);
checkForComodification();
E result = parent.remove(parentOffset + index);
this.modCount = parent.modCount;
this.size--;
return result;
}
可以看出arraylist是非線程安全的佃扼，多線程操作需要程序員自己處理并發(fā)的問題。
linkedList
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
可以看出linkedlist未繼承AbstractList,而是自己實現(xiàn)list蔼夜。繼承于AbstractSequentialList的雙向鏈表兼耀。它也可以被當作堆棧、隊列或雙端隊列進行操作求冷。實現(xiàn) List 接口瘤运，能對它進行隊列操作。實現(xiàn) Deque 接口匠题，即能將LinkedList當作雙端隊列使用拯坟。實現(xiàn)了Cloneable接口，即覆蓋了函數(shù)clone()韭山，能克隆郁季。實現(xiàn)java.io.Serializable接口冷溃，這意味著LinkedList支持序列化，能通過序列化去傳輸梦裂。
/**
*空構造器
*/
public LinkedList() {
}
添加元素秃诵，刪除元素
public boolean add(E e) {
linkLast(e);
return true;
}
public boolean remove(Object o) {
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
vector
public class Vector<E>
extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
可以看出，vector和arraylist有點類似塞琼，和arraylist最大的區(qū)別就是vector是線程安全的。
構造函數(shù)
/**
* initialCapacity是初始容量禁舷，capacityIncrement表示每次擴容時需 要擴大的量彪杉，當此參數(shù)小于等于0時，2倍擴容
*/
public Vector(int initialCapacity, int capacityIncrement) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
this.capacityIncrement = capacityIncrement;
}
/**
*
*/
public Vector(int initialCapacity) {
this(initialCapacity, 0);
}
/**
*
*/
public Vector() {
this(10);
}
voctor的添加元素和刪除元素方法
public synchronized void addElement(E obj) {
modCount++;
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = obj;
}
public synchronized boolean removeElement(Object obj) {
modCount++;
int i = indexOf(obj);
if (i >= 0) {
removeElementAt(i);
return true;
}
return false;
}
從這個方法可以看出牵咙，voctor實現(xiàn)同步的辦法是加了synchronized派近。
一般情況下,arraylist遍歷元素時使用foreach，因為arraylist底層是數(shù)組實現(xiàn)洁桌，查詢比較快渴丸。而linkedlist底層是雙向鏈表，對插入和刪除性能比較好另凌，在遍歷時用foreach效率就會很低（此處更正谱轨，不只foreach效率低，并且使用foreach遍歷list無論是否多線程操作都會發(fā)生fail-fast錯誤吠谢。）土童，一般就會使用到Iterator（稱為迭代器） 來提高效率，因為創(chuàng)建它的代價很小工坊。但在多線程時對它使用不當會發(fā)生一個叫fail-fast（稱為快速失斚缀埂）的問題，也就是會報java.util.ConcurrentModificationException王污，原因在于iterator是對linkedlist中對象的引用的一個拷貝罢吃，比如：
Object o = new Object();
//o就是對new Object()對象的引用，相當于一個指針指向在堆中的真實對象昭齐，而對對象引用的拷貝是指用一個新的引用指向o這個引用尿招。
Object ob = o;
在iterator容器中全是對真實對象引用的拷貝。層層尋找阱驾，我們找到了這個方法泊业。
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
就是這個方法拋出了這個異常，modCount這個參數(shù)我們發(fā)現(xiàn)在abstractList中
//modCount是抽象類AbstractList中的變量啊易，默認為0,用于記錄集合操作過程中作的修改次數(shù)
protected transient int modCount = 0;
expectedModCount 存在abstractList中茴晋，初始等于modCount为流；
//expectedModCount表示迭代器對集合進行修改的次數(shù)。
int expectedModCount = modCount;
這里不難分析出，一個是表示線程對集合修改次數(shù)，一個地iterator對集合修改次數(shù)叉袍。當兩個值不相等，拋出異常。假設場景：當一個線程對iterator遍歷時（假設它正在遍歷昼丑，不存在添加修改），expectedModCount就不會改變夸赫。而另外一個線程同時在刪除或添加元素菩帝，modCount就是改變。這就導致這兩個值不一致茬腿，報錯呼奢。
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();
}
}
和我們猜測的一樣每次next(),都會檢查的，解決辦法就是保證容器的操作原子性切平，加鎖握础，同步，當然悴品，也可以使用java.util.concurrent包下的很多實現(xiàn)了線程安全的容器禀综。
～～～～劃水～
通過查api文檔知道，arraylist苔严，linkedlist是在java.util包下線程不安全的集合類定枷，vorctor雖然是線程安全的，但它使用的是synchronized來實現(xiàn)線程安全届氢，它的效率太低了依鸥。今天我們來說java.util.concurrent包下的線程安全的集合類。
CopyOnWriteArrayList悼沈，通過名字就知道贱迟，它的策略是在寫的時候復制list，簡單的講絮供，一個線程在對list寫的時候衣吠，不是直接對list寫，而是對list進行復制壤靶，對復制出來的list寫缚俏，寫完后在把引用指向這個復制的list。在寫的期間不影響其他線程對list的訪問贮乳。
看看它的讀寫方法
//可以看到讀方法是沒有加鎖的
@SuppressWarnings("unchecked")
private E get(Object[] a, int index) {
return (E) a[index];
}
public E get(int index) {
return get(getArray(), index);
}
//寫方法手動加鎖
public E set(int index, E element) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] elements = getArray();
E oldValue = get(elements, index);
if (oldValue != element) {
int len = elements.length;
Object[] newElements = Arrays.copyOf(elements, len);
newElements[index] = element;
setArray(newElements);
} else {
// Not quite a no-op; ensures volatile write semantics
setArray(elements);
}
return oldValue;
} finally {
lock.unlock();
}
}
public boolean add(E e) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] elements = getArray();
int len = elements.length;
Object[] newElements = Arrays.copyOf(elements, len + 1);
newElements[len] = e;
setArray(newElements);
return true;
} finally {
lock.unlock();
}
}
public void add(int index, E element) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] elements = getArray();
int len = elements.length;
if (index > len || index < 0)
throw new IndexOutOfBoundsException("Index: "+index+
", Size: "+len);
Object[] newElements;
int numMoved = len - index;
if (numMoved == 0)
newElements = Arrays.copyOf(elements, len + 1);
else {
newElements = new Object[len + 1];
System.arraycopy(elements, 0, newElements, 0, index);
System.arraycopy(elements, index, newElements, index + 1,
numMoved);
}
newElements[index] = element;
setArray(newElements);
} finally {
lock.unlock();
}
}
寫方法為什么加鎖呢忧换，是為了在一個線程對list復制時其他線程不能復制，寫完后把引用指向新的list時其他線程才能對新的list進行拷貝進行寫操作向拆。這樣保證了線程安全亚茬，注意這樣的list，**線程不能及時獲取到準確的數(shù)據(jù)浓恳。應用于讀多寫少的場景刹缝。比如黑名單碗暗。
那么問題來了，CopyOnWriteArrayList不能滿足我們想的需求啊梢夯，我們希望及時獲取到被修改的數(shù)據(jù)言疗，但又不想用vector（因為它效率低，讀方法和寫方法都是synchronized）颂砸。那怎么辦呢噪奄，那么接下來我們就該聊聊集合工具類Collections提供的synchronizedList方法了。它是個靜態(tài)方法人乓，不需要new勤篮。我們看看它的源碼吧！
public static <T> List<T> synchronizedList(List<T> list) {
return (list instanceof RandomAccess ?
new SynchronizedRandomAccessList<>(list) :
new SynchronizedList<>(list));
}
可以看出撒蟀，它需要傳入一個list對象，然后看它是否屬于RandomAccess的子類（instanceof判斷一個對象是否屬于某個類）温鸽，我們研究看看RandomAccess這個類是個啥保屯。
public interface RandomAccess {
}
源代碼就這么點，它就是接口涤垫，而且沒有定義任何方法姑尺。那就百度查查是干啥的。
RandomAccess 就是一個標記接口蝠猬，用于標明實現(xiàn)該接口的List支持快速隨機訪問切蟋，主要目的是使算法能夠在隨機和順序訪問的List中性能更加高效（在Collections二分查找時）。原來是提高效率的榆芦。
假如我們需要同步arraylist柄粹，可以查到，arraylist是實現(xiàn)了這個接口的匆绣。說明arraylist instanceof RandomAccess 返回為true驻右，程序便會new SynchronizedRandomAccessList<>(list)。現(xiàn)在該研究研究SynchronizedRandomAccessList是個啥了崎淳。
SynchronizedRandomAccessList(List<E> list) {
super(list);
}
繼續(xù)往里面走
SynchronizedList(List<E> list) {
super(list);
this.list = list;
}
this.list是啥
static class SynchronizedList<E> extends SynchronizedCollection<E>
implements List<E> {
private static final long serialVersionUID = -7754090372962971524L;
final List<E> list;
... //后面代碼略
原來是Collections類自己實現(xiàn)的的一個靜態(tài)list容器堪夭，我們看他的添加和獲取方法如何處理多線程并發(fā)。
public E get(int index) {
synchronized (mutex) {return list.get(index);}
}
public E set(int index, E element) {
synchronized (mutex) {return list.set(index, element);}
}
public void add(int index, E element) {
synchronized (mutex) {list.add(index, element);}
}
又是synchronized拣凹，可這個mutex是啥玩意森爽，對他加鎖就可以實現(xiàn)解決多線程問題？
static class SynchronizedCollection<E> implements Collection<E>, Serializable {
private static final long serialVersionUID = 3053995032091335093L;
final Collection<E> c; // Backing Collection
final Object mutex; // Object on which to synchronize
...//其他代碼略
這有是啥呢嚣镜？先看看它指向哪個對象爬迟？
SynchronizedCollection(Collection<E> c) {
this.c = Objects.requireNonNull(c);
mutex = this;
}
默認指向自己吶！大家可注意到SynchronizedList<E>是繼承了SynchronizedCollection<E>的菊匿，這兩個類都是Collections類自己實現(xiàn)的list容器雕旨。原來搞了半天扮匠，是對自己的容器對象加鎖（默認情況，也可以指定加鎖對象７采）這里我們應該差不多可以總結SynchronizedList和vector的區(qū)別了棒搜，SynchronizedList是對代碼塊實現(xiàn)同步。vector是對整個方法實現(xiàn)同步活箕。哈哈力麸，SynchronizedList效率確實會高那么點點的。還有一個很大不同是它倆擴容機制育韩，vector擴容是2倍增長克蚂，arraylist每次擴容是前一次的50%.
還有一個不同是SynchronizedList這個靜態(tài)方法也可以把linkedlist實現(xiàn)同步。哈哈筋讨，vector卻不能鞍０取！ 具體哪個場景用哪個悉罕，就得自己斟酌了赤屋。
～～～～劃水～
