摘要：有序可重復數組，線程不安全。是基于鏈接節點的線程安全的隊列。它實質上就是一種帶有一點扭曲的數據結構。鏈表結構，結構新特性，當節點數大于時，將鏈表轉換為紅黑樹過長的鏈表搜索性能降低，使用紅黑樹來提高查找性能。
Collection
List(有序,可重復)
ArrayList
數組，線程不安全。
查詢：帶下標訪問數組，O(1)
修改：由于arraylist不允許空的空間，當在一個arraylist的中間插入或者刪除元素，需要遍歷移動插入/刪除位置到數組尾部的所有元素。另外arraylist需要擴容時，需要將實際存儲的數組元素復制到一個新的數組去，因此一般認為修改的時間復雜度O(N)
擴容
/*minCapacity為原list長度*/
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// 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 + (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);
}
默認情況1.5倍增長
Vector
數組，線程安全(條件)
與ArrayList不同的是使用了同步（Synchronized），基本實現了線程安全
對象進行操作時，不加鎖的話還是有問題，例如下面的例子
public Object deleteLast(Vector v){
int lastIndex = v.size()-1;
v.remove(lastIndex);
}
執行deleteLast操作時如果不加鎖，可能會出現remove時size錯誤
擴容默認2倍增長
Stack堆棧
繼承Vector
通過push、pop進行入棧，出棧
LinkedList
雙向鏈表，線程不安全
查詢，需要遍歷鏈表，時間復雜度O(N)
修改，只需要修改1～2個節點的指針地址，時間復雜度O(1)
Set(無序,唯一)
HashSet
HashMap, 線程不安全
操作元素時間復雜度, O(1)
LinkedHashSet
LinkedHashMap，線程不安全
public class LinkedHashSet
extends HashSet
implements Set, Cloneable, java.io.Serializable {
...
public LinkedHashSet() {super(16, .75f, true);}
}
//hashset.java中的構造方法
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}
操作元素 O(1)
由于底層結構是LinkedHashMap，可以記錄元素之間插入的順序
TreeSet
TreeMap, 線程不安全
由于是樹結構，可以保證數據存儲是有序的
操作元素時間復雜度，O(logN)
Queue隊列
queue使用時要盡量避免Collection的add()和remove()方法，而是要使用offer()來加入元素，使用poll()來獲取并移出元素。它們的優
點是通過返回值可以判斷成功與否，add()和remove()方法在失敗的時候會拋出異常。 如果要使用前端而不移出該元素，使用
element()或者peek()方法。
1、沒有實現的阻塞接口的LinkedList：
實現了java.util.Queue接口和java.util.AbstractQueue接口
內置的不阻塞隊列： PriorityQueue 和 ConcurrentLinkedQueue
PriorityQueue 和 ConcurrentLinkedQueue 類在 Collection Framework 中加入兩個具體集合實現。
PriorityQueue 類實質上維護了一個有序列表。加入到 Queue 中的元素根據它們的天然排序（通過其 java.util.Comparable 實現）或者根據傳遞給構造函數的 java.util.Comparator 實現來定位。
ConcurrentLinkedQueue 是基于鏈接節點的、線程安全的隊列。并發訪問不需要同步。因為它在隊列的尾部添加元素并從頭部刪除它們，所以只要不需要知道隊列的大小， ConcurrentLinkedQueue 對公共集合的共享訪問就可以工作得很好。收集關于隊列大小的信息會很慢，需要遍歷隊列。
2)實現阻塞接口的
java.util.concurrent 中加入了 BlockingQueue 接口和五個阻塞隊列類。它實質上就是一種帶有一點扭曲的 FIFO 數據結構。不是立即從隊列中添加或者刪除元素，線程執行操作阻塞，直到有空間或者元素可用。
五個隊列所提供的各有不同：
ArrayBlockingQueue ：一個由數組支持的有界隊列。
LinkedBlockingQueue ：一個由鏈接節點支持的可選有界隊列。
PriorityBlockingQueue ：一個由優先級堆支持的無界優先級隊列。
DelayQueue ：一個由優先級堆支持的、基于時間的調度隊列。
SynchronousQueue ：一個利用 BlockingQueue 接口的簡單聚集（rendezvous）機制。
Map
HashMap
鏈表結構，Node結構
static class Node implements Map.Entry {
final int hash;
final K key;
V value;
Node next;
Node(int hash, K key, V value, Node next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
JDK 1.8新特性，當節點數大于8時，將鏈表轉換為紅黑樹
static final int TREEIFY_THRESHOLD = 8;
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
過長的鏈表搜索性能降低，使用紅黑樹來提高查找性能。
hash值計算
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
對key的hash碼高16位實現異或
a⊕b = (?a ∧ b) ∨ (a ∧?b)
如果a、b兩個值不相同，則異或結果為1。如果a、b兩個值相同，異或結果為0
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node[] tab; Node p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
...
插入table時，下標index = (n - 1) & hash
在n較小時，hash碼的低位的0和1不均勻，容易沖突導致碰撞。而通過上述XOR算法調整后，hash的低16位會變大，從而使得0和1分布更加均勻。
計算表容量
static final int MAXIMUM_CAPACITY = 1 << 30;
public HashMap(int initialCapacity, float loadFactor) {
/**省略此處代碼**/
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
假設cap=37，則n=36， 100100
右移1， 010010，或結果=110110
右移2， 001101，或結果=111111
右移4， 000011，或結果=111111
右移8， 000000，或結果=111111
右移16， 000000，或結果=111111
結果為63，二進制或操作只有在兩數都為0時，才為0，因此通過循環右移，或操作，實際是為了找到n的最高位，并將后面的數字全部全改寫為1，從而實現返回大于等于initialCapacity的最小的2的冪。
擴容
final Node[] resize() {
Node[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node[] newTab = (Node[])new Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) { //遍歷舊鏈表
Node e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null) //單節點
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode) //樹
((TreeNode)e).split(this, newTab, j, oldCap);
else { //鏈表
Node loHead = null, loTail = null;
Node hiHead = null, hiTail = null;
Node next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else { //尾部指針hi
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
這段代碼的含義是將oldTab[j]中的鏈表對半拆到newTab[j]和newTab[j + oldCap]
if ((e.hash & oldCap) == 0)怎么理解
我們知道oldTab中的index = (n - 1) & hash，假設n=8，則
newTab中的index = (16-1) & hash，那么在newTab中的index為index或者index + 8，那么e.hash & oldCap == 0 ,hash 必然為 X001000的形態才有可能，也就是說
if ((e.hash & oldCap) == 0)代表newindex == index的情況
loHead loTail/ hiTail hiHead 這2對指針
前面說了if ((e.hash & oldCap) == 0)表示newindex == index，那么lo指針指向的就是此類節點，hi指針指向剩下的節點
通過tail指針的移動，實現鏈表拆分以及各節點next指針的更新
HashTable
Dictionary, 線程安全
操作元素時間復雜度, O(1)
synchronized 線程安全
寫入數據
public synchronized V put(K key, V value) {
// Make sure the value is not null
if (value == null) {
throw new NullPointerException();
}
// Makes sure the key is not already in the hashtable.
Entry tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
Entry entry = (Entry)tab[index];
for(; entry != null ; entry = entry.next) { //遍歷鏈表
if ((entry.hash == hash) && entry.key.equals(key)) {
V old = entry.value;
entry.value = value;
return old;
}
}
addEntry(hash, key, value, index);
return null;
}
private void addEntry(int hash, K key, V value, int index) {
modCount++;
Entry tab[] = table;
if (count >= threshold) {
// Rehash the table if the threshold is exceeded
rehash();
tab = table;
hash = key.hashCode();
index = (hash & 0x7FFFFFFF) % tab.length;
}
// Creates the new entry.
@SuppressWarnings("unchecked")
Entry e = (Entry) tab[index];
tab[index] = new Entry<>(hash, key, value, e);
count++;
}
擴容
遍歷，重新計算index，并填入newMap
protected void rehash() {
int oldCapacity = table.length;
Entry[] oldMap = table;
// overflow-conscious code
int newCapacity = (oldCapacity << 1) + 1;
if (newCapacity - MAX_ARRAY_SIZE > 0) {
if (oldCapacity == MAX_ARRAY_SIZE)
// Keep running with MAX_ARRAY_SIZE buckets
return;
newCapacity = MAX_ARRAY_SIZE;
}
Entry[] newMap = new Entry[newCapacity];
modCount++;
threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
table = newMap;
for (int i = oldCapacity ; i-- > 0 ;) {
for (Entry old = (Entry)oldMap[i] ; old != null ; ) {
Entry e = old;
old = old.next;
int index = (e.hash & 0x7FFFFFFF) % newCapacity;
e.next = (Entry)newMap[index]; //反轉鏈表
newMap[index] = e;
}
}
}
TreeMap
紅黑樹是平衡二叉樹排序樹，我們來看下它的特性
紅黑樹特性
二叉排序樹特性
是一棵空樹，
或者是具有下列性質的二叉樹
左子樹也是二叉排序樹，且非空左子樹上所有結點的值均小于它的根結點的值
右子樹也是二叉排序樹，且非空右子樹上所有結點的值均大于它的根結點的值
平衡二叉樹特性
它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1
左右兩個子樹都是一棵平衡二叉樹。
紅黑樹的特性:
節點是紅色或黑色。
根節點是黑色。
每個葉節點（NIL節點，空節點）是黑色的。
每個紅色節點的兩個子節點都是黑色。(從每個葉子到根的所有路徑上不能有兩個連續的紅色節點)
從任一節點到其每個葉子的所有路徑都包含相同數目的黑色節點。
查找
基于遞歸的思想處理
/*查找大于等于K的最小節點*/
final Entry getCeilingEntry(K key) {
Entry p = root;
while (p != null) {
int cmp = compare(key, p.key);
if (cmp < 0) { //key < p.key
if (p.left != null)
p = p.left;
else
return p;
} else if (cmp > 0) { key > p.key
if (p.right != null) {
p = p.right;
} else { //叔節點
Entry parent = p.parent;
Entry ch = p;
while (parent != null && ch == parent.right) {
ch = parent;
parent = parent.parent;
}
return parent;
}
} else
return p;
}
return null;
}
/*查找小于等于K的最大節點, 原理類似，省略*/
final Entry getFloorEntry(K key) {
...
}
/*查找大于K的最大節點, 原理類似，省略*/
final Entry getHigherEntry(K key) {
...
}
/*查找小于K的最大節點, 原理類似，省略*/
final Entry getLowerEntry(K key) {
...
}
恢復平衡
插入/刪除節點會破壞紅黑樹的平衡，為了恢復平衡，可以進行2類操作：旋轉和著色
旋轉
左旋
private void rotateLeft(Entry p) {
if (p != null) {
Entry r = p.right;
p.right = r.left;
if (r.left != null)
r.left.parent = p;
r.parent = p.parent;
if (p.parent == null)
root = r;
else if (p.parent.left == p)
p.parent.left = r;
else
p.parent.right = r;
r.left = p;
p.parent = r;
}
}
右旋
插入節點
插入節點總是為紅色
場景分析
情形1: 新節點位于樹的根上，沒有父節點
將新節點(根節點設置為黑色）
情形2: 新節點的父節點是黑色
無處理
情形3:新節點的父節點是紅色，分3類情況
3A: 當前節點的父節點是紅色，且當前節點的祖父節點的另一個子節點（叔叔節點）也是紅色。
3B: 當前節點的父節點是紅色，叔叔節點是黑色，且當前節點是其父節點的右孩子
3C: 當前節點的父節點是紅色，叔叔節點是黑色，且當前節點是其父節點的左孩子
總結
==為了保證紅黑樹特性5，插入的節點需要是紅色==
==根節點是紅色或者黑色，都不影響紅黑樹特性5，也就是說當父節點和叔節點均為紅色時，可以通過將互換祖父與父、叔節點的顏色來上朔不平衡，并最終通過將根節點從紅色設置為黑色來解決不平衡==
==當叔節點為黑色，父節點為紅色時，按照上述思路將父節點與祖父節點顏色互換后，必然會使得當前節點所在的子樹黑色節點過多而影響紅黑樹特性5，因此需要通過旋轉將黑色節點向相反方向轉移，以平衡根的兩側==
3A
當前節點的父節點是紅色，且當前節點的祖父節點的另一個子節點（叔叔節點）也是紅色。
處理思路:
父節點與叔節點變黑色
祖父節點變紅色
當前節點轉換為祖父節點，迭代處理
graph TD
1[祖父紅]-->2[父黑]
1-->3[叔黑]
2-->4{新紅}
2-->5[兄]
3B
當前節點的父節點是紅色，叔叔節點是黑色，且當前節點是其父節點的右孩子
處理思路:
左旋/右旋父節點
后續操作見3C
3C
當前節點的父節點是紅色，叔叔節點是黑色，且當前節點是其父節點的左孩子
處理思路
父節點設置為黑色
祖父節點設置為紅色
右旋/左旋祖父節點
private void fixAfterInsertion(Entry x) {
x.color = RED; //新插入的節點為紅色
while (x != null && x != root && x.parent.color == RED) {
// x的父節點 == x的父-父-左子節點
if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
Entry y = rightOf(parentOf(parentOf(x)));
// y為x的叔節點
if (colorOf(y) == RED) { //叔節點為紅色, 3A
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
} else { //叔節點為黑色
if (x == rightOf(parentOf(x))) { //3B
x = parentOf(x);
rotateLeft(x);
}
//3C
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateRight(parentOf(parentOf(x)));
}
} else {
Entry y = leftOf(parentOf(parentOf(x)));
if (colorOf(y) == RED) { //3A
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
} else {
if (x == leftOf(parentOf(x))) { //3C
x = parentOf(x);
rotateRight(x);
}
//3B
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateLeft(parentOf(parentOf(x)));
}
}
}
root.color = BLACK;
}
刪除節點
情況分析
被刪除節點沒有兒子，即為葉節點。那么，直接將該節點刪除就OK了。
被刪除節點只有一個兒子。那么，直接刪除該節點，并用該節點的唯一子節點頂替它的位置。
被刪除節點有兩個兒子。那么，先找出它的后繼節點；然后把“它的后繼節點的內容”復制給“該節點的內容”；之后，刪除“它的后繼節點”。在這里，后繼節點相當于替身，在將后繼節點的內容復制給"被刪除節點"之后，再將后繼節點刪除。這樣就巧妙的將問題轉換為"刪除后繼節點"的情況了，下面就考慮后繼節點。 在"被刪除節點"有兩個非空子節點的情況下，它的后繼節點不可能是雙子非空。既然"的后繼節點"不可能雙子都非空，就意味著"該節點的后繼節點"要么沒有兒子，要么只有一個兒子。若沒有兒子，則按"情況①"進行處理；若只有一個兒子，則按"情況② "進行處理。
private void deleteEntry(Entry p) {
modCount++;
size--;
// 情況3 將p的值賦予后繼節點s，并轉換為刪除s
if (p.left != null && p.right != null) {
Entry s = successor(p);
p.key = s.key;
p.value = s.value;
p = s;
}
// 情況2
Entry replacement = (p.left != null ? p.left : p.right);
if (replacement != null) {
// Link replacement to parent
replacement.parent = p.parent;
if (p.parent == null)
root = replacement;
else if (p == p.parent.left)
p.parent.left = replacement;
else
p.parent.right = replacement;
// Null out links so they are OK to use by fixAfterDeletion.
p.left = p.right = p.parent = null;
// Fix replacement
if (p.color == BLACK)
fixAfterDeletion(replacement);
} else if (p.parent == null) {
root = null; //p是根節點
} else { //情況1
if (p.color == BLACK)
fixAfterDeletion(p);
if (p.parent != null) {
if (p == p.parent.left)
p.parent.left = null;
else if (p == p.parent.right)
p.parent.right = null;
p.parent = null;
}
}
}
重新平衡
刪除節點x，根據上文分析，x有0或1個子節點
x是紅色節點，那么刪除它不會破壞平衡
如果x是黑色
4A 兄節點為紅色
4B 兄節點的兩個子節點均為黑色
4C 兄節點的遠端子節點為黑色，另一個為紅色或無
4D 兄節點的遠端子節點為紅色，另一個為紅色或無
兄節點及其子樹的黑色節點應該比X多一個
4A 兄節點為紅色
處理方法：
兄節點設置為黑色
父節點設置為紅色
左旋/右旋父節點，變形為B/C/D情況
4B 兄節點的兩個子節點均為黑色
處理方法：
兄節點設置為紅色
x設置為父節點，上溯不平衡
4C 遠端侄節點為黑色，另一個為紅色或無
處理方法
近端侄節點設置為黑色
兄節點設置為紅色
右旋/左旋兄節點
轉換為4D處理
4D 兄節點為黑色，遠端侄節點為紅色，一個為紅色或無
處理方法
將父節點的顏色賦予兄節點
將父節點設置為黑色
將遠端侄節點的顏色設置為黑色
左旋父節點
