作者：阿進的寫字檯
主頁：https://www.cnblogs.com/homejim/p/10029796.html
一、HashMap在JAVA中的怎麼工作的？
基於Hash的原理
二、什麼是哈希？
最簡單形式的 hash，是一種在對任何變量/對象的屬性應用任何公式/算法後， 為其分配唯一代碼的方法。
一個真正的hash方法必須遵循下面的原則
哈希函數每次在相同或相等的對象上應用哈希函數時, 應每次返回相同的哈希碼。換句話說, 兩個相等的對象必須一致地生成相同的哈希碼。
Java 中所有的對象都有 Hash 方法。
Java中的所有對象都繼承 Object 類中定義的 hashCode() 函數的默認實現。 此函數通常通過將對象的內部地址轉換為整數來生成哈希碼，從而為所有不同的對象生成不同的哈希碼。
三、HashMap 中的 Node 類
Map的定義是： 將鍵映射到值的對象。
因此，HashMap 中必須有一些機制來存儲這個鍵值對。 答案是肯的。 HashMap 有一個內部類 Node，如下所示：
當然，Node 類具有存儲為屬性的鍵和值的映射。 key 已被標記為 final，另外還有兩個字段：next 和 hash。
在下面中， 我們將會理解這些屬性的必須性。
四、鍵值對在 HashMap中是如何存儲的
鍵值對在 HashMap 中是以 Node 內部類的數組存放的，如下所示：
transient Node[] table;
哈希碼計算出來之後， 會轉換成該數組的下標， 在該下標中存儲對應哈希碼的鍵值對， 在此先不詳細講解hash碰撞的情況。
該數組的長度始終是2的次冪， 通過以下的函數實現該過程
其原理是將傳入參數 (cap) 的低二進制全部變為1，最後加1即可獲得對應的大於 cap 的 2 的次冪作為數組長度。
為什麼要使用2的次冪作為數組的容量呢？
在此有涉及到 HashMap 的 hash 函數及數組下標的計算， 鍵(key)所計算出來的哈希碼有可能是大於數組的容量的，那怎麼辦？ 可以通過簡單的求餘運算來獲得，但此方法效率太低。HashMap中通過以下的方法保證 hash 的值計算後都小於數組的容量。
(n - 1) & hash
這也正好解釋了為什麼需要2的次冪作為數組的容量。由於n是2的次冪，因此，n-1類似於一個低位掩碼。通過與操作，高位的hash值全部歸零，保證低位才有效 從而保證獲得的值都小於n。
同時，在下一次 resize() 操作時， 重新計算每個 Node 的數組下標將會因此變得很簡單，具體的後文講解。以默認的初始值16為例
01010011 00100101 01010100 00100101
& 00000000 00000000 00000000 00001111
----------------------------------
00000000 00000000 00000000 00000101 //高位全部歸零，只保留末四位
// 保證了計算出的值小於數組的長度 n
但是，使用了該功能之後，由於只取了低位，因此 hash 碰撞會也會相應的變得很嚴重。這時候就需要使用「擾動函數」
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
該函數通過將哈希碼的高16位的右移後與原哈希碼進行異或而得到，以上面的例子為例
此方法保證了高16位不變， 低16位根據異或後的結果改變。計算後的數組下標將會從原先的5變為0。
使用了 「擾動函數」 之後， hash 碰撞的概率將會下降。 有人專門做過類似的測試， 雖然使用該 「擾動函數」 並沒有獲得最大概率的避免 hash 碰撞，但考慮其計算性能和碰撞的概率， JDK 中使用了該方法，且只hash一次。
五、哈希碰撞及其處理
在理想的情況下， 哈希函數將每一個 key 都映射到一個唯一的 bucket， 然而， 這是不可能的。哪怕是設計在良好的哈希函數，也會產生哈希衝突。
前人研究了很多哈希衝突的解決方法，在維基百科中，總結出了四大類
在 Java 的 HashMap 中， 採用了第一種 Separate chaining 方法(大多數翻譯為拉鍊法)+鏈表和紅黑樹來解決衝突。
在 HashMap 中， 哈希碰撞之後會通過 Node 類內部的成員變量 Node
static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
六、HashMap 的初始化
public HashMap();
public HashMap(int initialCapacity);
public HashMap(Map extends K, ? extends V> m);
public HashMap(int initialCapacity, float loadFactor);
HashMap 中有四個構造函數， 大多是初始化容量和負載因子的操作。以 public HashMap(int initialCapacity, float loadFactor) 為例
通過該函數進行了容量和負載因子的初始化，如果是調用的其他的構造函數， 則相應的負載因子和容量會使用默認值（默認負載因子=0.75， 默認容量=16）。在此時， 還沒有進行存儲容器 table 的初始化， 該初始化要延遲到第一次使用時進行。
七、HashMap 中哈希表的初始化或動態擴容
所謂的哈希表， 指的就是下面這個類型為內部類Node的 table 變量。
transient Node[] table;
作為數組， 其在初始化時就需要指定長度。在實際使用過程中， 我們存儲的數量可能會大於該長度，因此 HashMap 中定義了一個閾值參數(threshold)， 在存儲的容量達到指定的閾值時， 需要進行擴容。
我個人認為初始化也是動態擴容的一種， 只不過其擴容是容量從 0 擴展到構造函數中的數值（默認16）。 而且不需要進行元素的重hash.
7.1 擴容發生的條件
初始化的話只要數值為空或者數組長度為 0 就會進行。 而擴容是在元素的數量大於閾值（threshold）時就會觸發。
threshold = loadFactor * capacity
比如 HashMap 中默認的 loadFactor=0.75, capacity=16, 則
threshold = loadFactor * capacity = 0.75 * 16 = 12
那麼在元素數量大於 12 時， 就會進行擴容。 擴容後的 capacity 和 threshold 也會隨之而改變。
負載因子影響觸發的閾值，因此，它的值較小的時候，HashMap 中的 hash 碰撞就很少， 此時存取的性能都很高，對應的缺點是需要較多的內存；而它的值較大時，HashMap 中的 hash 碰撞就很多，此時存取的性能相對較低，對應優點是需要較少的內存；不建議更改該默認值，如果要更改，建議進行相應的測試之後確定。
7.2 再談容量為2的整數次冪和數組索引計算
前面說過了數組的容量為 2 的整次冪， 同時， 數組的下標通過下面的代碼進行計算
index = (table.length - 1) & hash
該方法除了可以很快的計算出數組的索引之外， 在擴容之後， 進行重 hash 時也會很巧妙的就可以算出新的 hash 值。 由於數組擴容之後， 容量是現在的 2 倍， 擴容之後 n-1 的有效位會比原來多一位， 而多的這一位與原容量二進制在同一個位置。 示例
這樣就可以很快的計算出新的索引啦
7.3 步驟
- 先判斷是初始化還是擴容， 兩者在計算newCap和newThr時會不一樣
- 計算擴容後的容量，臨界值。
- 將hashMap的臨界值修改為擴容後的臨界值
- 根據擴容後的容量新建數組，然後將hashMap的table的引用指向新數組。
- 將舊數組的元素複製到table中。在該過程中， 涉及到幾種情況， 需要分開進行處理（只存有一個元素， 一般鏈表， 紅黑樹）
具體的看代碼吧
7.4 注意事項
雖然 HashMap 設計的非常優秀， 但是應該儘可能少的避免 resize(), 該過程會很耗費時間。
同時， 由於 hashmap 不能自動的縮小容量 因此，如果你的 hashmap 容量很大，但執行了很多 remove操作時，容量並不會減少。如果你覺得需要減少容量，請重新創建一個 hashmap。
八、HashMap.put() 函數內部是如何工作的？
在使用多次 HashMap 之後， 大體也能說出其添加元素的原理：計算每一個key的哈希值， 通過一定的計算之後算出其在哈希表中的位置，將鍵值對放入該位置，如果有哈希碰撞則進行哈希碰撞處理。
而其工作時的原理如下
源碼如下：
在此過程中， 會涉及到哈希碰撞的解決。
九、HashMap.get() 方法內部是如何工作的？
其最終是調用了 getNode 函數。 其邏輯如下
源碼如下：
閱讀更多 Java面經 的文章
