首先
平時開發(fā)的時候，HashMap的使用一定是非常多的骡尽，它實現(xiàn)了對鍵值對的操作遣妥，讓我們可以很方便的存儲和檢索鍵值對。對于它的名稱攀细，是這樣去理解的：
Map箫踩，中文有映射意思，從key--->value是一種映射谭贪。
另外境钟，其內(nèi)部實現(xiàn)用到了取hash的方法
相信大家都能把 HashMap用得很溜，所以這里就不去對它的使用方法進行敘述了俭识。這里主要講一下其內(nèi)部實現(xiàn)慨削，另外找?guī)滋巶€人覺得設計得十分巧妙的代碼來分析一下。
內(nèi)部實現(xiàn)
首先我們來認識一下Node ，它繼承自Map.Entry：
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
}
一個 Node 對象即是一個 kv對（key value 鍵值對）理盆。
HashMap內(nèi)部定義了一個Node<K,V>[] table痘煤，這個數(shù)組用于存儲kv對。table形如：
那么這些kv對 是怎么找到自己在table中的位置的呢猿规？
首先是求得鍵的 hashcode衷快，然后通過 index = (n-1) & hashcode 計算獲取到這個 kv對 在數(shù)組中的下標（n是數(shù)組table的size）。這時候姨俩，問題來了≌喊危現(xiàn)實情況存在不同的 key 的 hashcode 相同，那么數(shù)組 table 中的每個元素需要存儲多個 kv對环葵。正是這樣调窍，table 中的每個元素也稱作為 bucket（桶），一個 bucket 中存儲了多個 kv對张遭。
一個 bucket 也就是一個 Node 對象邓萨，bucket 其實是一個鏈表，我們看到了 Node 對象中有這樣一個字段：
Node<K,V> next;
正是 next 字段實現(xiàn)了鏈表的效果菊卷，可以讓一個 Node 指向另一個 Node缔恳。所以每個 bucket 是長這樣的：
這里補充一下，其實 bucket 的形態(tài)是有兩種洁闰，鏈表和紅黑樹歉甚，這里先不對紅黑樹的形態(tài)進行討論。
了解了HashMap的內(nèi)部結構之后扑眉，下面我們看看通過key查詢value的步驟：
- 通過key計算得到index纸泄，由而得到bucket的位置。
- 遍歷bucket中的每個Node腰素，若找到一個Node聘裁，并且該Node的鍵與key相等，則該Node的value就是我們需要查找的value耸弄；否則咧虎，則返回null。
一般而言计呈，每個桶中的kv對的數(shù)量不會很大砰诵，從而在查找的過程中避免了大量的循環(huán)操作，這也是HashMap高效的原因所在捌显∽屡恚可是，假若發(fā)生了一個bucket中有大量的kv對扶歪，那么在查詢時應該怎么去避免較多的循環(huán)呢理肺？
此時摄闸，HashMap就會把這個bucket從鏈表轉化為紅黑樹，從而提高查詢效率妹萨。
在源碼中年枕，是這樣判斷的：
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
TREEIFY_THRESHOLD是預先設定的閾值，若當前的bucket中kv對的數(shù)量達到閾值之后乎完，就會調(diào)用treeifyBin方法將鏈表變成紅黑樹熏兄。
從整體上來講，HashMap的內(nèi)部結構就是這些了树姨。下面的內(nèi)容是對源碼中一些巧妙的代碼細節(jié)進行分析摩桶。
巧妙的細節(jié)
table的size總是為2^n，并且HashMap的最大容量是 1<<30
table是HashMap中的數(shù)組帽揪。隨著Map中的kv對越來越多的時候硝清，table的size是需要不斷變大的，但是table的size總是為2^n转晰。
在上面芦拿，我們講過，下標的計算方式是index = (n-1) & hashcode挽霉，n即table的長度防嗡，table的長度總是2的整數(shù)倍变汪。那么就可以保證 n-1 的二進制位全部為1侠坎，進一步可以保證公式index = (n-1) & hashcode計算出的下標均勻分布。
其實裙盾，table的size總是為2^n就是HashMap的最大容量為1<<30的原因实胸。
1<<31 = -2147483648，是一個負數(shù)番官，顯然不能作為table的長度庐完。
Map初始化容量大小
我們可以通過這個構造方法初始化HashMap并指定Map的容量：
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
可是Map的容量大小必須是2的整數(shù)倍，所以啊徘熔，初始容量大小并不能直接設置為initialCapacity门躯，而應該設置為2^n，并且滿足：
- 2^n大于等于initialCapacity酷师。
- 2^n盡量小讶凉。
源代碼中是通過如下方法找到這個真正的初始容量的：
/**
* Returns a power of two size for the given target capacity.
*/
static final int tableSizeFor(int cap) {
int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
Integer.numberOfLeadingZeros這個方法計算bit位前面0的個數(shù)，如整數(shù)2的bit位為：00000000 00000000 00000000 00000010,它從左到右有連續(xù)的30個0山孔，那么Integer.numberOfLeadingZeros(2)=30懂讯。
可以結合下圖對tableSizeFor方法進行理解，首先cap前面有x個0台颠，那么cap-1前面就有x個或者x+1個0褐望；對-1進行右移操作之后，就得到圖中a，b兩種情況瘫里。
我們可以看到tableSizeFor方法实蔽，在對-1進行>>>之后還+1處理了，因為a谨读，b滿足前面都是0盐须，后面都是1，在對其+1處理之后就會變成2的倍數(shù)漆腌。所以cd一定為2^n贼邓。下面對c，d分別進行說明：
- cap前面有x個0闷尿，而c前面有x-1個0塑径，那么c一定滿足大于cap。
- d前面0的個數(shù)和cap一樣填具，都是x個统舀。我再回顧一下b這種情形：當cap-1之后前面0的個數(shù)增加了1，發(fā)生這種情況就說明cap本身就是2的倍數(shù)劳景。cap和d前面0的個數(shù)一樣誉简，進一步說明d一定等于cap。
最后c盟广，d就是我們在找的那個大于等于initialCapacity最小的2^n了闷串。
table的size進行double時，需要重新計算table數(shù)組里面元素的下標
HashMap對table的size進行調(diào)整的方式是進行Double筋量，由于kv對的下標計算方式與size有關烹吵，所以size調(diào)整之后下標也需要跟著一起做調(diào)整。
當桶中只有一個節(jié)點時桨武，做法很簡單肋拔，根據(jù)公式index = (n-1) & hashcode計算即可得到新的下標。
當桶中有多個元素時呀酸，也可以用同樣的方法遍歷計算它們的下標凉蜂。但是，源代碼中并沒有這樣去處理性誉，而且找到了另一種較高效的方法：
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)
hiHead = e;
else
hiTail.next = e;
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;
}
下圖中的cap即數(shù)組table的size窿吩，對cap double之后，發(fā)現(xiàn)它們兩者唯一的區(qū)別就是：
cap -1 第 x-1 位是0艾栋，2xcap-1 第 x-1 位是1
double cap
此時我們結合下標計算公式能夠想到下面兩種情況：
- 若hash的第 x-1 位是0爆存，那么hash & (2xcap-1)計算出的下標和hash & (cap-1)計算出的下標一樣。
- 若hash的第 x-1 位是1蝗砾，那么新下標的第 x-1 位也是1先较，進一步我們可以得到新下標=老下標+cap携冤。
通過上面的分析來理解這段代碼就比較簡單了，是通過(e.hash & oldCap) == 0來判斷hash的第 x-1 位是0還是1闲勺，如果是0即加到loHead鏈表中曾棕，否則就加到hiHead鏈表中。
最后loHead的下標是老下標j菜循，然后hiHead的新下標即j+oldCap翘地。
最后
HashMap的作者對二進制操作的賊流暢，膜拜膜拜膜拜～
