一嚼酝、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) 的低二進制全部變?yōu)?，最后加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變?yōu)?背亥。
使用了 「擾動函數」 之后秒际， hash 碰撞的概率將會下降。 有人專門做過類似的測試狡汉， 雖然使用該 「擾動函數」 并沒有獲得最大概率的避免 hash 碰撞娄徊，但考慮其計算性能和碰撞的概率， JDK 中使用了該方法轴猎，且只hash一次嵌莉。
五、哈希碰撞及其處理
在理想的情況下捻脖， 哈希函數將每一個 key 都映射到一個唯一的 bucket锐峭， 然而， 這是不可能的可婶。哪怕是設計在良好的哈希函數沿癞，也會產生哈希沖突。
前人研究了很多哈希沖突的解決方法矛渴，在維基百科中椎扬，總結出了四大類
在 Java 的 HashMap 中， 采用了第一種 Separate chaining 方法(大多數翻譯為拉鏈法)+鏈表和紅黑樹來解決沖突具温。
在 HashMap 中蚕涤， 哈希碰撞之后會通過 Node 類內部的成員變量 Node<K,V> next; 來形成一個鏈表(節(jié)點小于8)或紅黑樹（節(jié)點大于8， 在小于6時會從新轉換為鏈表）铣猩， 從而達到解決沖突的目的揖铜。
static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
六、HashMap 的初始化
public HashMap();
public HashMap(int initialCapacity);
public HashMap(Map m);
public HashMap(int initialCapacity, float loadFactor);
HashMap 中有四個構造函數达皿， 大多是初始化容量和負載因子的操作天吓。以 public HashMap(int initialCapacity, float loadFactor) 為例
通過該函數進行了容量和負載因子的初始化，如果是調用的其他的構造函數峦椰， 則相應的負載因子和容量會使用默認值（默認負載因子=0.75龄寞， 默認容量=16）。在此時汤功， 還沒有進行存儲容器 table 的初始化物邑， 該初始化要延遲到第一次使用時進行。
七、HashMap 中哈希表的初始化或動態(tài)擴容
所謂的哈希表拂封， 指的就是下面這個類型為內部類Node的 table 變量茬射。
transient Node[] table;
作為數組， 其在初始化時就需要指定長度冒签。在實際使用過程中在抛， 我們存儲的數量可能會大于該長度，因此 HashMap 中定義了一個閾值參數(threshold)萧恕， 在存儲的容量達到指定的閾值時刚梭， 需要進行擴容。
我個人認為初始化也是動態(tài)擴容的一種票唆， 只不過其擴容是容量從 0 擴展到構造函數中的數值（默認16）朴读。 而且不需要進行元素的重hash.
7.1 擴容發(fā)生的條件
初始化的話只要數值為空或者數組長度為 0 就會進行。 而擴容是在元素的數量大于閾值（threshold）時就會觸發(fā)走趋。
threshold = loadFactor * capacity
比如 HashMap 中默認的 loadFactor=0.75, capacity=16, 則
threshold = loadFactor * capacity = 0.75 * 16 = 12
那么在元素數量大于 12 時衅金， 就會進行擴容。 擴容后的 capacity 和 threshold 也會隨之而改變簿煌。
負載因子影響觸發(fā)的閾值氮唯，因此，它的值較小的時候姨伟，HashMap 中的 hash 碰撞就很少惩琉， 此時存取的性能都很高，對應的缺點是需要較多的內存夺荒；而它的值較大時瞒渠，HashMap 中的 hash 碰撞就很多，此時存取的性能相對較低技扼，對應優(yōu)點是需要較少的內存伍玖；不建議更改該默認值，如果要更改剿吻，建議進行相應的測試之后確定私沮。
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 設計的非常優(yōu)秀删铃， 但是應該盡可能少的避免 resize(), 該過程會很耗費時間诫隅。
同時， 由于 hashmap 不能自動的縮小容量 因此兔毒，如果你的 hashmap 容量很大芍殖，但執(zhí)行了很多 remove操作時，容量并不會減少。如果你覺得需要減少容量，請重新創(chuàng)建一個 hashmap樱溉。
八挖帘、HashMap.put() 函數內部是如何工作的骄崩？
在使用多次 HashMap 之后站楚， 大體也能說出其添加元素的原理：計算每一個key的哈希值舅踪， 通過一定的計算之后算出其在哈希表中的位置货徙，將鍵值對放入該位置皮胡，如果有哈希碰撞則進行哈希碰撞處理痴颊。
而其工作時的原理如下
源碼如下：
在此過程中， 會涉及到哈希碰撞的解決玉转。
九妓蛮、HashMap.get() 方法內部是如何工作的蛤克？
其最終是調用了 getNode 函數捺癞。 其邏輯如下
源碼如下：
擴展閱讀
來源：https://www.cnblogs.com/homejim/p/10029796.html
