概述
鍵值對操作在大的業(yè)務(wù)場景中經(jīng)常用到等舔，HashMap是Java程序員使用頻率最高的用于映射(鍵值對)處理的數(shù)據(jù)類型牺荠。隨著JDK（Java Developmet Kit）版本的更新丈挟，JDK1.8對HashMap底層的實現(xiàn)進(jìn)行了優(yōu)化，例如引入紅黑樹的數(shù)據(jù)結(jié)構(gòu)和擴容的優(yōu)化等
簡介
Java為數(shù)據(jù)結(jié)構(gòu)中的映射定義了一個接口java.util.Map志电，此接口主要有四個常用的實現(xiàn)類曙咽，分別是HashMap、Hashtable挑辆、LinkedHashMap和TreeMap例朱，類繼承關(guān)系如下圖所示
1. HashMap：它根據(jù)鍵的hashCode值存儲數(shù)據(jù)，大多數(shù)情況下可以直接定位到它的值鱼蝉，因而具有很快的訪問速度洒嗤，但遍歷順序卻是不確定的。 HashMap最多只允許一條記錄的鍵為null魁亦，允許多條記錄的值為null渔隶。HashMap非線程安全，即任一時刻可以有多個線程同時寫HashMap，可能會導(dǎo)致數(shù)據(jù)的不一致间唉。如果需要滿足線程安全绞灼，可以用 Collections的synchronizedMap方法使HashMap具有線程安全的能力，或者使用ConcurrentHashMap呈野。
2. HashTable：Hashtable是遺留類(基本上不再使用)低矮，很多映射的常用功能與HashMap類似，不同的是它承自Dictionary類被冒，并且是線程安全的军掂，任一時間只有一個線程能寫Hashtable，并發(fā)性不如ConcurrentHashMap昨悼，因為ConcurrentHashMap引入了分段鎖蝗锥。Hashtable不建議在新代碼中使用，不需要線程安全的場合可以用HashMap替換率触，需要線程安全的場合可以用ConcurrentHashMap替換终议。
3. LinkedHashMap：LinkedHashMap是HashMap的一個子類，保存了記錄的插入順序闲延，在用Iterator遍歷LinkedHashMap時，先得到的記錄肯定是先插入的韩玩，也可以在構(gòu)造時帶參數(shù)垒玲，按照訪問次序排序。
4. TreeMap：TreeMap實現(xiàn)SortedMap接口找颓，能夠把它保存的記錄根據(jù)鍵排序合愈，默認(rèn)是按鍵值的升序排序，也可以指定排序的比較器击狮，當(dāng)用Iterator遍歷TreeMap時佛析，得到的記錄是排過序的。如果使用排序的映射彪蓬，建議使用TreeMap寸莫。在使用TreeMap時，key必須實現(xiàn)Comparable接口或者在構(gòu)造TreeMap傳入自定義的Comparator档冬，否則會在運行時拋出java.lang.ClassCastException類型的異常膘茎。
HashMap實現(xiàn)原理
存儲結(jié)構(gòu)-字段
從結(jié)構(gòu)實現(xiàn)來講，HashMap是數(shù)組+鏈表+紅黑樹(jdk1.8新增)的
- 從源碼可知酷誓，HashMap中有一個非常重要的字段披坏，就是Node[] table
static class Node<K,V> implements Map.Entry<K,V> {
final int hash; //用來定位數(shù)組索引位置
final K key;
V value;
Node<K,V> next; //鏈表的下一個node
Node(int hash, K key, V value, Node<K,V> next) { ... }
...
}
Node是HashMap的一個內(nèi)部類，實現(xiàn)了Map.Entry接口盐数，本質(zhì)是就是一個映射(鍵值對)棒拂。上圖中的每個黑色圓點就是一個Node對象。
- HashMap就是使用哈希表來存儲的玫氢。哈希表為解決沖突帚屉，可以采用開放地址法和鏈地址法等來解決問題谜诫，Java中HashMap采用了鏈地址法。鏈地址法涮阔，簡單來說猜绣，就是數(shù)組加鏈表的結(jié)合。在每個數(shù)組元素上都一個鏈表結(jié)構(gòu)敬特，當(dāng)數(shù)據(jù)被Hash后掰邢，得到數(shù)組下標(biāo)，把數(shù)據(jù)放在對應(yīng)下標(biāo)元素的鏈表上伟阔。例如程序執(zhí)行下面代碼：
map.put("皇家馬德里","C羅")
系統(tǒng)將調(diào)用"皇家馬德里"這個key的hashCode()方法得到其hashCode 值（該方法適用于每個Java對象）辣之，然后再通過Hash算法的后兩步運算（高位運算和取模運算，下文有介紹）來定位該鍵值對的存儲位置皱炉，有時兩個key會定位到相同的位置怀估，表示發(fā)生了Hash碰撞。當(dāng)然Hash算法計算結(jié)果越分散均勻合搅，Hash碰撞的概率就越小多搀，map的存取效率就會越高。
在理解Hash和擴容流程之前灾部，我們得先了解下HashMap的幾個字段康铭。從HashMap的默認(rèn)構(gòu)造函數(shù)源碼可知，構(gòu)造函數(shù)就是對下面幾個字段進(jìn)行初始化赌髓，源碼如下：
int threshold; // 所能容納的key-value對極限
final float loadFactor; // 負(fù)載因子
int modCount;
int size;
首先从藤，Node[] table的初始化長度length(默認(rèn)值是16)，Load factor為負(fù)載因子(默認(rèn)值是0.75)锁蠕，threshold是HashMap所能容納的最大數(shù)據(jù)量的Node(鍵值對)個數(shù)夷野。threshold = length * Load factor。也就是說荣倾，在數(shù)組定義好長度之后悯搔，負(fù)載因子越大，所能容納的鍵值對個數(shù)越多舌仍。threshold就是在此Load factor和length(數(shù)組長度)對應(yīng)下允許的最大元素數(shù)目鳖孤，超過這個數(shù)目就重新resize(擴容)，擴容后的HashMap容量是之前容量的兩倍抡笼。
size這個字段其實很好理解苏揣，就是HashMap中實際存在的鍵值對數(shù)量。注意和table的長度length推姻、容納最大鍵值對數(shù)量threshold的區(qū)別平匈。而modCount字段主要用來記錄HashMap內(nèi)部結(jié)構(gòu)發(fā)生變化的次數(shù)。強調(diào)一點，內(nèi)部結(jié)構(gòu)發(fā)生變化指的是結(jié)構(gòu)發(fā)生變化增炭，例如put新鍵值對忍燥，但是某個key對應(yīng)的value值被覆蓋不屬于結(jié)構(gòu)變化。
在HashMap中隙姿，哈希桶數(shù)組table的長度length大小必須為2的n次方(一定是合數(shù))梅垄，這是一種非常規(guī)的設(shè)計，常規(guī)的設(shè)計是把桶的大小設(shè)計為素數(shù)输玷，應(yīng)為素數(shù)導(dǎo)致沖突的概率小于合數(shù)队丝。
這里存在一個問題，即使負(fù)載因子和Hash算法設(shè)計的再合理欲鹏，也免不了會出現(xiàn)拉鏈過長的情況机久，一旦出現(xiàn)拉鏈過長，則會嚴(yán)重影響HashMap的性能赔嚎。于是膘盖，在JDK1.8版本中，對數(shù)據(jù)結(jié)構(gòu)做了進(jìn)一步的優(yōu)化尤误，引入了紅黑樹侠畔。而當(dāng)鏈表長度太長（默認(rèn)超過8）時，鏈表就轉(zhuǎn)換為紅黑樹损晤，利用紅黑樹快速增刪改查的特點提高HashMap的性能软棺，其中會用到紅黑樹的插入、刪除沉馆、查找等算法
(插入 https://blog.csdn.net/Lyt15829797751/article/details/81054920)
(刪除 https://blog.csdn.net/qq_37169817/article/details/78880110)
功能實現(xiàn)-方法
1. 確定哈希桶數(shù)組的索引位置
不管增加码党、刪除德崭、查找鍵值對斥黑，定位到哈希桶數(shù)組的位置都是很關(guān)鍵的第一步。前面說過HashMap的數(shù)據(jù)結(jié)構(gòu)是數(shù)組和鏈表的結(jié)合眉厨，所以我們當(dāng)然希望這個HashMap里面的元素位置盡量分布均勻些锌奴，盡量使得每個位置上的元素數(shù)量只有一個，那么當(dāng)我們用hash算法求得這個位置的時候憾股，馬上就可以知道對應(yīng)位置的元素就是我們要的鹿蜀，不用遍歷鏈表，大大優(yōu)化了查詢的效率服球。HashMap定位數(shù)組索引位置茴恰，直接決定了hash方法的離散性能。
源碼的實現(xiàn)：
方法一：
static final int hash(Object key) { //jdk1.8 & jdk1.7
int h;
// h = key.hashCode() 為第一步 取hashCode值
// h ^ (h >>> 16) 為第二步 高位參與運算
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
方法二：
static int indexFor(int h, int length) { //jdk1.7的源碼斩熊，jdk1.8沒有這個方法往枣，但是實現(xiàn)原理一樣的
return h & (length-1); //第三步 取模運算
}
總結(jié)來說就是：取key的hashCode值、高位運算、取模運算分冈。
其中 n為table的長度
2. HashMap的put方法
HashMap的put方法執(zhí)行過程可以通過下圖來理解
①.判斷鍵值對數(shù)組table[i]是否為空或為null圾另，否則執(zhí)行resize()進(jìn)行擴容；
②.根據(jù)鍵值key計算hash值得到插入的數(shù)組索引i雕沉，如果table[i]==null集乔，直接新建節(jié)點添加，轉(zhuǎn)向⑥坡椒，如果table[i]不為空扰路，轉(zhuǎn)向③；
③.判斷table[i]的首個元素是否和key一樣肠牲，如果相同直接覆蓋value幼衰，否則轉(zhuǎn)向④，這里的相同指的是hashCode以及equals缀雳；
④.判斷table[i] 是否為treeNode渡嚣，即table[i] 是否是紅黑樹，如果是紅黑樹肥印，則直接在樹中插入鍵值對识椰，否則轉(zhuǎn)向⑤；
⑤.遍歷table[i]深碱，判斷鏈表長度是否大于8腹鹉，大于8的話把鏈表轉(zhuǎn)換為紅黑樹，在紅黑樹中執(zhí)行插入操作敷硅，否則進(jìn)行鏈表的插入操作功咒；遍歷過程中若發(fā)現(xiàn)key已經(jīng)存在直接覆蓋value即可；
⑥.插入成功后绞蹦，判斷實際存在的鍵值對數(shù)量size是否超多了最大容量threshold力奋，如果超過，進(jìn)行擴容幽七。
JDK1.8中HashMap的put方法
public V put(K key, V value) {
// 對key的hashCode()做hash
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// tab為空則創(chuàng)建
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 計算index景殷，并對null做處理
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// 節(jié)點存在
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 該鏈為樹
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);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 寫入
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 超過load factor*current capacity，resize
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
3. get函數(shù)的實現(xiàn)
get的流程大致如下：
- 若為table中的第一個節(jié)點澡屡，直接命中猿挚；
- 如果有沖突，則通過key.equals(k)去查找對應(yīng)的entry驶鹉，若為樹绩蜻，則在樹中通過key.equals(k)查找，O(logn)室埋；若為鏈表办绝，則在鏈表中通過key.equals(k)查找踏兜，O(n)。
代碼如下
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 直接命中
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// 未命中
if ((e = first.next) != null) {
// 在樹中g(shù)et
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// 在鏈表中g(shù)et
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
4. resize的實現(xiàn)
當(dāng)put時八秃，如果發(fā)現(xiàn)目前的bucket(即哈希桶數(shù)組)占用程度已經(jīng)超過了Load Factor所希望的比例碱妆，那么就會發(fā)生resize。在resize的過程昔驱，簡單的說就是把bucket擴充為2倍疹尾，之后重新計算index，把節(jié)點再放到新的bucket中(jdk1.8)骤肛。
當(dāng)我們使用2次冪的擴展時(即長度擴展為原來的兩倍)纳本，所以，元素的位置要么是在原位置腋颠，要么是在原位置再移動2次冪的位置繁成。
因為n變?yōu)?倍，那么n-1的mask范圍在高位多1bit(紅色)淑玫，因此新的index就會發(fā)生這樣的變化：
因此巾腕，我們在擴充HashMap的時候，不需要重新計算hash絮蒿，只需要看看原來的hash值新增的那個bit是1還是0就好了尊搬，是0的話索引沒變，是1的話索引變成“原索引+oldCap”土涝》鹗伲可以看看下圖為16擴充為32的resize示意圖：
鏈表后的key值hash后，第5位bit 依次為1,0,1,0
HashMap的線程不安全性
在并發(fā)場景下但壮，當(dāng)我們對hashmap進(jìn)行put操作時冀泻，得到的hashmap的最終結(jié)果由于線程不安全性，就會出現(xiàn)不一致的情況蜡饵。我們具體舉一個例子進(jìn)行查看：
public void hashMapTest() throws Exception{
Thread t1 = new Thread(){
@Override
public void run() {
for (int i = 0; i < 100 ; i++) {
map.put(String.valueOf(i),String.valueOf(i));
}
}
};
Thread t2 = new Thread(){
@Override
public void run() {
for (int i = 100; i <200 ; i++) {
map.put(String.valueOf(i),String.valueOf(i));
}
}
};
t1.start();
t2.start();
System.out.println(Thread.currentThread().getContextClassLoader());
if (!Thread.currentThread().isInterrupted()) {
Thread.sleep(1000);
}
for (int i = 0; i < 200 ; i++) {
System.out.println("key:"+i+" value:"+map.get(i));
}
}
得到結(jié)果：
一般我們都是使用默認(rèn)構(gòu)造方法HashMap<K,V>聲明HashMap弹渔，但是看一下代碼就會發(fā)現(xiàn)還有其他的構(gòu)造方法：HashMap(int initialCapacity, float loadFactor)，其中參數(shù)initialCapacity是初始容量验残，loadFactor是加載因子捞附。而我們之前看到的threshold = (int)(capacity * loadFactor); 在默認(rèn)的情況下巾乳，一個HashMap的容量為16您没，加載因子為0.75，那么他的閥值就是12胆绊。
注意：jdk1.8的hashmap不會在并發(fā)情況下造成死循環(huán)氨鹏，但依然會導(dǎo)致數(shù)據(jù)丟失的發(fā)生(多線程情況下的數(shù)據(jù)覆蓋問題)
