一、HashMap簡介
看一下官方文檔中對HashMap的描述
* Hash table based implementation of the <tt>Map</tt> interface. This
* implementation provides all of the optional map operations, and permits
* <tt>null</tt> values and the <tt>null</tt> key. (The <tt>HashMap</tt>
* class is roughly equivalent to <tt>Hashtable</tt>, 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<K, V>
但是，在 JDK 1.8 之前的這種做法，即使負載因子和 Hash 算法設計的再合理，也無法避免會出現連結清單過長的情況， 一旦連結清單過長，會嚴重影響 HashMap 的性能，是以，在 JDK 1.8 之後，使用了紅黑樹這個資料結構，當連結清單長度大于 8 時，該連結清單就會轉化成紅黑樹，利用紅黑樹快速增删查改的特點提高 HashMap 的性能。
因為 HashMap 是不同步的，如果需要考慮線程安全，需要使用 ConcurrentHashMap，或者可以使用 Collections.synchronizedMap() 方法傳回被指定 map 支援的同步的 map。
Map<Integer, Integer> map = Collections.synchronizedMap(new HashMap<>());
二、源碼分析（基于JDK1.8）
1. 成員變量
// 預設初始容量是16，必須是2的幂
static final int DEFAULT_INITIAL_CAPACITY = << ; // aka 16
// 最大容量（必須是2的幂且小于2的30次方，傳入容量過大會被這個值替換）
static final int MAXIMUM_CAPACITY = << ;
// 預設加載因子，加載因子就是指哈希表在其容量自動增加之前可以達到多滿的一種尺度
static final float DEFAULT_LOAD_FACTOR = f;
// 預設的轉換成紅黑樹的門檻值，即連結清單長度達到該值時，該連結清單将轉換成紅黑樹
static final int TREEIFY_THRESHOLD = ;
// 存儲Entry的預設空數組
static final Entry<?,?>[] EMPTY_TABLE = {};
// 存儲Entry的數組，長度為2的幂。HashMap采用拉鍊法實作的，
// 每個Entry的本質是個單向連結清單
transient Entry<K,V>[] table = (Entry<K,V>[]) 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<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next; // 指向下一個節點
Node(int hash, K key, V value, Node<K,V> 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 < )
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= || 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<? extends K, ? extends V> 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) ? : (h = key.hashCode()) ^ (h >>> );
}
（”>>>”為按位右移補零操作符。左操作數的值按右操作數指定的位數右移，移動得到的空位以零填充。）
hash 值的計算主要分三步：
1. 取key的hashCode值
2. 高位運算
3. 對1、2進行異或運算得到hash值
計算索引
// 此處取的put方法片段，這裡就是用(n - 1) & hash 計算的索引（n為表的長度）
if ((p = tab[i = (n - ) & 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 - ;
n |= n >>> ;
n |= n >>> ;
n |= n >>> ;
n |= n >>> ;
n |= n >>> ;
return (n < ) ? : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + ;
}
有了這個前提： 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<K,V>[] tab; Node<K,V> p; int n, i;
// 若tab為空，就建立一個（進行擴容操作）
if ((tab = table) == null || (n = tab.length) == )
n = (tab = resize()).length;
//根據key計算hash值并處理後得到索引，如果表的這個位置為空，則直接插入
if ((p = tab[i = (n - ) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
// 如果不為空
else {
Node<K,V> 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<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 如果不是，則周遊連結清單，然後插入
else {
for (int binCount = ; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 連結清單長度大于8，則轉換成紅黑樹，并插入鍵值對
if (binCount >= TREEIFY_THRESHOLD - ) // -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<K,V> e;
// 計算hash值
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
// 如果表非空，并且根據計算出的索引值對應的值非空
if ((tab = table) != null && (n = tab.length) > &&
(first = tab[(n - ) & 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<K,V>)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<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? : oldTab.length;
int oldThr = threshold;
int newCap, newThr = ;
if (oldCap > ) {
// 如果超過最大值就不再擴容了
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 如果沒超過最大值，并且假設容量 double 後也不超過最大值，
// 那就擴容為原來的 2 倍，
// 然後再看原來的容量是不是還夠
// 如果不夠了，門檻值再 double，否則隻是擴容，不改變門檻值
else if ((newCap = oldCap << ) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << ; // double threshold
}
// 從門檻值中取出 resize 應該擴容的值
else if (oldThr > ) // 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 == ) {
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<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
// 指向新的 table
table = newTab;
if (oldTab != null) {
// 把每個bucket都移動到新的buckets中
for (int j = ; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
// 删除
oldTab[j] = null;
// 如果目前結點是尾結點
if (e.next == null)
// 重新計算索引值，然後放入元素
newTab[e.hash & (newCap - )] = e;
// 如果目前結點已經轉換成紅黑樹了
else if (e instanceof TreeNode)
// 将樹上的結點 rehash，然後放到新位置，紅黑樹這塊以後在分析
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
// 進行連結清單複制
// lo鍊的新索引值和以前相同
// hi鍊的新索引值為：原索引值 + oldCap
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> 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) == ) {
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<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
因為增加了xxTail指針，是以可以随時找到尾部，避免周遊尾部，是以可以直接在尾部插入，因而避免了死循環問題。
不過這不代表 JDK 1.8 的HashMap就是線程安全了的，因為很明顯還存在比如并發時元素的覆寫之類的問題，是以多線程環境下還是建議使用 ConcurrentHashMap 或者進行同步操作。
![Java集合架構——Map接口第三階段 JAVA常見對象的學習[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)