一.什么是hash表
不同數(shù)據(jù)結(jié)構(gòu)的操作性能：
1.數(shù)組
下標(biāo)查找：O(1)
值查找:遍歷O(n),二分查找O(logn),插入刪除平均O(n)
2.線性鏈表
查找、更新:O(n)
新增弓熏、刪除:O(1)
3.二叉樹
平均O(logn)
4.哈希表
哈希表中進(jìn)行添加刃永，刪除，查找等操作,不考慮hash沖突O(1);
二.HashMap的基本結(jié)構(gòu)
在 Java 的 HashMap 中与学， 采用了第一種 Separate chaining 方法(大多數(shù)翻譯為拉鏈法)+鏈表和紅黑樹來解決沖突。
哈希沖突
當(dāng)我們通過Hash函數(shù)得出的實際存儲地址相同怎么辦？
在 HashMap 中汇恤， 哈希碰撞之后會通過 Node 類內(nèi)部的成員變量 Node<K,V> next; 來形成一個鏈表(節(jié)點小于8)或紅黑樹（節(jié)點大于8， 在小于6時會從新轉(zhuǎn)換為鏈表）拔恰， 從而達(dá)到解決沖突的目的因谎。
static final int UNTREEIFY_THRESHOLD = 6;
什么是Hash？
最簡單形式的 hash仁连，是一種在對任何變量/對象的屬性應(yīng)用任何公式/算法后蓝角， 為其分配唯一代碼的方法。
哈希函數(shù)每次在相同或相等的對象上應(yīng)用哈希函數(shù)時, 應(yīng)每次返回相同的哈希碼饭冬。換句話說, 兩個相等的對象必須一致地生成相同的哈希碼使鹅。
Java 中所有的對象都有 Hash 方法。
Java中的所有對象都繼承 Object 類中定義的 hashCode() 函數(shù)的默認(rèn)實現(xiàn)昌抠。 此函數(shù)通常通過將對象的內(nèi)部地址轉(zhuǎn)換為整數(shù)來生成哈希碼患朱，從而為所有不同的對象生成不同的哈希碼。
3.HashMap的代碼實現(xiàn)：
HashMap的Node結(jié)構(gòu):
Node是HashMap用來存儲鍵值對的數(shù)據(jù)結(jié)構(gòu)炊苫，其基本結(jié)構(gòu)如下：
static class Node<K,V> implements Map.Entry<K,V> {
// key的hash值
final int hash;
// key值
final K key;
// value值
V value;
// 鏈表下一個節(jié)點
Node<K,V> next;
HashMap如何存儲包含鍵值對的Node?
鍵值對在 HashMap 中是以 Node 內(nèi)部類的數(shù)組存放的裁厅，如下所示：
transient Node<K,V>[] table;
通過計算出來的Hash碼，轉(zhuǎn)換成該數(shù)組的下標(biāo)侨艾，在該下標(biāo)的位置存儲對應(yīng)的Node.
該數(shù)組對應(yīng)的長度始終是2的次冪执虹，如下函數(shù):
/**
* Returns a power of two size for the given target capacity.
*/
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
其原理是將傳入?yún)?shù) (cap) 的低二進(jìn)制全部變?yōu)?，最后加1即可獲得對應(yīng)的大于 cap 的 2 的次冪作為數(shù)組長度唠梨。
為什么要使用2的次冪作為數(shù)組的容量呢袋励？
在此有涉及到 HashMap 的 hash 函數(shù)及數(shù)組下標(biāo)的計算， 鍵(key)所計算出來的哈希碼有可能是大于數(shù)組的容量的，那怎么辦茬故？ 可以通過簡單的求余運算來獲得盖灸，但此方法效率太低。HashMap中通過以下的方法保證 hash 的值計算后都小于數(shù)組的容量磺芭。
(n - 1) & hash
這也正好解釋了為什么需要2的次冪作為數(shù)組的容量赁炎。由于n是2的次冪，因此钾腺，n-1類似于一個低位掩碼徙垫。通過與操作，高位的hash值全部歸零垮庐，保證低位才有效 從而保證獲得的值都小于n松邪。
以默認(rèn)的初始值16為例。
01010011 00100101 01010100 00100101
& 00000000 00000000 00000000 00001111
----------------------------------
00000000 00000000 00000000 00000101 //高位全部歸零哨查，只保留末四位
// 保證了計算出的值小于數(shù)組的長度 n
但是逗抑，使用了該功能之后，由于只取了低位寒亥，因此 hash 碰撞會也會相應(yīng)的變得很嚴(yán)重邮府。這時候就需要使用「擾動函數(shù)」。（原來擾動函數(shù)是hash()方法...）
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
該函數(shù)通過將哈希碼的高16位的右移后與原哈希碼進(jìn)行異或而得到溉奕，以上面的例子為例褂傀。
此方法保證了高16位不變， 低16位根據(jù)異或后的結(jié)果改變加勤。計算后的數(shù)組下標(biāo)將會從原先的5變?yōu)?仙辟。
使用了 「擾動函數(shù)」 之后， hash 碰撞的概率將會下降鳄梅。 有人專門做過類似的測試叠国， 雖然使用該 「擾動函數(shù)」 并沒有獲得最大概率的避免 hash 碰撞，但考慮其計算性能和碰撞的概率戴尸， JDK 中使用了該方法粟焊，且只hash一次。
HashMap如何進(jìn)行初始化孙蒙？
以下是初始化的代碼：
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
參數(shù)：initialCapacity(初始化容量)项棠、loadFactor(負(fù)載因子)
通過該函數(shù)進(jìn)行了容量和負(fù)載因子的初始化，如果是調(diào)用的其他的構(gòu)造函數(shù)挎峦， 則相應(yīng)的負(fù)載因子和容量會使用默認(rèn)值（默認(rèn)負(fù)載因子=0.75香追， 默認(rèn)容量=16）。在此時坦胶， 還沒有進(jìn)行存儲容器 table 的初始化翅阵， 該初始化要延遲到第一次使用時進(jìn)行歪玲。
HashMap如何進(jìn)行擴容？
transient Node<K,V>[] table;
所謂擴容掷匠，就是在table數(shù)組的容量達(dá)到閥值的時候，需要進(jìn)行擴容.
int threshold;
擴容發(fā)生的條件岖圈？
初始化的話只要數(shù)值為空或者數(shù)組長度為 0 就會進(jìn)行讹语。 而擴容是在元素的數(shù)量大于閾值（threshold）時就會觸發(fā)。
threshold = loadFactor * capacity
比如 HashMap 中默認(rèn)的 loadFactor=0.75, capacity=16, 則蜂科。
threshold = loadFactor * capacity = 0.75 * 16 = 12
那么在元素數(shù)量大于 12 時顽决， 就會進(jìn)行擴容。 擴容后的 capacity 和 threshold 也會隨之而改變导匣。
負(fù)載因子:影響擴容觸發(fā)的閥值才菠，值較小的時候，哈希碰撞就很少贡定，存取性能比較高赋访，但是會占用較多內(nèi)存。值較大時缓待，哈希碰撞很多蚓耽，性能比較低，需要較少內(nèi)存旋炒。不建議修改步悠。
擴容的過程：
JDK1.7
void resize(int newCapacity) { //傳入新的容量
Entry[] oldTable = table; //引用擴容前的Entry數(shù)組
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) { //擴容前的數(shù)組大小如果已經(jīng)達(dá)到最大(2^30)了
threshold = Integer.MAX_VALUE; //修改閾值為int的最大值(2^31-1)，這樣以后就不會擴容了
return;
}
Entry[] newTable = new Entry[newCapacity]; //初始化一個新的Entry數(shù)組
transfer(newTable); //Ｌ闭颉鼎兽！將數(shù)據(jù)轉(zhuǎn)移到新的Entry數(shù)組里
table = newTable; //HashMap的table屬性引用新的Entry數(shù)組
threshold = (int)(newCapacity * loadFactor);//修改閾值
}
使用一個容量更大的數(shù)組來代替已有的容量小的數(shù)組；transfer()方法將原有Entry數(shù)組的元素拷貝到新的Entry數(shù)組里铣除；
transfer()函數(shù)的代碼
void transfer(Entry[] newTable) {
Entry[] src = table; //src引用了舊的Entry數(shù)組
int newCapacity = newTable.length;
for (int j = 0; j < src.length; j++) { //遍歷舊的Entry數(shù)組
Entry<K,V> e = src[j]; //取得舊Entry數(shù)組的每個元素
if (e != null) {
src[j] = null;//釋放舊Entry數(shù)組的對象引用（for循環(huán)后谚咬，舊的Entry數(shù)組不再引用任何對象）
do {
Entry<K,V> next = e.next;
int i = indexFor(e.hash, newCapacity); //！通孽！重新計算每個元素在數(shù)組中的位置
e.next = newTable[i]; //標(biāo)記[1]
newTable[i] = e; //將元素放在數(shù)組上
e = next; //訪問下一個Entry鏈上的元素
} while (e != null);
}
}
}
注釋標(biāo)記[1]處序宦，將newTable[i]的引用賦給了e.next，也就是使用了單鏈表的頭插入方式背苦，同一位置上新元素總會被放在鏈表的頭部位置互捌；這樣先放在一個索引上的元素終會被放到Entry鏈的尾部(如果發(fā)生了hash沖突的話)；
indexFor()是計算每個元素在數(shù)組中的位置行剂，源碼：
static int indexFor(int h, int length) {
return h & (length-1); //位AND計算
}
這樣秕噪，在舊數(shù)組中同一條Entry鏈上的元素，通過重新計算索引位置后厚宰，有可能被放到了新數(shù)組的不同位置上腌巾；
例如遂填，舊數(shù)組容量為16，對象A的hash值是4澈蝙，對象B的hash值是20,對象C的hash值是36吓坚；
通過indexFor()計算后，A灯荧、B礁击、C對應(yīng)的數(shù)組索引位置分別為4,4,4; 說明這3個對象在數(shù)組的同一位置上，形成了Entry鏈逗载；
舊數(shù)組擴容后容量為16*2哆窿，重新計算對象所在的位置索引，A厉斟、B挚躯、C對應(yīng)的數(shù)組索引位置分別為4,20,4; B對象已經(jīng)被放到別處了；
JDK1.8
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
//step1:
hiHead = e;
else
//step2:
hiTail.next = e;
//step3:
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;
}
大概步驟為：
1.將容量修改為擴容后的容量
2.將閥值賦值為擴容后的閥值
3.創(chuàng)建新的Node數(shù)組擦秽，將老數(shù)組的引用更新為新數(shù)組
4.將老數(shù)組中的Node節(jié)點重新hash到新的數(shù)組中码荔。（注意對于只有單個節(jié)點、鏈表号涯、紅黑樹的情況處理不同）
這里解釋一下對于鏈表的情況：
前面說過了數(shù)組的容量為 2 的整次冪目胡， 同時， 數(shù)組的下標(biāo)通過下面的代碼進(jìn)行計算链快。
index = (table.length - 1) & hash
該方法除了可以很快的計算出數(shù)組的索引之外誉己， 在擴容之后， 進(jìn)行重 hash 時也會很巧妙的就可以算出新的 hash 值域蜗。 由于數(shù)組擴容之后巨双， 容量是現(xiàn)在的 2 倍， 擴容之后 n-1 的有效位會比原來多一位霉祸， 而多的這一位與原容量二進(jìn)制在同一個位置筑累。 示例。
if ((e.hash & oldCap) == 0)
該語句用語判斷是否需要進(jìn)行移動丝蹭，從而提高效率慢宗。
==* 如何通過保證head 和 tail 來保證鏈表的順序和之前一樣，（避免產(chǎn)生循環(huán)引用奔穿？）==
else {
if (hiTail == null)
//step1:
hiHead = e;
else
//step2:
hiTail.next = e;
//step3:
hiTail = e;
}
這里以高位舉例解析其中部分代碼镜沽，這里不區(qū)分不移動的節(jié)點：
上圖說明頭節(jié)點確認(rèn)后是不再變的，只在尾節(jié)點后追加贱田。
注意：
雖然 HashMap 設(shè)計的非常優(yōu)秀缅茉， 但是應(yīng)該盡可能少的避免 resize(), 該過程會很耗費時間。
同時男摧， 由于 hashmap 不能自動的縮小容量 因此蔬墩，如果你的 hashmap 容量很大译打，但執(zhí)行了很多 remove操作時，容量并不會減少拇颅。如果你覺得需要減少容量奏司，請重新創(chuàng)建一個 hashmap。
HashMap的get()過程
HashMap的put()過程
參考：
https://my.oschina.net/placeholder/blog/180069
https://mp.weixin.qq.com/s/GfB6yerj3fVm_WqSbVCRqA
