一、集合大綱
Java中的集合包含多種資料結構，如連結清單、隊列、哈希表等。從類的繼承結構來說，可以分為兩大類，一類是繼承自Collection接口，這類集合包含List、Set和Queue等集合類。另一類是繼承自Map接口，這主要包含了哈希表相關的集合類
結構圖如下
二、常見分類
Collection 接口的接口 對象的集合（單列集合）
├——-List 接口：元素按進入先後有序儲存，可重複
│—————-├ LinkedList 接口實作類， 連結清單， 插入删除， 沒有同步， 線程不安全
│—————-├ ArrayList 接口實作類， 數組， 随機通路， 沒有同步， 線程不安全
│—————-└ Vector 接口實作類 數組， 同步， 線程安全
│ ———————-└ Stack 是Vector類的實作類
└——-Set 接口： 僅接收一次，不可重複，并做内部排序
├—————-└HashSet 使用hash表（數組）存儲元素
│————————└ LinkedHashSet 連結清單維護元素的插入次序
└ —————-TreeSet 底層實作為二叉樹，元素排好序
Map 接口 鍵值對的集合 （雙列集合）
├———Hashtable 接口實作類， 同步， 線程安全
├———HashMap 接口實作類 ，沒有同步， 線程不安全-
│—————–├ LinkedHashMap 雙向連結清單和哈希表實作
│—————–└ WeakHashMap
├ ——–TreeMap 紅黑樹對所有的key進行排序
└———IdentifyHashMap
三、List實作原理
3.1 實作的接口
常用的實作List接口的主要有ArrayList、Vector、LinkedList 三個，
3.1.1 ArrayList
特點：ArrayList是List使用中最常用的實作類，它的查詢速度快，效率高，但增删慢，線程不安全。
原理：ArrayList底層實作采用的資料結構是數組，并且數組預設大小為10，是以下面兩種方式是等同的
List list = new ArrayList(); //沒有指定數組大小，使用預設值（預設大小是10）
List list = new ArrayList(10); // 指定數組大小為10，傳如的參數便是數組的大小，傳入為10時，跟預設值相同，是以是等同的
擴容機制：
jdk1.8的擴容算法：newCapacity = oldCapacity + ( oldCapacity >> 1 ) ; // oldCapacity >> 2 移位運算，此處相當于oldCapacity除以2，但是 >> 這種寫法更加高效
jdk1.6的擴容算法：newCapacity = ( oldCapacity * 3 ) / 2 +1 ;
參數介紹：newCapacity 是擴容後的容量大小，oldCapacity 是擴容前的大小
檢視jdk源碼，移位運算需要學習下，換句話說，就是需要學習下二進制，比如：反碼、補碼，二進制與十進制、十六進制的互相轉換。與機器交流的都是0110等，是以挺重要的。
3.1.2 Vector
特點：Vector的底層也是通過數組實作的，預設大小也是10。主要特點：查詢快，增删慢 ， 線程安全，但是效率低
原理：建立對象與ArrayList類似，但有一點不同，它可以設定擴容是容量增長大小。
根據Vector的三個構造器就可以很明了的了解 new Vector(); 與 new Vector(10);與 new Vector(10,0); 三個是等同的，很明了就不贅述了
1.無參構造器 public Vector() {
this(10);
}
2.傳一個參數（容量大小） 容量大小即底層數組大小
public Vector(int initialCapacity) {
this(initialCapacity, 0);
}
3.傳兩個參數（容量大小，容量修正） 容量修正即擴容時的增加量
public Vector(int initialCapacity, int capacityIncrement) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
this.capacityIncrement = capacityIncrement;
}
擴容機制：
jdk1.8的擴容算法：newCapacity = oldCapacity + ( ( capacityIncrement > 0 ) ? capacityIncrement : oldCapacity );
jdk1.6的擴容算法：newCapacity = ( capacityIncrement > 0 ) ? ( oldCapacity + capacityIncrement ) : ( oldCapacity * 2 );
參數介紹：capacityIncrement 是容量修正（即容量新增大小），沒有設定，預設為0 ，newCapacity 是擴容後的容量大小，oldCapacity 是擴容前的大小
一觀察，就會發現1.6與1.8的寫法變化不大，但是仔細一分析，就會發現jdk1.6中有使用乘法運算，即 oldCapacity * 2。 在jdk1.8中換成了加法運算，這是因為乘法的效率是低于加法的，這應該算法的優化。
3.1.3 LinkedList
特點：LinkedList底層是一個雙向連結清單，它增删快，效率高，但是查詢慢，線程不安全
原理：構造器隻有如下兩種;
1.無參構造
public LinkedList() {
}
2.有參構造
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
由于它的底層實作是連結清單，是以沒有容量大小的定義，隻有上個節點，目前節點，下個節點，每個節點都有一個上級節點和一個下級節點。
新增元素實作代碼如下
private void linkFirst(E e) {
final Node<E> f = first;
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}
先擷取頭部節點元素，判斷是否為null，若為null，說明原連結清單中沒有元素，則把 first 和 last 都賦為目前新增節點。 若不為null，說明原連結清單中有元素，則把first賦為目前新增節點，把原頭部節點f的上級節點修改為目前新增節點的下級節點
尾部新增
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++;
}
與頭部新增元素類似，不再贅述。
删除元素：
删除元素有三種方式，删除第一進制素，删除最後一個元素，删除中間部分的某個元素。 現介紹最後一個，最後一個搞懂了，前兩個就懂了。
實作代碼：
E unlink(Node<E> x) {
// assert x != null;
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;
}
原理：要删除元素的目前節點x，将目前節點x的上級節點的下級節點設為目前節點x的下級節點，将目前節點x的下級節點的上級節點設為目前節點x的上級節點。
中間考慮上級節點或下級節點為空的情況，也就是頭部删除與尾部删除。