先看再點贊，給自己一點思考的時間，微信搜索【沉默王二】關注這個有顏值卻假裝靠才華茍且的程式員， 本文 GitHub github.com/itwanger 已收錄，里面還有一線大廠整理的面試題，以及我的系列文章，
List 系列差不多寫完了， 單執行緒環境下最重要的就是 ArrayList 和 LinkedList，多執行緒環境下最重要的就是 CopyOnWriteArrayList，新來的同學可以點擊鏈接回顧一下 List 的知識點，接下來，我要帶著 HashMap 去爬山了，注意不是六峰山，純粹就是為了鍛煉了一下身體，不不不，純粹是為了和 HashMap 拉近關系，同學們注意不要掉隊，
說一句很廢的話，HashMap 是一個 Map，用來存盤 key-value 的鍵值對，每個鍵都可以精確地映射到一個值，然后我們可以通過這個鍵快速地找到對應的值，
對于一個 List 來說，如果要找到一個值，時間復雜度為 ，如果 List 排序過的話，時間復雜度可以降低到
（二分查找法），但如果是 Map 的話，大多數情況下，時間復雜度能夠降低到
，
來看一下 HashMap 的特點：
HashMap 的鍵必須是唯一的，不能重復，
HashMap 的鍵允許為 null，但只能有一個這樣的鍵；值可以有多個 null，
HashMap 是無序的，它不保證元素的任何特定順序，
HashMap 不是執行緒安全的；多執行緒環境下，建議使用 ConcurrentHashMap，或者使用
Collections.synchronizedMap(hashMap)將 HashMap 轉成執行緒同步的，只能使用關聯的鍵來獲取值，
HashMap 只能存盤物件，所以基本資料型別應該使用其包裝器型別，比如說 int 應該為 Integer，
HashMap 實作了 Cloneable 和 Serializable 介面，因此可以拷貝和序列化，
01、HashMap 的重要欄位
HashMap 有 5 個非常重要的欄位，我們來了解一下，（JDK 版本為 14）
transient Node<K,V>[] table;
transient int size;
transient int modCount;
int threshold;
final float loadFactor;
1）table 是一個 Node 型別的陣列，默認長度為 16，在第一次執行 resize() 方法的時候初始化，
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
final HashMap.Node<K,V>[] resize() {
newCap = DEFAULT_INITIAL_CAPACITY;
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
}
Node 是 HashMap 的一個內部類，實作了 Map.Entry 介面，本質上是一個鍵值對，
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
HashMap.Node<K,V> next;
Node(int hash, K key, V value, HashMap.Node<K,V> next) {
...
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
public final int hashCode() {
...
}
public final V setValue(V newValue) {
...
}
public final boolean equals(Object o) {
...
}
}
2）size 就是 HashMap 中實際存盤的鍵值對數量，它和 table 的 length 是有區別的，
為了說明這一點，我們來看下面這段代碼：
HashMap<String,Integer> map = new HashMap<>();
map.put("1", 1);
宣告一個 HashMap，然后 put 一個鍵值對，在 put() 方法處打一個斷點后進入，等到該方法臨近結束的時候加一個 watch（table.length），然后就可以觀察到如下結果，
也就是說，陣列的大小為 16，但 HashMap 的大小為 1，
3）modCount 主要用來記錄 HashMap 實際操作的次數，以便迭代器在執行 remove() 等操作的時候快速拋出 ConcurrentModificationException，因為 HashMap 和 ArrayList 一樣，也是 fail-fast 的，
關于 ConcurrentModificationException 的更多資訊，請點擊下面的鏈接查看 03 小節的內容，
4）threshold 用來判斷 HashMap 所能容納的最大鍵值對數量，它的值等于陣列大小 * 負載因子，默認情況下為 12（16 * 0.75），也就是第一次執行 resize() 方法的時候，
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
static final float DEFAULT_LOAD_FACTOR = 0.75f;
final HashMap.Node<K,V>[] resize() {
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
5）loadFactor 為負載因子，默認的 0.75 是對空間和時間效率上的一個平衡選擇，一般不建議修改，像我這種作業了十多年的老菜鳥，就從來沒有修改過這個值，
02、HashMap 的 hash 演算法
Hash，一般譯作“散列”，也有直接音譯為“哈希”的，這玩意什么意思呢？就是把任意長度的資料通過一種演算法映射到固定長度的域上（散列值），
再直觀一點，就是對一串資料 wang 進行雜糅，輸出另外一段固定長度的資料 er——作為資料 wang 的特征，我們通常用一串指紋來映射某一個人，別小瞧手指頭那么大點的指紋，在你所處的范圍內很難找出第二個和你相同的（人的散列演算法也好厲害，有沒有？），
對于任意兩個不同的資料塊，其散列值相同的可能性極小，也就是說，對于一個給定的資料塊，找到和它散列值相同的資料塊極為困難，再者，對于一個資料塊，哪怕只改動它的一個位元位，其散列值的改動也會非常的大——這正是 Hash 存在的價值！
同學們已經知道了，HashMap 的底層資料結構是一個陣列，那不管是增加、洗掉，還是查找鍵值對，定位到陣列的下標非常關鍵，
那 HashMap 是通過什么樣的方法來定位下標呢？
第一步，hash() 方法：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
第二步，putVal() 方法中的一行代碼：
n = (tab = resize()).length;
i = (n - 1) & hash;
為了更容易理解，我把這兩步的方法合并到了一起：
String [] keys = {"沉","默","王","二"};
for (String k : keys) {
int hasCode = k.hashCode();
int right = hasCode >>> 16;
int hash = hasCode ^ right;
int i = (16 - 1) & hash;
System.out.println(hash + " 下標：" + i);
}
1）k.hashCode() 用來計算鍵的 hashCode 值，對于任意給定的物件，只要它的 hashCode() 回傳值是相同，那么 hash() 方法計算得到的 Hash 碼就總是相同的，
要能夠做到這一點，就要求作為鍵的物件必須是不可變的，并且 hashCode() 方法要足夠的巧妙，能夠最大可能回傳不重復的 hashCode 值，比如說 String 類，
public int hashCode() {
int h = hash;
if (h == 0 && value.length > 0) {
char val[] = value;
for (int i = 0; i < value.length; i++) {
h = 31 * h + val[i];
}
hash = h;
}
return h;
}
2）>>> 為無符號右移運算子，高位補 0，移多少位補多少個 0，
3）^ 為異或運算子，其運算規則為 1^0 = 1、1^1 = 0、0^1 = 1、0^0 = 0，
4）& 為按位與運算子，運算規則是將兩邊的數轉換為二進制位，然后運算最終值，運算規則即（兩個為真才為真）1&1=1、1&0=0、0&1=0、0&0=0，
關于 >>>、^、& 運算子，涉及到二進制，本篇文章不再深入研究，感興趣的同學可以自行研究一下，
假如四個字串分別是"沉","默","王","二"，它們通過 hash() 方法計算后值和下標如下所示：
27785 下標：9
40664 下標：8
29579 下標：11
20108 下標：12
應該說，這樣的 hash 演算法非常巧妙，尤其是第二步，
HashMap 底層陣列的長度總是 2 的 n 次方，當 length 總是 2 的 n 次方時，
(length - 1) & hash運算等價于對陣列的長度取模，也就是hash%length，但是 & 比 % 具有更高的效率，
03、HashMap 的 put() 方法
HashMap 的 hash 演算法我們是明白了，但似乎有一絲疑慮，就是萬一計算后的 hash 值沖突了怎么辦？
比如說，“沉X”計算后的 hash 值為 27785，其下標為 9，放在了陣列下標為 9 的位置上；過了一會，又來個“沉Y”計算后的 hash 值也為 27785，下標也為 9，也需要放在下標為 9 的位置上，該怎么辦？
為了模擬這種情況，我們來新建一個自定義的鍵類，
public class Key {
private final String value;
public Key(String value) {
this.value = value;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass())
return false;
Key key = (Key) o;
return value.equals(key.value);
}
@Override
public int hashCode() {
if (value.startsWith("沉")) {
return "沉".hashCode();
}
return value.hashCode();
}
}
在 hashCode() 方法中，加了一個判斷，如果鍵是以“沉”開頭的話，就回傳“沉”的 hashCode 值，這就意味著“沉X”和“沉Y”將會出現在陣列的同一個下標上，
HashMap<Key,String> map = new HashMap<>();
map.put(new Key("沉X"),"沉默王二X");
map.put(new Key("沉Y"),"沉默王二Y");
那緊接著來看一下 put() 方法的原始碼：
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
put() 方法會先呼叫 hash() 方法計算 key 的 hash 值，然后再呼叫內部方法 putVal()：
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
HashMap.Node<K,V>[] tab; HashMap.Node<K,V> p; int n, i;
// ①、陣列 table 為 null 時，呼叫 resize 方法創建默認大小的陣列
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);
else {
HashMap.Node<K,V> e; K k;
// ③、如果鍵已經存在了，并且 hash 值相同，直接覆寫
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// ④、紅黑樹處理
else if (p instanceof HashMap.TreeNode)
e = ((HashMap.TreeNode<K,V>)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;
}
// 如果鍵已經存在了，并且 hash 值相同，直接覆寫
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;
}
代碼里我加了一些注釋，同學們一定要花點時間看一下，
如果哈希沖突的話，會執行 ② 處對應的 else 陳述句，先判斷鍵是否相等，相等的話直接覆寫；否則執行 ④，做紅黑樹處理；如果不是，會執行 ⑤，把上一個節點的 next 賦值為新的 Node，
也就是說，如果哈希沖突了，會在陣列的同一個位置上增加鏈表，如果鏈表的長度大于 8，將會轉化成紅黑樹進行處理，
以上就是大牛們嘴里常說的“鏈地址法”，簡單點說，就是陣列加鏈表，由于鏈表的查詢效率比較低（時間復雜度為 ），Java 8 又追加了紅黑樹（時間復雜度為
），
留個小作業哈，同學們可以研究一下，當鍵為 null 的時候，鍵值對存放在什么位置上？
04、HashMap 的 get() 方法
理解了 HashMap 的 hash 演算法和 put() 方法，get() 方法就很容易理解，
public V get(Object key) {
HashMap.Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
首先計算 key 的 hash 值，當 hash 值確定后，鍵值對在陣列中的下標位置也就確定了，然后再呼叫 getNode() 方法：
final HashMap.Node<K,V> getNode(int hash, Object key) {
HashMap.Node<K,V>[] tab; HashMap.Node<K,V> 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) {
if (first instanceof HashMap.TreeNode)
return ((HashMap.TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
其中 first = tab[(n - 1) & hash] 就可以快速的確定鍵對應的值，如果鍵相等并且鍵的 hash 相等，則直接回傳；如果鍵的哈希沖突了，就先判斷是不是紅黑樹，不是的話就遍歷鏈表，
05、最后
說句實在話，在寫這篇文章之前，我對 HashMap 的認知并沒有這么深刻，但寫完這篇文章后，我敢拍著胸脯信誓旦旦地說：“HashMap 我真的掌握了，同學們誰以后再問我，就可以把這篇文章甩給他了，”
這次爬山雖然很累，但確實識訓很大，值了！
我是沉默王二，一枚有顏值卻假裝靠才華茍且的程式員，關注即可提升學習效率，別忘了三連啊，點贊、收藏、留言，我不挑，奧利給??，
注：如果文章有任何問題，歡迎毫不留情地指正，
如果你覺得文章對你有些幫助，歡迎微信搜索「沉默王二」第一時間閱讀，回復關鍵字「小白」可以免費獲取我肝了 4 萬+字的 《Java 小白從入門到放肆》2.0 版；本文 GitHub github.com/itwanger 已收錄，歡迎 star，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/108961.html
標籤：Java
上一篇：深入理解 Spring Cloud 核心組件與底層原理
下一篇：java_Lambda運算式