一線資深java工程師明確了需要精通集合容器，尤其是今天我談到的HashMap。

[[440095]]

HashMap在Java集合的重要性不亞于Volatile在并發(fā)編程的重要性(可見性與有序性)。

我會(huì)重點(diǎn)講解以下9點(diǎn)：

1. HashMap的數(shù)據(jù)結(jié)構(gòu)
2. HashMap核心成員
3. HashMapd的Node數(shù)組
4. HashMap的數(shù)據(jù)存儲(chǔ)
5. HashMap的哈希函數(shù)
6. 哈希沖突：鏈?zhǔn)焦１?/li>
7. HashMap的get方法：哈希函數(shù)
8. HashMap的put方法
9. 為什么槽位數(shù)必須使用2^n?

HashMap的數(shù)據(jù)結(jié)構(gòu)

首先我們從數(shù)據(jù)結(jié)構(gòu)的角度來看：HashMap是:數(shù)組+鏈表+紅黑樹(JDK1.8增加了紅黑樹部分)的數(shù)據(jù)結(jié)構(gòu)，如下所示:

這里需要搞明白兩個(gè)問題：

• 數(shù)據(jù)底層具體存儲(chǔ)的是什么?
• 這樣的存儲(chǔ)方式有什么優(yōu)點(diǎn)呢?

1.核心成員

默認(rèn)初始容量(數(shù)組默認(rèn)大小):16，2的整數(shù)次方static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 最大容量static final int MAXIMUM_CAPACITY = 1 << 30; 默認(rèn)負(fù)載因子static final float DEFAULT_LOAD_FACTOR = 0.75f;裝載因子用來衡量HashMap滿的程度，表示當(dāng)map集合中存儲(chǔ)的數(shù)據(jù)達(dá)到當(dāng)前數(shù)組大小的75%則需要進(jìn)行擴(kuò)容 鏈表轉(zhuǎn)紅黑樹邊界static final int TREEIFY_THRESHOLD = 8; 紅黑樹轉(zhuǎn)離鏈表邊界static final int UNTREEIFY_THRESHOLD = 6; 哈希桶數(shù)組transient Node[] table; 實(shí)際存儲(chǔ)的元素個(gè)數(shù)transient int size; 當(dāng)map里面的數(shù)據(jù)大于這個(gè)threshold就會(huì)進(jìn)行擴(kuò)容int threshold 閾值 = table.length * loadFactor

2.Node數(shù)組

從源碼可知，HashMap類中有一個(gè)非常重要的字段，就是 Node[] table，即哈希桶數(shù)組，明顯它是一個(gè)Node的數(shù)組。 

static class Node implements Map.Entry { final int hash;//用來定位數(shù) 
組索引位置 final K key; V value; Node next;//鏈表的下一個(gè)Node節(jié)點(diǎn)  
Node(int hash, K key, V value, Node next) { this.hash = hash;  
this.key = key; this.value = value; this.next = next; } public final  
K getKey() { return key; } public final V getValue() { return value; 
 } public final String toString() { return key + "=" + value; }  
public final int hashCode() { return Objects.hashCode(key) ^  
Objects.hashCode(value); } public final V setValue(V newValue) { V  
oldValue = value; value = newValue; return oldValue; } public final  
boolean equals(Object o) { if (o == this) return true; if (o  
instanceof Map.Entry) { Map.Entry e = (Map.Entry)o; if  
(Objects.equals(key, e.getKey()) && Objects.equals(value,  
e.getValue())) return true; } return false; }} 

Node是HashMap的一個(gè)內(nèi)部類，實(shí)現(xiàn)了Map.Entry接口，本質(zhì)是就是一個(gè)映射(鍵值對(duì))。

HashMap的數(shù)據(jù)存儲(chǔ)

1.哈希表來存儲(chǔ)

HashMap采用哈希表來存儲(chǔ)數(shù)據(jù)。

哈希表(Hash table，也叫散列表)，是根據(jù)關(guān)鍵碼值(Key value)而直接進(jìn)行訪問的數(shù)據(jù)結(jié)構(gòu)，只要輸入待查找的值即key，即可查找到其對(duì)應(yīng)的值。

哈希表其實(shí)就是數(shù)組的一種擴(kuò)展，由數(shù)組演化而來。可以說，如果沒有數(shù)組，就沒有散列表。

2.哈希函數(shù)

哈希表中元素是由哈希函數(shù)確定的,將數(shù)據(jù)元素的關(guān)鍵字Key作為自變量，通過一定的函數(shù)關(guān)系(稱為哈希函數(shù))，計(jì)算出的值，即為該元素的存儲(chǔ)地址。

表示為：Addr = H(key),如下圖所示：

哈希表中哈希函數(shù)的設(shè)計(jì)是相當(dāng)重要的，這也是建哈希表過程中的關(guān)鍵問題之一。

3.核心問題

建立一個(gè)哈希表之前需要解決兩個(gè)主要問題：

• 構(gòu)造一個(gè)合適的哈希函數(shù),均勻性 H(key)的值均勻分布在哈希表中
• 沖突的處理

沖突：在哈希表中，不同的關(guān)鍵字值對(duì)應(yīng)到同一個(gè)存儲(chǔ)位置的現(xiàn)象。

4.哈希沖突：鏈?zhǔn)焦１?/h3>

哈希表為解決沖突，可以采用地址法和鏈地址法等來解決問題，Java中HashMap采用了鏈地址法。

鏈地址法，簡(jiǎn)單來說，就是數(shù)組加鏈表的結(jié)合,如下圖所示：

HashMap的哈希函數(shù)

/*** 重新計(jì)算哈希值*/static final int hash(Object key) { int h; // h = key.hashCode() 為第一步 取hashCode值 // h ^ (h >>> 16) 為第二步 高位參與運(yùn)算 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);} 

//計(jì)算數(shù)組槽位

(n - 1) & hash 

對(duì)key進(jìn)行了hashCode運(yùn)算，得到一個(gè)32位的int值h,然后用h 異或 h>>>16位。在JDK1.8的實(shí)現(xiàn)中，優(yōu)化了高位運(yùn)算的算法，通過hashCode()的高16位異或低16位實(shí)現(xiàn)的：(h = k.hashCode()) ^ (h >>> 16)。

這樣做的好處是，可以將hashcode高位和低位的值進(jìn)行混合做異或運(yùn)算，而且混合后，低位的信息中加入了高位的信息，這樣高位的信息被變相的保留了下來。

等于說計(jì)算下標(biāo)時(shí)把hash的高16位也參與進(jìn)來了，摻雜的元素多了，那么生成的hash值的隨機(jī)性會(huì)增大，減少了hash碰撞。

備注：

• ^異或：不同為1，相同為0
• >>> ：無符號(hào)右移：右邊補(bǔ)0
• &運(yùn)算：兩位同時(shí)為“1”，結(jié)果才為“1，否則為0

h & (table.length -1)來得到該對(duì)象的保存位，而HashMap底層數(shù)組的長度總是2的n次方。

為什么槽位數(shù)必須使用2^n?

1.為了讓哈希后的結(jié)果更加均勻

假如槽位數(shù)不是16，而是17，則槽位計(jì)算公式變成：(17 – 1) & hash

從上文可以看出，計(jì)算結(jié)果將會(huì)大大趨同，hashcode參加&運(yùn)算后被更多位的0屏蔽，計(jì)算結(jié)果只剩下兩種0和16，這對(duì)于hashmap來說是一種災(zāi)難。2.等價(jià)于length取模

當(dāng)length總是2的n次方時(shí)，h& (length-1)運(yùn)算等價(jià)于對(duì)length取模，也就是h%length，但是&比%具有更高的效率。

位運(yùn)算的運(yùn)算效率高于算術(shù)運(yùn)算，原因是算術(shù)運(yùn)算還是會(huì)被轉(zhuǎn)化為位運(yùn)算。

最終目的還是為了讓哈希后的結(jié)果更均勻的分部，減少哈希碰撞，提升hashmap的運(yùn)行效率。

分析HashMap的put方法：

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,               boolean evict) {    Node<K,V>[] tab; Node<K,V> p; int n, i;    
     // 當(dāng)前對(duì)象的數(shù)組是null 或者數(shù)組長度時(shí)0時(shí)，則需要初始化數(shù)組  
   if ((tab = table) == null || (n = tab.length) == 0) {        n = (tab = resize()).length;    }        // 使用hash與數(shù)組長度減一的值進(jìn)行異或得到分散的數(shù)組下標(biāo)，預(yù)示著按照計(jì)算現(xiàn)在的    // key會(huì)存放 
到這個(gè)位置上，如果這個(gè)位置上沒有值，那么直接新建k-v節(jié)點(diǎn)存放    //  
其中長度n是一個(gè)2的冪次數(shù)    if ((p = tab[i = (n - 1) & hash]) ==  
null) {        tab[i] = newNode(hash, key, value, null);    }    
     // 如果走到else這一步，說明key索引到的數(shù)組位置上已經(jīng)存在內(nèi)容，即出現(xiàn)了碰撞    // 這個(gè)時(shí)候需要更為復(fù)雜處理碰撞的方式來處理， 
如鏈表和樹    else {        Node<K,V> e; K k;               //節(jié)點(diǎn) 
key存在，直接覆蓋value        if (p.hash == hash &&            ((k = p.key) == key || (key != null && key.equals(k)))) {    
         e = p;        }        // 判斷該鏈為紅黑樹        else if (p instanceof TreeNode) {            // 其中this表示當(dāng)前HashMap, tab為map中的數(shù)組           
  e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);        }        else {  // 判斷該鏈為鏈表            
 for (int binCount = 0; ; ++binCount) {                // 如果當(dāng)前碰撞到的節(jié)點(diǎn)沒有后續(xù)節(jié)點(diǎn)，則直接新建節(jié)點(diǎn)并追加                if ((e = p.next) == null) {                    
 p.next = newNode(hash, key, value, null);                    // TREEIFY_THRESHOLD = 8                     
// 從0開始的，如果到了7則說明滿8了，這個(gè)時(shí)候就需要轉(zhuǎn)                    // 重新確定是否是擴(kuò)容還是轉(zhuǎn)用紅黑樹了                   
  if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st                        treeifyBin(tab, hash);                    break;                }                // 找到了碰撞節(jié)點(diǎn)中，key完全相等的節(jié)點(diǎn)，則用新節(jié)點(diǎn)替換老節(jié)點(diǎn)                if (e.hash == hash &&                     
((k = e.key) == key || (key != null && key.equals(k))))                    break;                p = e;            }        }        // 此時(shí)的e是保存的被碰撞的那個(gè)節(jié)點(diǎn)，即老節(jié)點(diǎn)        if (e != null) { // existing mapping for key             
V oldValue = e.value;             
// onlyIfAbsent是方法的調(diào)用參數(shù)，表示是否替換已存在的值，            
 // 在默認(rèn)的put方法中這個(gè)值是false，所以這里會(huì)用新值替換舊值            if (!onlyIfAbsent || oldValue == null)                e.value = value;            
 // Callbacks to allow LinkedHashMap post-actions            afterNodeAccess(e);            
 return oldValue;         
}    }    // map變更性操作計(jì)數(shù)器    // 比如map結(jié)構(gòu)化的變更像內(nèi)容增減或者rehash，這將直接導(dǎo)致外部map的并發(fā)     
// 迭代引起fail-fast問題，該值就是比較的基礎(chǔ)    ++modCount;        // size即map中包括k-v數(shù)量的多少    
// 超過最大容量 就擴(kuò)容    if (++size > threshold)        resize();    // Callbacks to allow LinkedHashMap post-actions    afterNodeInsertion(evict);    return null;} 

HashMap的put方法執(zhí)行過程整體如下：

1. 判斷鍵值對(duì)數(shù)組table[i]是否為空或?yàn)閚ull，否則執(zhí)行resize()進(jìn)行擴(kuò)容;
2. 根據(jù)鍵值key計(jì)算hash值得到插入的數(shù)組索引i，如果table[i]==null，直接新建節(jié)點(diǎn)添加
3. 判斷table[i]的首個(gè)元素是否和key一樣，如果相同直接覆蓋value
4. 判斷table[i] 是否為treeNode，即table[i] 是否是紅黑樹，如果是紅黑樹，則直接在樹中插入鍵值對(duì)
5. 遍歷table[i]，判斷鏈表長度是否大于8，大于8的話把鏈表轉(zhuǎn)換為紅黑樹，在紅黑樹中執(zhí)行插入操作，否則進(jìn)行鏈表的插入操作;遍歷過程中若發(fā)現(xiàn)key已經(jīng)存在直接覆蓋value即可;
6. 插入成功后，判斷實(shí)際存在的鍵值對(duì)數(shù)量size是否超多了最大容量threshold，如果超過，進(jìn)行擴(kuò)容。

HashMap總結(jié)

HashMap底層結(jié)構(gòu)?基于Map接口的實(shí)現(xiàn)，數(shù)組+鏈表的結(jié)構(gòu)，JDK 1.8后加入了紅黑樹，鏈表長度>8變紅黑樹,<6變鏈表

兩個(gè)對(duì)象的hashcode相同會(huì)發(fā)生什么? Hash沖突，HashMap通過鏈表來解決hash沖突

HashMap 中 equals() 和 hashCode() 有什么作用?HashMap 的添加、獲取時(shí)需要通過 key 的 hashCode() 進(jìn)行 hash()，然后計(jì)算下標(biāo) ( n-1 & hash)，從而獲得要找的同的位置。當(dāng)發(fā)生沖突(碰撞)時(shí)，利用 key.equals() 方法去鏈表或樹中去查找對(duì)應(yīng)的節(jié)點(diǎn)

HashMap 何時(shí)擴(kuò)容?put的元素達(dá)到容量乘負(fù)載因子的時(shí)候，默認(rèn)16*0.75

hash 的實(shí)現(xiàn)嗎?h = key.hashCode()) ^ (h >>> 16)， hashCode 進(jìn)行無符號(hào)右移 16 位，然后進(jìn)行按位異或，得到這個(gè)鍵的哈希值，由于哈希表的容量都是 2 的 N 次方，在當(dāng)前，元素的 hashCode() 在很多時(shí)候下低位是相同的，這將導(dǎo)致沖突(碰撞)，因此 1.8 以后做了個(gè)移位操作：將元素的 hashCode() 和自己右移 16 位后的結(jié)果求異或

HashMap線程安全嗎?HashMap讀寫效率較高，但是因?yàn)槠涫欠峭降模醋x寫等操作都是沒有鎖保護(hù)的，所以在多線程場(chǎng)景下是不安全的，容易出現(xiàn)數(shù)據(jù)不一致的問題，在單線程場(chǎng)景下非常推薦使用。

以上就是HashMap的介紹，希望對(duì)你有所收獲!