1.Collection分類：
ArrayList源碼：
新增：
//1.ArrayList是數組結構，查詢快增删慢。
//2.看源碼：先看繼承實作了什麼（知源頭），再看構造方法、定義的變量（識輪廓），在看對應調用的方法（會應用）
public boolean add(E e) {
ensureCapacityInternal(size + 1); // 判斷是否擴容
elementData[size++] = e;//指派後size+1
return true;
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
//elementData目前的數組 minCapacity：目前數組size+1
private static int calculateCapacity(Object[] elementData, int minCapacity) {
//若目前數組是一個空數組（還未新增過），取到預設容量10，否則傳回size+1
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;//記錄改變次數
//1.新增到第10次之前elementData.length是10，後面會1.5*10擴容
//2.新增到第10次時進入到grow方法 進行擴容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
//>>右移：除以2的n次方
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
//最大值是Integer的MAX
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; 指定索引的新增
//指定索引去新增
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
//多了這一步驟：用于将index之後的元素都往後移一位步：
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
} 删除：
public E remove(int index) {
rangeCheck(index);//校驗索引值
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;//要移動的長度
if (numMoved > 0)
//将elementData從index+1開始長度為numMoved的部分移動到index位置處，即：index+1後面的元素前進一位
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // 指派 size-1
return oldValue;
} 查詢：
//因為它本身就是個數組 速度快
//arrayList差別于數組的地方在于能夠自動擴充大小，其中關鍵的方法就是gorw()方法
public E get(int index) {
rangeCheck(index);
return elementData(index);
} LinkedList源碼：
LinkedList是一個雙向連結清單，查詢慢、增删快
LinkedList屬性：
transient int size = 0; //連結清單大小
transient Node<E> first;//頭結點資訊
transient Node<E> last;//尾節點資訊
//節點資訊：資料+前/後指針
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
} 新增：
//從尾部新增： 其它類似！
public boolean add(E e) {
linkLast(e);
return true;
}
void linkLast(E e) {
//定義一個中間節點，将尾部節點資料指派給他
final Node<E> l = last;
//指定新增節點的前後指針
final Node<E> newNode = new Node<>(l, e, null);
//變為尾節點
last = newNode;
//若該連結清單為空的，新增節點就是頭結點
if (l == null)
first = newNode;
//由于是雙向連結清單，前後指針要指定
else
l.next = newNode;
size++;
modCount++;
} 删除：
//連結清單的删除可以根據索引，元素值。。。
public boolean remove(Object o) {
//這個就說明LinedList可以存放null元素
//周遊該連結清單，找到一緻的元素删掉
if (o == null) {
//從頭結點first開始一直next到尾節點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;
}
//解鍊操作
E unlink(Node<E> x) {
//首先先擷取要删除元素的資料+前後一個資料資訊
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
//判斷是不是頭結點
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;//去掉該元素指針
}
//判斷是不是為節點
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
//資料置空
x.item = null;
size--;
modCount++;
return element;
} 查詢：
//可以根據索引、查詢頭尾
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
//采用了二分法進行查詢
Node<E> node(int index) {
//如果目前索引小于size的一半，從頭結點開始查詢
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
} ArrayList和LinekList的差別：
- LinkedList在删除和增加等操作上性能好（它隻需要改變目前結點和前後結點即可，而ArrayList使用System.copy（...）方法操作的是一段長度的元素），而ArrayList在查詢的性能上好。
- ArrayList：必須開辟連續空間進行存儲資料而LinkedList不需要。
- 兩者在周遊時可以使用for-each循環、Iterator、listIterator周遊器。
Vector源碼：
Vector是數組結構（和ArrayList類似），線程安全的。在分析源碼之前先了解下鎖機制(也是Vector為啥是線程安全的)：對象鎖、方法鎖、類鎖:
- 對象鎖就是方法鎖：就是在一個類中的方法上加上synchronized關鍵字，這就是給這個方法加鎖了。Vector就是在方法上添加了synchronized關鍵字。
- 類鎖：鎖的是整個類，當有多個線程來聲明這個類的對象的時候将會被阻塞，直到擁有這個類鎖的對象被銷毀或者主動釋放了類鎖。這個時候在被阻塞住的線程被挑選出一個占有該類鎖，聲明該類的對象。其他線程繼續被阻塞住。例如：在類A上有關鍵字synchronized，那麼就是給類A加了類鎖，線程1第一個聲明此類的執行個體，則線程1拿到了該類鎖，線程2在想聲明類A的對象，就會被阻塞。
Vector屬性：
protected Object[] elementData; //數組容器
protected int elementCount; //元素個數
protected int capacityIncrement;//增長系數 在擴容的時候用到（若它大于0每次擴容是原數組容量+增長系數 若小于等于0 原數組容量*2）
//Vector提供了構造方法 可以指定初始化容量和增長系數
public Vector(int initialCapacity, int capacityIncrement) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
this.capacityIncrement = capacityIncrement;
}
//預設初始化容量是10
public Vector() {
this(10);
} 增加：
//synchronized關鍵字
//和ArrayList原理類似 都是先判斷是否擴容 在去指派，不同的是擴容方式
public synchronized boolean add(E e) {
modCount++;
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = e;
return true;
}
private void ensureCapacityHelper(int minCapacity) {
//若新增之後的長度>原長度擴容
//這裡和ArrayList有點差別：應為無參構造的Vector預設長度為10，而ArrayList是0，在新增後初始化長度10然後再1.5*原長度
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
//擴容 原長度+擴容系數/原長度*2
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
//原長度+擴容系數（指定擴容系數>0）/原長度*2（
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);
} 删除：
//根據索引
public synchronized E remove(int index) {
modCount++;
if (index >= elementCount)
throw new ArrayIndexOutOfBoundsException(index);
E oldValue = elementData(index);
int numMoved = elementCount - index - 1;
//将index後面的元素整體前移一位
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--elementCount] = null; // Let gc do its work
return oldValue;
}
//根據元素值：根據元素值找到其索引，在根據索引删除
public boolean remove(Object o) {
return removeElement(o);
}
public synchronized boolean removeElement(Object obj) {
modCount++;
int i = indexOf(obj);
if (i >= 0) {
removeElementAt(i);
return true;
}
return false;
}
public synchronized void removeElementAt(int index) {
modCount++;
if (index >= elementCount) {
throw new ArrayIndexOutOfBoundsException(index + " >= " +
elementCount);
}
else if (index < 0) {
throw new ArrayIndexOutOfBoundsException(index);
}
int j = elementCount - index - 1;
if (j > 0) {
System.arraycopy(elementData, index + 1, elementData, index, j);
}
elementCount--;
elementData[elementCount] = null; /* to let gc do its work */
} 總結：
1、arrayList和LinkedList差別？
- ArrayList底層是用數組實作的順序表，是随機存取類型，可自動擴增，并且在初始化時，數組的長度是0，隻有在增加元素時，長度才會增加。預設是10，不能無限擴增，有上限，在查詢操作的時候性能更好
- LinkedList底層是用連結清單來實作的，是一個雙向連結清單，注意這裡不是雙向循環連結清單,順序存取類型。在源碼中，似乎沒有元素個數的限制。應該能無限增加下去，直到記憶體滿了在進行删除，增加操作時性能更好。
- 兩個都市線程不安全的，在iterator時，會發生fail-fast。
2、ArrayList和Vector的差別？
- ArrayList線程不安全，在用iterator，會發生fail-fast
- Vector線程安全，因為在方法前加了Synchronized關鍵字。也會發生fail-fast
3、fail-fast和fail-safe差別是什麼?什麼情況下會發生？
一句話，在在java.util下的集合都是發生fail-fast，而在java.util.concurrent下的發生的都是fail-safe 。fail-fast：快速失敗，例如在arrayList中使用疊代器周遊時，有另外的線程對arrayList的存儲數組進行了改變，比如add、delete、等使之發生了結構上的改變，是以Iterator就會快速報一個java.util.ConcurrentModificationException 異常，這就是快速失敗。fail-safe:安全失敗，在java.util.concurrent下的類，都是線程安全的類，他們在疊代的過程中，如果有線程進行結構的改變，不會報異常，而是正常周遊，這就是安全失敗。
- 1、為什麼在java.util.concurrent包下對集合有結構的改變，卻不會報異常？
這裡稍微解釋一下，在concurrent下的集合類增加元素的時候使用Arrays.copyOf()來拷貝副本，在副本上增加元素，如果有其他線程在此改變了集合的結構，那也是在副本上的改變，而不是影響到原集合，疊代器還是照常周遊，周遊完之後，改變原引用指向副本，是以總的一句話就是如果在次包下的類進行增加删除，就會出現一個副本。是以能防止fail-fast，這種機制并不會出錯，是以我們叫這種現象為fail-safe。
- 2、vector也是線程安全的，為什麼是fail-fast呢？
這裡搞清楚一個問題，并不是說線程安全的集合就不會報fail-fast，而是報fail-safe，你得搞清楚上面這個問題答案的原理，出現fail-safe是因為他們在實作增删的底層機制不一樣，就像上面說的，會有一個副本，而像arrayList、linekdList、verctor等，他們底層就是對着真正的引用進行操作，是以才會發生異常。
- 3、既然是線程安全的，為什麼在疊代的時候，還會有别的線程來改變其集合的結構呢(也就是對其删除和增加等操作)？
首先，我們疊代的時候，根本就沒用到集合中的删除、增加，查詢的操作，就拿vector來說，我們都沒有用那些加鎖的方法是以其他線程是可以拿到該集合的。
- fail-fast
- fail-safe
4、為什麼現在都不提倡使用vector了？
- 1、vector實作線程安全的方法是在每個操作方法上加鎖，這些鎖并不是必須要的，在實際開發中，一般都市通過鎖一系列的操作來實作線程安全，也就是說将需要同步的資源放一起加鎖來保證線程安全，
- 2、如果多個Thread并發執行一個已經加鎖的方法，但是在該方法中，又有vector的存在，vector本身實作中已經加鎖了，那麼相當于鎖上又加鎖，會造成額外的開銷，
- 3、就如上面第三個問題所說的，vector還有fail-fast的問題，也就是說它也無法保證周遊安全，在周遊時又得額外加鎖，又是額外的開銷，還不如直接用arrayList，然後再加鎖呢。
總結：Vector在你不需要進行線程安全的時候，也會給你加鎖，也就導緻了額外開銷，是以在jdk1.5之後就被棄用了，現在如果要用到線程安全的集合，都是從java.util.concurrent包下去拿相應的類。