前言
手執煙花以謀生 心懷詩意以謀愛
不論我是否去記錄，在往昔與未來的無限歲月中，仍會有人奮起，有人沉淪，有人成為英雄，有人扮演小丑，有人挺身而出，有人迷惘沉淪。但你只需——“在繁華中自律，在落魄中自愈，在謀生的路上不拋棄良知，在謀愛的路上不丟失最嚴，這次我站在風中，任你大霧四起。”
HashMap的設計原理
1. HashMap設計思路：- Map是一種以鍵值對存儲數據的容器，而 HashMap 則是借助了鍵值 Key 的 hashcode 值來組織存儲，使得可以非?？焖俸透咝У氐馗鶕I值 key 進行數據的存取。
- 對于鍵值對，HashMap 內部會將其封裝成一個對應的 Entry 對象，即 Entry 對象是鍵值對的組織形式；
- 對于每個對象而言，JVM 都會為其生成一個 hashcode 值。HashMap 在存儲鍵值對 Entry 的時候，會根據 Key 的 hashcode 值，以某種映射關系，決定應當將這對鍵值對 Entry 存儲在 HashMap 中的什么位置上；
- 當通過 Key 值取數據的時候，然后根據 Key 值的 hashcode 和 內部映射條件，直接定位到 Key 對應的 Value 值存放在什么位置，可以非常高效地將 Value 值取出。
HashMap 的哈希函數設計
hash 函數是先拿到 key 的 hashcode，是一個32位的 int 值，然后讓 hashcode 的高16位和低16位進行異或操 作
也叫擾動函數，這么設計有二點原因
- 一定要盡可能降低 hash 碰撞，越分散越好；
- 算法一定要盡可能高效，因為這是高頻操作, 因此采用位運算；
什么是Hash？
Hash，一般翻譯做“散列”，也有直接音譯為“哈?！钡模褪前讶我忾L度的 `輸入`，通過散列算法變換成固定長度的 `輸出`，該輸出就是散列值。ok，這樣的定義可能比較抽象。咱們結合上面提到的方案二的例子一句一句解釋。? HashMap 的數據結構（JDK 1.8）
本文說的是 JDK1.8 版本的，內部使用數組 + 鏈表紅黑樹
JDK1.8 對 HashMap 主要做了哪些優化呢？
- 數組 + 鏈表改成了數組 + 鏈表或紅黑樹；
- 鏈表的插入方式從頭插法改成了尾插法，簡單說就是插入時，如果數組位置上已經有元素，1.7 將新元 素放到數組中，原始節點作為新節點的后繼節點，1.8 遍歷鏈表，將元素放置到鏈表的最后；
- 擴容的時候 1.7 需要對原數組中的元素進行重新 hash 定位在新數組的位置，1.8 采用更簡單的判斷邏 輯，位置不變或索引 + 舊容量大小；
- 在插入時，1.7 先判斷是否需要擴容，再插入，1.8 先進行插入，插入完成再判斷是否需要擴容；
?為什么要做這幾點優化
- 防止發生 hash 沖突，鏈表長度過長，將時間復雜度由 O(n) 降為 O(logn) ;
- 因為 1.7 頭插法擴容時，頭插法會使鏈表發生反轉，多線程環境下會產生環； A 線程在插入節點 B，B 線程也在插入，遇到容量不夠開始擴容，重新 hash，放置元素，采用頭插法， 后遍歷到的 B 節點放入了頭部，這樣形成了環，如下圖所示：
1.7 的擴容調用 transfer 代碼，如下所示：
void transfer(Entry[] newTable, boolean rehash) {int newCapacity = newTable.length;for (Entry<K,V> e : table) {while(null != e) {Entry<K,V> next = e.next;if (rehash) {e.hash = null == e.key ? 0 : hash(e.key);} int i = indexFor(e.hash, newCapacity);e.next = newTable[i]; //A線程如果執行到這一行掛起，B線程開始進行擴容newTable[i] = e;e = next;}}} - 擴容的時候為什么 1.8 不用重新 hash 就可以直接定位原節點在新數據的位置 這是由于擴容是擴大為原數組大小的 2 倍，用于計算數組位置的掩碼僅僅只是高位多了一個 1，怎么理 解呢？ 擴容前長度為 16，用于計算 (n-1) & hash 的二進制 n-1 為 0000 1111，擴容為 32 后的二進制就高位多 了 1，為 0001 1111。 因為是 & 運算，1 和任何數 & 都是她本身，那就分二種情況，如下圖：原數據 hashcode 高位第 4 位為 0 和高位為 1 的情況； 第四位高位為 0，重新 hash 數值不變，第四位為 1，重新 hash 數值比原來大 16（舊數組的容量）
