Base on Java8
簡介
HashMap是基于哈希表實現(xiàn)的映射（map）析苫。此實現(xiàn)提供了所有可選映射操作查描，并允許空值和空鍵损晤。(HashMap類大致相當(dāng)于Hashtable奋刽，只是它是不同步的，并且允許空值)升薯。該類不能保證映射的順序，特別是击困，它不能保證順序隨時間保持不變涎劈。
這個實現(xiàn)為基本操作(get和put)提供了恒定時間的性能（ constant-time performance），假設(shè)哈希函數(shù)將元素正確地分散在桶（bucket）中阅茶。對集合視圖迭代需要的時間與HashMap實例的“容量”(bucket的數(shù)量)加上它的大小(鍵-值映射的數(shù)量)成正比蛛枚。因此，如果迭代性能很重要脸哀，那么不要將初始容量設(shè)置得太高(或負(fù)載系數(shù)設(shè)置得太低)蹦浦，這一點非常重要。
HashMap的實例有兩個影響其性能的參數(shù):初始容量和負(fù)載因子撞蜂。初始容量是哈希表中的桶數(shù)白筹，就是創(chuàng)建哈希表時的容量。負(fù)載因子是一種度量方法谅摄，用來衡量在自動增加哈希表的容量之前徒河，哈希表允許達(dá)到的滿度。當(dāng)哈希表中的條目數(shù)超過負(fù)載因子和當(dāng)前容量的乘積時送漠，哈希表將被重新哈希(rehash顽照，即重新構(gòu)建內(nèi)部數(shù)據(jù)結(jié)構(gòu))，這樣哈希表的桶數(shù)大約是原來的兩倍闽寡。
作為一般規(guī)則代兵，默認(rèn)的負(fù)載因子(.75)在時間和空間成本之間提供了一個很好的折衷。較高的值會減少空間開銷爷狈，但會增加查找成本(反映在HashMap類的大多數(shù)操作中植影，包括get和put)。在設(shè)置初始容量時涎永，應(yīng)該考慮映射中的預(yù)期條目數(shù)及其負(fù)載因子思币，以便最小化重散列操作的數(shù)量鹿响。如果初始容量大于最大條目數(shù)除以負(fù)載因子，則不會發(fā)生重新散列操作（rehash）（If the initial capacity is greater than the maximum number of entries divided by the load factor, no rehash operations will ever occur.）谷饿。
如果要在一個HashMap實例中存儲許多映射惶我，那么以足夠大的容量創(chuàng)建它將比根據(jù)需要讓映射自動執(zhí)行重散列以增長表更高效。注意博投，對同一個hashCode()使用多個鍵肯定會降低散列表的性能绸贡。為了改善性能，當(dāng)鍵是可比較（即鍵實現(xiàn)Comparable接口）的時毅哗，這個類可以使用鍵之間的比較順序來幫助斷開連接）（this class may use comparison order among keys to help break tie）听怕。
即hash沖突時，將沖突的key-value作為鏈表鏈接在數(shù)組上虑绵；同時Comparable接口可以有助于實現(xiàn)HashMap內(nèi)部的紅黑樹尿瞭。
注意，這個實現(xiàn)不能保證同步蒸殿。如果多個線程并發(fā)地訪問一個散列映射筷厘，并且至少有一個線程修改了映射的結(jié)構(gòu)，那么它必須在外部進(jìn)行同步(結(jié)構(gòu)修改是添加或刪除一個或多個映射的任何操作;僅僅改變實例已經(jīng)包含的鍵相關(guān)聯(lián)的值不是結(jié)構(gòu)修改)宏所。這通常是通過在封裝映射的某個對象上進(jìn)行同步來實現(xiàn)的（This is typically accomplished by synchronizing on some object that naturally encapsulates the map）酥艳。如果不存在這樣的對象，則應(yīng)該使用集合“包裝”映射（ Collections.synchronizedMap）爬骤。這最好在創(chuàng)建時完成充石，以防止意外的非同步訪問映射:
Map m = Collections.synchronizedMap(new HashMap(...));
這個類的所有“集合視圖方法”返回的迭代器都是快速失敗（fail-fast）的:如果在迭代器創(chuàng)建后的任何時候?qū)τ成溥M(jìn)行了結(jié)構(gòu)上的修改——除了通過迭代器自己的remove方法之外的任何方式霞玄，迭代器都將拋出一個ConcurrentModificationException異常骤铃。因此，在面對并發(fā)修改時坷剧，迭代器會快速且干凈地失敗惰爬，而不是在未來某個不確定的時間冒險做出任意的、不確定的行為惫企。
注意撕瞧，迭代器的快速失敗行為不能得到保證，因為一般來說狞尔，在存在非同步并發(fā)修改時不可能做出任何硬性保證丛版。快速失敗迭代器盡最大努力拋出ConcurrentModificationException偏序。因此页畦，如果要編寫一個依賴于這個異常來保證其正確性的程序，那將是錯誤的:迭代器的快速失敗行為應(yīng)該僅用于檢測錯誤研儒。
該類是Java Collections框架的成員豫缨。
分析
HashMap本質(zhì)上是一個散列表独令，那么就離不開散列表的三大問題：散列函數(shù)、哈希沖突州胳、擴容方案记焊；同時作為一個數(shù)據(jù)結(jié)構(gòu)逸月，必須考慮多線程并發(fā)訪問的問題栓撞，也就是線程安全。這四大重點則為學(xué)習(xí)HashMap的重點碗硬，也是HashMap設(shè)計的重點瓤湘。
先看HashMap的使用場景：
Map<String, String> map = new HashMap<>();
map.put("key", "value");
put方法將鍵值對存入HashMap。
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
在HashMap種恩尾，put方法則繼續(xù)調(diào)用putVal方法弛说，傳入的第一個參數(shù)就是存放的key的哈希值。也就是通過散列函數(shù)計算出的哈希值翰意。
哈希函數(shù)
哈希函數(shù)的目的就是確定所要存放的元素在數(shù)組中的下標(biāo)木人。
查看hash方法的源碼：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
這段代碼叫“擾動函數(shù)”。
大家都知道上面代碼里的key.hashCode()函數(shù)調(diào)用的是key鍵值類型自帶的哈希函數(shù)冀偶，返回int型散列值醒第。
理論上散列值是一個int型，如果直接拿散列值作為下標(biāo)訪問HashMap主數(shù)組的話进鸠，考慮到2進(jìn)制32位帶符號的int表值范圍從-2147483648到2147483648稠曼。前后加起來大概40億的映射空間。只要哈希函數(shù)映射得比較均勻松散客年，一般應(yīng)用是很難出現(xiàn)碰撞的3霞幅。
當(dāng)然，要在內(nèi)存中存放40億長的數(shù)組不太現(xiàn)實量瓜，所以需要通過取模運算得到數(shù)組下標(biāo)司恳。取模運算通過indexFor方法完成（JDK8沒有indexFor方法，而是直接通過table[index = (n – 1) & hash]實現(xiàn)）4绍傲。
這里也同樣可以看出為什么HashMap的數(shù)組長度要取為2的整數(shù)冪扔傅，因為這樣（數(shù)組長度-1）正好相當(dāng)于一個“低位掩碼”∵笕。“與”操作的結(jié)果就是散列值的高位全部歸零铅鲤，只保留低位值，用來做數(shù)組下標(biāo)訪問枫弟。
10100101 11000100 00100101
& 00000000 00000000 00001111
----------------------------------
00000000 00000000 00000101 //高位全部歸零邢享，只保留末四位
從HashMap的構(gòu)造函數(shù)可以看出HashMap的初始化容量可以被指定：
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
為了保證HashMap數(shù)組長度為2的整數(shù)冪，HashMap提供了tableSizeFor方法淡诗，該方法使最高位的1后面的位全變?yōu)?骇塘。
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;
}
調(diào)用者確保傳入的cap為正整數(shù)伊履。
比如：傳入的cap為12
0000,1001 #n=11
>>>1 0000,0100
| 0000,1001
------------------
0000,1101 #n=13
>>>2 0000,0011
| 0000,1101
------------------
0000,1111 #n=15
>>>4 0000,0000
| 0000,1111
------------------
0000,1111 #n=15
...
不難看出，最后執(zhí)行下去n的結(jié)果還是15款违，也就是2n-1唐瀑，所以最后返回時會進(jìn)行加1操作。
如果對傳入的cap沒有做減1操作插爹，且cap剛好為2的整數(shù)次冪哄辣，則返回值會變?yōu)閏ap的2倍。
哈希沖突解決
一旦哈希表的長度小于準(zhǔn)備插入表的數(shù)據(jù)赠尾，那么hash沖突必然會出現(xiàn)力穗。hash沖突指的是兩個不同的key經(jīng)過hash計算之后得到的數(shù)組下標(biāo)是相同的。解決hash沖突的方式很多气嫁，如開放定址法（前提是散列表的長度大于等于所要存放的元素）当窗、再哈希法、公共溢出表法（把哈希表分為公共表和溢出表寸宵，如果發(fā)生了溢出崖面，溢出的數(shù)據(jù)全部放在溢出區(qū)5）、鏈地址法梯影。HashMap采用的是鏈地址法巫员。
舊版本（JDK1.8之前）的HashMap存在一個問題，即使負(fù)載因子和Hash算法設(shè)計的再合理光酣，也免不了會出現(xiàn)拉鏈過長的情況疏遏，一旦出現(xiàn)拉鏈過長，則會嚴(yán)重影響HashMap的性能救军。于是财异，在JDK1.8版本中，對數(shù)據(jù)結(jié)構(gòu)做了進(jìn)一步的優(yōu)化唱遭，引入了紅黑樹戳寸。而當(dāng)鏈表長度太長（TREEIFY_THRESHOLD默認(rèn)超過8）時，鏈表就轉(zhuǎn)換為紅黑樹拷泽，利用紅黑樹快速增刪改查的特點提高HashMap的性能（O(logn)）疫鹊。當(dāng)長度小于（UNTREEIFY_THRESHOLD默認(rèn)為6），就會退化成鏈表4司致。
擴容
進(jìn)行putVal方法插入數(shù)據(jù)時會比較當(dāng)前容器包含元素數(shù)與最大容量和負(fù)載因子乘積的大胁疬骸：
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
...
if (++size > threshold)
resize();
...
}
threshold：The next size value at which to resize (capacity * load factor).
得益于HashMap保證哈希表的容量為2的整數(shù)次冪，數(shù)據(jù)的遷移也較為方便脂矫。
key在新的數(shù)組的hash結(jié)果只有兩種：在原來的位置枣耀，或者在原來位置+原數(shù)組長度。
比如：
hashcode 0010 1101
length-1 & 0000 0111
----------------------
0000 0101
擴容后
hashcode 0010 1101
length-1 & 0000 1111
----------------------
0000 1101
在新數(shù)組中的hash結(jié)果庭再，僅僅取決于高一位的數(shù)值捞奕。如果高一位是0牺堰，那么計算結(jié)果就是在原位置，而如果是1颅围，則加上原數(shù)組的長度即可伟葫。
源碼
put
Params:
hash – hash for key
key – the key
value – the value to put
onlyIfAbsent – if true, don't change existing value
evict – if false, the table is in creation mode.
Returns:
previous value, or null if none
public V put(K key, V value) {
// 獲取hash值，再調(diào)用putVal方法插入數(shù)據(jù)
return putVal(hash(key), key, value, false, true);
}
// onlyIfAbsent表示是否覆蓋舊值院促，true表示不覆蓋筏养，false表示覆蓋，默認(rèn)為false
// evict和LinkHashMap的回調(diào)方法有關(guān)一疯，不在本文討論范圍
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
// tab是HashMap內(nèi)部數(shù)組撼玄，n是數(shù)組的長度夺姑，i是要插入的下標(biāo)墩邀，p是該下標(biāo)對應(yīng)的節(jié)點
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 判斷數(shù)組是否是null或者是否是空，若是盏浙，則調(diào)用resize()方法進(jìn)行擴容
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 使用位與運算代替取模得到下標(biāo)
// 判斷當(dāng)前下標(biāo)是否是null眉睹，若是則創(chuàng)建節(jié)點直接插入，若不是废膘，進(jìn)入下面else邏輯
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
// e表示和當(dāng)前key相同的節(jié)點竹海，若不存在該節(jié)點則為null
// k是當(dāng)前數(shù)組下標(biāo)節(jié)點的key
Node<K,V> e; K k;
// 判斷當(dāng)前節(jié)點與要插入的key是否相同，是則表示找到了已經(jīng)存在的key
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 判斷該節(jié)點是否是樹節(jié)點丐黄，如果是調(diào)用紅黑樹的方法進(jìn)行插入
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 最后一種情況是直接鏈表插入
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 長度大于等于8時轉(zhuǎn)化為紅黑樹
// 注意斋配，treeifyBin方法中會進(jìn)行數(shù)組長度判斷，
// 若小于64灌闺，則優(yōu)先進(jìn)行數(shù)組擴容而不是轉(zhuǎn)化為樹
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
break;
}
// 找到相同的直接跳出循環(huán)
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 如果找到相同的key節(jié)點艰争，則判斷onlyIfAbsent和舊值是否為null
// 執(zhí)行更新或者不操作，最后返回舊值
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
// 如果不是更新舊值桂对，說明HashMap中鍵值對數(shù)量發(fā)生變化
// modCount數(shù)值+1表示結(jié)構(gòu)改變
++modCount;
// 判斷長度是否達(dá)到最大限度甩卓，如果是則進(jìn)行擴容
if (++size > threshold)
resize();
// 最后返回null（afterNodeInsertion是LinkHashMap的回調(diào)）
afterNodeInsertion(evict);
return null;
}
代碼注釋來自參考6
resize
final Node<K,V>[] resize() {
// 變量分別是原數(shù)組、原數(shù)組大小蕉斜、原閾值逾柿；新數(shù)組大小、新閾值
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
// 如果原數(shù)組長度大于0
if (oldCap > 0) {
// 如果已經(jīng)超過了設(shè)置的最大長度(1<<30,也就是最大整型正數(shù))
if (oldCap >= MAXIMUM_CAPACITY) {
// 直接把閾值設(shè)置為最大正數(shù)
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
// 設(shè)置為原來的兩倍
newThr = oldThr << 1;
}
// 原數(shù)組長度為0宅此，但最大限度不是0机错，把長度設(shè)置為閾值
// 對應(yīng)的情況就是新建HashMap的時候指定了數(shù)組長度
else if (oldThr > 0)
newCap = oldThr;
// 第一次初始化，默認(rèn)16和0.75
// 對應(yīng)使用默認(rèn)構(gòu)造器新建HashMap對象
else {
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 如果原數(shù)組長度小于16或者翻倍之后超過了最大限制長度父腕，則重新計算閾值
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"})
// 建立新的數(shù)組
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
// 循環(huán)遍歷原數(shù)組弱匪，并給每個節(jié)點計算新的位置
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
// 如果他沒有后繼節(jié)點，那么直接使用新的數(shù)組長度取模得到新下標(biāo)
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
// 如果是紅黑樹侣诵，調(diào)用紅黑樹的拆解方法
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
// 新的位置只有兩種可能：原位置痢法，原位置+老數(shù)組長度
// 把原鏈表拆成兩個鏈表狱窘，然后再分別插入到新數(shù)組的兩個位置上
// 不用多次調(diào)用put方法
else {
// 分別是原位置不變的鏈表和原位置+原數(shù)組長度位置的鏈表
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
// 遍歷老鏈表，判斷新增判定位是1or0進(jìn)行分類
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);
// 最后賦值給新的數(shù)組
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
// 返回新數(shù)組
return newTab;
}
代碼注釋來自參考6
