摘要：底層的數據結構就是數組鏈表紅黑樹，紅黑樹是在中加進來的。負載因子哈希表中的填滿程度。
前言
把 Java 容器的學習筆記放到 github 里了，還在更新~
其他的目前不打算抽出來作為文章寫，感覺挖的還不夠深，等對某些東西理解的更深了再寫文章吧
Java 容器
目錄如下：
Java 容器
一、概述
二、源碼學習
1. Map
1.1 HashMap
1.2 LinkedHashMap
1.3 TreeMap
1.4 ConcurrentHashMap
2. Set
2.1 HashSet
2.2 LinkedHashSet
2.3 TreeSet
3. List
3.1 ArrayList
3.2 LinkedList
3.3 Vector
4. Queue
4.1 LinkedList
4.2 PriorityQueue
后面還會對并發、和一些 Java 基礎的東西做整理
為啥要做那么多筆記呢？個人比較喜歡把東西寫出來~嘻嘻
如果真的有人認真看了的話，要是有錯誤或者對我寫的感到迷惑的地方，再或者希望對哪些知識再深入了解一些，請盡管說出來，給我的個人博客留言 or 發郵件 or 提 issue 都 ok，我會非常感謝你的~
個人博客鏈接
一、HashMap簡介
看一下官方文檔中對HashMap的描述
* Hash table based implementation of the Map interface. This
* implementation provides all of the optional map operations, and permits
* null values and the null key. (The HashMap
* class is roughly equivalent to Hashtable, except that it is
* unsynchronized and permits nulls.) This class makes no guarantees as to
* the order of the map; in particular, it does not guarantee that the order
* will remain constant over time.
HashMap 是基于哈希表的 Map 接口的實現。
允許使用 null 值和 null 鍵。
除了不同步和允許使用 null 之外，HashMap 類與 Hashtable 大致相同。
不保證順序
不保證該順序恒久不變。
HashMap 底層的數據結構就是數組+鏈表+紅黑樹，紅黑樹是在 JDK 1.8 中加進來的。尤其是在 JDK 1.8 對它優化以后，HashMap 變成了一個更強的容器...嗯...真的很強。
當新建一個 HashMap 時，就會初始化一個數組。在這個數組中，存放的是 Node 類，它擁有指向多帶帶的一個鏈表的頭結點的引用，這個鏈表是用來解決 hash 沖突的（如果不同的 key 被映射到數組中同一位置的話，就將其放入鏈表中，從而解決沖突）。
大概就是這樣子... ?(? ???ω??? ?)?
數組
__
|__| 鏈表
__ __ __ __ __
|__|---> |__|->|__|->|__|->|__|->...
__
|__|
__
|__|
__
|__|
__
|__| : Node
但是，在 JDK 1.8 之前的這種做法，即使負載因子和 Hash 算法設計的再合理，也無法避免會出現鏈表過長的情況， 一旦鏈表過長，會嚴重影響 HashMap 的性能，所以，在 JDK 1.8 之后，使用了紅黑樹這個數據結構，當鏈表長度大于 8 時，該鏈表就會轉化成紅黑樹，利用紅黑樹快速增刪查改的特點提高 HashMap 的性能。
因為 HashMap 是不同步的，如果需要考慮線程安全，需要使用 ConcurrentHashMap，或者可以使用 Collections.synchronizedMap() 方法返回被指定 map 支持的同步的 map。
Map map = Collections.synchronizedMap(new HashMap<>());
二、源碼分析（基于JDK1.8）
1. 成員變量
// 默認初始容量是16，必須是2的冪
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
// 最大容量（必須是2的冪且小于2的30次方，傳入容量過大會被這個值替換）
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默認加載因子，加載因子就是指哈希表在其容量自動增加之前可以達到多滿的一種尺度
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 默認的轉換成紅黑樹的閾值，即鏈表長度達到該值時，該鏈表將轉換成紅黑樹
static final int TREEIFY_THRESHOLD = 8;
// 存儲Entry的默認空數組
static final Entry[] EMPTY_TABLE = {};
// 存儲Entry的數組，長度為2的冪。HashMap采用拉鏈法實現的，
// 每個Entry的本質是個單向鏈表
transient Entry[] table = (Entry[]) EMPTY_TABLE;
// HashMap的大小，即HashMap中實際存在的鍵值對數量
transient int size;
// 閾值，表示所能容納的key-value對的極限，用于判斷是否需要調整HashMap的容量
// 如果 table 還是空的，那么這個閾值就是 0 或者是默認的容量 16
int threshold;
// 加載因子實際大小
final float loadFactor;
// HashMap被修改的次數，用于 fail-fast 機制
transient int modCount;
其中需要特別注意的是capacity和load factor這兩個屬性
官方文檔中對其描述是：
The capacity is the number of buckets in the hash table, and the initial capacity is simply the capacity at the time the hash table is created.
The load factor is a measure of how full the hash table is allowed to get before its capacity is automatically increased.
capacity（容量）：就是buckets的數目。
load factor（負載因子）：哈希表中的填滿程度。
若加載因子設置過大，則填滿的元素越多，從而提高了空間利用率，但是沖突的機會增加了，沖突的越多，鏈表就會變得越長，那么查找效率就會變低；
若加載因子設置過小，則填滿的元素越少，那么空間利用率就會降低，表中數據將變得更加稀疏，但是沖突的機會減小了，這樣鏈表就不會太長，查找效率就會變高。
一般，如果機器內存足夠，想增加查找速度，可以將load factor設小一點；相反，如果內存不足，并且對查找速度要求不高，可以將load factor設大一點。
2. 靜態內部類 Node
Node 實際上就是一個單鏈表，它實現了Map.Entry接口，其中next也是一個Node對象，用來處理hash沖突，形成一個鏈表。
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;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
// 判斷兩個node是否equal（必須key和value都相等）
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry e = (Map.Entry)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
3. 構造函數
HashMap 有四個構造函數
/**
用指定的初始容量和負載因子創建HashMap
*/
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
/**
用指定的容量創建HashMap，負載因子為默認的0.75
*/
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
/**
均使用默認值(初始容量：16 默認負載因子：0.75)
*/
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
/**
用指定的一個 map 構造一個新HashMap
新的 HashMap 的負載因子為默認值 0.75，容量為足以裝載該 map 的容量，會在 putMapEntries 中設置
*/
public HashMap(Map m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
4. 確定哈希桶數組索引的位置
確定位置這部分是很重要的，無論增刪查鍵值對，首先都要定位到哈希桶數組的位置！理想的情況就是數組中每個位置都只有一個元素，這樣在用算法求得這個位置后，我們就能直接命中該元素，不用再遍歷鏈表了，這樣可以極大地優化查找的效率.
在源碼中，采用的方法就是先根據 hashCode 先計算出 hash 值，然后根據 hash 值再求得索引，從而找到位置。
求hash值
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
（">>>"為按位右移補零操作符。左操作數的值按右操作數指定的位數右移，移動得到的空位以零填充。）
hash 值的計算主要分三步：
取key的hashCode值
高位運算
對1、2進行異或運算得到hash值
計算索引
// 此處取的put方法片段，這里就是用(n - 1) & hash 計算的索引（n為表的長度）
if ((p = tab[i = (n - 1) & hash]) == null)
計算方法其實就是取模運算。
對于計算索引的取模運算，是一個非常非常巧妙的運算~ ヽ(??▽?)ノ
它是用 hash & (n - 1) 得到索引值，因為 HashMap 底層數組的長度總是 2 的 n 次方（這是 HashMap 在速度上的優化），通過下面這個函數去保證 table 的長度為 2 的次冪。
// 這個靜態函數的作用就是返回一個比 cap 大但是又最接近 cap 的 2 次冪的整數
// 原理就是通過不斷地 位或 和 按位右移補零 操作，
// 將 n 變成 0..0111..111 這種形式，最后 + 1，就變成了 2 的次冪
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;
}
有了這個前提： n 一定為 2 的 n 次方，那么這個表達式才能等價于 hash % n，為什么不直接用 hash % n 呢？因為 & 比 % 具有更高的效率呀，所以采用的是 hash & (n - 1) 而不是 hash % n。
那么為什么n 為 2 的 n 次方時 hash & (n - 1) 可以等價于對 n 取模呢？
我是這樣想的
首先，n，即鏈表長度，為 2 的 n 次方，那么 n 就可以表示成 100...00 的這種樣子，那么 n - 1 就是 01111...11。
如果 hash < n，& 后都是 hash 本身。
如果 hash = n，& 后結果為 0。
如果 hash > n，& 過后相當于 hash - k*n，即 hash % n。
其次，因為 n 為 2 的次冪，是偶數，偶數最后一位是 0，而 n - 1 肯定是奇數，奇數的最后一位是 1，這樣便保證了 hash & (n - 1) 的最后一位可能為 0 也可能為 1，這樣便可以保證散列的均勻性，即均勻分布在數組 table 中；而如果 n 為奇數，則 n - 1 肯定是偶數，那么它的最后一位肯定是 0，這樣 hash & (n - 1) 得到的結果的最后一位肯定是 0，即只能為偶數，這樣任何 hash 值都會被映射到數組的偶數下標位置上，這就浪費了近一半的空間！
因此，HashMap 的作者要求鏈表的長度必須為 2 的整數次冪，應該就是為了這樣能使不同 hash 值發生碰撞的概率較小，讓元素在哈希表中均勻的散列。
5. put方法源碼分析
put的過程大致是：
根據key計算hash值
判斷tab是否為空，若為空則進行resize()擴容
根據hash值計算出索引
如果沒有碰撞就直接放入
如果有碰撞，就先放到鏈表里
若鏈表長度超過8（默認的TREEIFY_THRESHOLD），則轉換成紅黑樹再放
如果key已經存在，就覆蓋其oldValue
插入成功后，如果size > threshold，就要擴容
public V put(K key, V value) {
// 計算hash值
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
// tab為哈希表數組，p為我們要找的那個插入位置的節點
Node[] tab; Node p; int n, i;
// 若tab為空，就創建一個（進行擴容操作）
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//根據key計算hash值并處理后得到索引，如果表的這個位置為空，則直接插入
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
// 如果不為空
else {
Node e; K k;
// 判斷key是否存在，如果存在，則直接覆蓋其value
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 判斷該鏈表是否為TreeNode，如果是，紅黑樹直接插入鍵值對
else if (p instanceof TreeNode)
e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
// 如果不是，則遍歷鏈表，然后插入
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 鏈表長度大于8，則轉換成紅黑樹，并插入鍵值對
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 插入
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 如果超過閾值，則進行擴容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
6. get方法源碼分析
get方法和put方法過程類似
public V get(Object key) {
Node e;
// 計算hash值
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node getNode(int hash, Object key) {
Node[] tab; Node first, e; int n; K k;
// 如果表非空，并且根據計算出的索引值對應的值非空
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 直接命中
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// 未直接命中
if ((e = first.next) != null) {
// 在紅黑樹中get
if (first instanceof TreeNode)
return ((TreeNode)first).getTreeNode(hash, key);
// 在鏈表中get
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
7. resize() 的擴容機制
為什么要進行 resize?
假設 table 的長度為 n，總共需要放入 HashMap 的鍵值對數量為 m，那么，大約每條鏈表的長度就是 m / n，查找的時間復雜度也就是 O(m / n)，顯然，如果要盡量降低時間復雜度，需要加大 n，也就是對 table 擴容。
什么時候進行resize?
在 put 過程中，如果發現當前 HashMap 的 size 已經超過了 load factor 希望占的比例，那么就會進行 resize 操作。
下面是對 resize 源碼的分析，這段我覺得是最艱難的一段。。這還跳過了紅黑樹 :(′□`」 ∠):
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;
}
// 如果沒超過最大值，并且假設容量 double 后也不超過最大值，
// 那就擴容為原來的 2 倍，
// 然后再看原來的容量是不是還夠
// 如果不夠了，閾值再 double，否則只是擴容，不改變閾值
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
// 從閾值中取出 resize 應該擴容的值
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
// oldCap = 0
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;
// 創建一個新的 table
@SuppressWarnings({"rawtypes","unchecked"})
Node[] newTab = (Node[])new Node[newCap];
// 指向新的 table
table = newTab;
if (oldTab != null) {
// 把每個bucket都移動到新的buckets中
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)
// 將樹上的結點 rehash，然后放到新位置，紅黑樹這塊以后在分析
((TreeNode)e).split(this, newTab, j, oldCap);
else { // preserve order
// 進行鏈表復制
// lo鏈的新索引值和以前相同
// hi鏈的新索引值為：原索引值 + oldCap
Node loHead = null, loTail = null;
Node hiHead = null, hiTail = null;
Node next;
do {
next = e.next;
/**
(e.hash & oldCap) == 0 這個地方比較難理解，但也是擴容最關鍵的地方
假設現在 (e.hash & oldCap) == 0 為 true
oldCap 和 new Cap 肯定都是 2 的次冪，也就是 100... 這種形式，那么假如現在 oldCap = 16，
那么原索引為
e.hash & (oldCap - 1) = e.hash & 01111 --> index ①
新的索引為
e.hash & (newCap - 1) = e.hash & 11111
同時我們已知 e.hash & oldCap = 0，
即 e.hash & 10000 = 0 ②
通過 ① ② 就可以推出
e.hash & 11111 --> index
即索引位置不變
*/
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
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;
}
擴容部分完結撒花 ★,°:.☆(￣▽￣)/$:.°★
三、關于 HashMap 的線程安全性
HashMap 不是線程安全的，它在被設計的時候就沒有考慮線程安全，因為這本來就不是一個并發容器，相應的并發容器是 ConcurrentHashMap，那么，HashMap 的線程不安全性主要體現在哪兒呢？
最著名的一個就是高并發環境下的死循環問題，具體是在 resize 時產生的。
這種死循環產生的主要原因是因為 1.7 的 resize 中，新的 table 采用的插入方式是隊頭插入（LIFO，后進先出），比如元素為 {3,5,7,9}，插入后就是 {9,7,5,9}，會將鏈表順序逆置，它這樣做主要是為了防止遍歷鏈表尾部，因為 resize 本來就是創建了一個新的 table，所以對于元素的順序不關心，因此采用隊頭插入的方式，如果是正常的從尾部插入的話，還需要先找到尾部的位置，增加了遍歷的消耗，而 resize 又正好不在乎元素順序，所以就使用的隊頭插入的方式。
但是這種方式帶來了一個問題，就是死循環，具體死循環怎么產生的我就不贅述了，因為網上有很多關于這個的具體分析，我要說的是，在 JDK 1.8 中，HashMap 除了加入了紅黑樹這個數據結構外還有一些其他的調整，在 resize 時對鏈表的操作，變成了兩對指針分別對 lo鏈 和 hi鏈 操作。
Node loHead = null, loTail = null;
Node hiHead = null, hiTail = null;
因為增加了xxTail指針，所以可以隨時找到尾部，避免遍歷尾部，因此可以直接在尾部插入，因而避免了死循環問題。
不過這不代表 JDK 1.8 的HashMap就是線程安全了的，因為很明顯還存在比如并發時元素的覆蓋之類的問題，所以多線程環境下還是建議使用 ConcurrentHashMap 或者進行同步操作。
