HashMap的實現(xiàn)原理詳解，看這篇就夠了
一線資深java工程師明確了需要精通集合容器，尤其是今天我談到的HashMap。
HashMap在Java集合的重要性不亞于Volatile在并發(fā)編程的重要性(可見性與有序性)。
我會重點講解以下9點：
- HashMap的數(shù)據(jù)結(jié)構
- HashMap核心成員
- HashMapd的Node數(shù)組
- HashMap的數(shù)據(jù)存儲
- HashMap的哈希函數(shù)
- 哈希沖突：鏈式哈希表
- HashMap的get方法：哈希函數(shù)
- HashMap的put方法
- 為什么槽位數(shù)必須使用2^n?
HashMap的數(shù)據(jù)結(jié)構
首先我們從數(shù)據(jù)結(jié)構的角度來看：HashMap是:數(shù)組+鏈表+紅黑樹(JDK1.8增加了紅黑樹部分)的數(shù)據(jù)結(jié)構，如下所示:
這里需要搞明白兩個問題：
- 數(shù)據(jù)底層具體存儲的是什么?
- 這樣的存儲方式有什么優(yōu)點呢?
1.核心成員
默認初始容量(數(shù)組默認大小):16，2的整數(shù)次方static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 最大容量static final int MAXIMUM_CAPACITY = 1 << 30; 默認負載因子static final float DEFAULT_LOAD_FACTOR = 0.75f;裝載因子用來衡量HashMap滿的程度，表示當map集合中存儲的數(shù)據(jù)達到當前數(shù)組大小的75%則需要進行擴容 鏈表轉(zhuǎn)紅黑樹邊界static final int TREEIFY_THRESHOLD = 8; 紅黑樹轉(zhuǎn)離鏈表邊界static final int UNTREEIFY_THRESHOLD = 6; 哈希桶數(shù)組transient Node[] table; 實際存儲的元素個數(shù)transient int size; 當map里面的數(shù)據(jù)大于這個threshold就會進行擴容int threshold 閾值 = table.length * loadFactor
2.Node數(shù)組
從源碼可知，HashMap類中有一個非常重要的字段，就是 Node[] table，即哈希桶數(shù)組，明顯它是一個Node的數(shù)組。
- static class Node implements Map.Entry { final int hash;//用來定位數(shù)
- 組索引位置 final K key; V value; Node next;//鏈表的下一個Node節(jié)點
- 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的一個內(nèi)部類，實現(xiàn)了Map.Entry接口，本質(zhì)是就是一個映射(鍵值對)。
HashMap的數(shù)據(jù)存儲
1.哈希表來存儲
HashMap采用哈希表來存儲數(shù)據(jù)。
哈希表(Hash table，也叫散列表)，是根據(jù)關鍵碼值(Key value)而直接進行訪問的數(shù)據(jù)結(jié)構，只要輸入待查找的值即key，即可查找到其對應的值。
哈希表其實就是數(shù)組的一種擴展，由數(shù)組演化而來。可以說，如果沒有數(shù)組，就沒有散列表。
2.哈希函數(shù)
哈希表中元素是由哈希函數(shù)確定的,將數(shù)據(jù)元素的關鍵字Key作為自變量，通過一定的函數(shù)關系(稱為哈希函數(shù))，計算出的值，即為該元素的存儲地址。
表示為：Addr = H(key),如下圖所示：
哈希表中哈希函數(shù)的設計是相當重要的，這也是建哈希表過程中的關鍵問題之一。
3.核心問題
建立一個哈希表之前需要解決兩個主要問題：
- 構造一個合適的哈希函數(shù),均勻性 H(key)的值均勻分布在哈希表中
- 沖突的處理
沖突：在哈希表中，不同的關鍵字值對應到同一個存儲位置的現(xiàn)象。
4.哈希沖突：鏈式哈希表
哈希表為解決沖突，可以采用地址法和鏈地址法等來解決問題，Java中HashMap采用了鏈地址法。
鏈地址法，簡單來說，就是數(shù)組加鏈表的結(jié)合,如下圖所示：
HashMap的哈希函數(shù)
- /*** 重新計算哈希值*/static final int hash(Object key) { int h; // h = key.hashCode() 為第一步 取hashCode值 // h ^ (h >>> 16) 為第二步 高位參與運算 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}
//計算數(shù)組槽位
- (n - 1) & hash
對key進行了hashCode運算，得到一個32位的int值h,然后用h 異或 h>>>16位。在JDK1.8的實現(xiàn)中，優(yōu)化了高位運算的算法，通過hashCode()的高16位異或低16位實現(xiàn)的：(h = k.hashCode()) ^ (h >>> 16)。
這樣做的好處是，可以將hashcode高位和低位的值進行混合做異或運算，而且混合后，低位的信息中加入了高位的信息，這樣高位的信息被變相的保留了下來。
等于說計算下標時把hash的高16位也參與進來了，摻雜的元素多了，那么生成的hash值的隨機性會增大，減少了hash碰撞。
備注：
- ^異或：不同為1，相同為0
- >>> ：無符號右移：右邊補0
- &運算：兩位同時為“1”，結(jié)果才為“1，否則為0
h & (table.length -1)來得到該對象的保存位，而HashMap底層數(shù)組的長度總是2的n次方。
為什么槽位數(shù)必須使用2^n?
1.為了讓哈希后的結(jié)果更加均勻
假如槽位數(shù)不是16，而是17，則槽位計算公式變成：(17 – 1) & hash
從上文可以看出，計算結(jié)果將會大大趨同，hashcode參加&運算后被更多位的0屏蔽，計算結(jié)果只剩下兩種0和16，這對于hashmap來說是一種災難。2.等價于length取模
當length總是2的n次方時，h& (length-1)運算等價于對length取模，也就是h%length，但是&比%具有更高的效率。
位運算的運算效率高于算術運算，原因是算術運算還是會被轉(zhuǎn)化為位運算。
最終目的還是為了讓哈希后的結(jié)果更均勻的分部，減少哈希碰撞，提升hashmap的運行效率。
分析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;
- // 當前對象的數(shù)組是null 或者數(shù)組長度時0時，則需要初始化數(shù)組
- if ((tab = table) == null || (n = tab.length) == 0) { n = (tab = resize()).length; } // 使用hash與數(shù)組長度減一的值進行異或得到分散的數(shù)組下標，預示著按照計算現(xiàn)在的 // key會存放
- 到這個位置上，如果這個位置上沒有值，那么直接新建k-v節(jié)點存放 //
- 其中長度n是一個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)了碰撞 // 這個時候需要更為復雜處理碰撞的方式來處理，
- 如鏈表和樹 else { Node<K,V> e; K k; //節(jié)點
- key存在，直接覆蓋value if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) {
- e = p; } // 判斷該鏈為紅黑樹 else if (p instanceof TreeNode) { // 其中this表示當前HashMap, tab為map中的數(shù)組
- e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); } else { // 判斷該鏈為鏈表
- for (int binCount = 0; ; ++binCount) { // 如果當前碰撞到的節(jié)點沒有后續(xù)節(jié)點，則直接新建節(jié)點并追加 if ((e = p.next) == null) {
- p.next = newNode(hash, key, value, null); // TREEIFY_THRESHOLD = 8
- // 從0開始的，如果到了7則說明滿8了，這個時候就需要轉(zhuǎn) // 重新確定是否是擴容還是轉(zhuǎn)用紅黑樹了
- if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } // 找到了碰撞節(jié)點中，key完全相等的節(jié)點，則用新節(jié)點替換老節(jié)點 if (e.hash == hash &&
- ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } // 此時的e是保存的被碰撞的那個節(jié)點，即老節(jié)點 if (e != null) { // existing mapping for key
- V oldValue = e.value;
- // onlyIfAbsent是方法的調(diào)用參數(shù)，表示是否替換已存在的值，
- // 在默認的put方法中這個值是false，所以這里會用新值替換舊值 if (!onlyIfAbsent || oldValue == null) e.value = value;
- // Callbacks to allow LinkedHashMap post-actions afterNodeAccess(e);
- return oldValue;
- } } // map變更性操作計數(shù)器 // 比如map結(jié)構化的變更像內(nèi)容增減或者rehash，這將直接導致外部map的并發(fā)
- // 迭代引起fail-fast問題，該值就是比較的基礎 ++modCount; // size即map中包括k-v數(shù)量的多少
- // 超過最大容量 就擴容 if (++size > threshold) resize(); // Callbacks to allow LinkedHashMap post-actions afterNodeInsertion(evict); return null;}
HashMap的put方法執(zhí)行過程整體如下：
- 判斷鍵值對數(shù)組table[i]是否為空或為null，否則執(zhí)行resize()進行擴容;
- 根據(jù)鍵值key計算hash值得到插入的數(shù)組索引i，如果table[i]==null，直接新建節(jié)點添加
- 判斷table[i]的首個元素是否和key一樣，如果相同直接覆蓋value
- 判斷table[i] 是否為treeNode，即table[i] 是否是紅黑樹，如果是紅黑樹，則直接在樹中插入鍵值對
- 遍歷table[i]，判斷鏈表長度是否大于8，大于8的話把鏈表轉(zhuǎn)換為紅黑樹，在紅黑樹中執(zhí)行插入操作，否則進行鏈表的插入操作;遍歷過程中若發(fā)現(xiàn)key已經(jīng)存在直接覆蓋value即可;
- 插入成功后，判斷實際存在的鍵值對數(shù)量size是否超多了最大容量threshold，如果超過，進行擴容。
HashMap總結(jié)
HashMap底層結(jié)構?基于Map接口的實現(xiàn)，數(shù)組+鏈表的結(jié)構，JDK 1.8后加入了紅黑樹，鏈表長度>8變紅黑樹,<6變鏈表
兩個對象的hashcode相同會發(fā)生什么? Hash沖突，HashMap通過鏈表來解決hash沖突
HashMap 中 equals() 和 hashCode() 有什么作用?HashMap 的添加、獲取時需要通過 key 的 hashCode() 進行 hash()，然后計算下標 ( n-1 & hash)，從而獲得要找的同的位置。當發(fā)生沖突(碰撞)時，利用 key.equals() 方法去鏈表或樹中去查找對應的節(jié)點
HashMap 何時擴容?put的元素達到容量乘負載因子的時候，默認16*0.75
hash 的實現(xiàn)嗎?h = key.hashCode()) ^ (h >>> 16)， hashCode 進行無符號右移 16 位，然后進行按位異或，得到這個鍵的哈希值，由于哈希表的容量都是 2 的 N 次方，在當前，元素的 hashCode() 在很多時候下低位是相同的，這將導致沖突(碰撞)，因此 1.8 以后做了個移位操作：將元素的 hashCode() 和自己右移 16 位后的結(jié)果求異或
HashMap線程安全嗎?HashMap讀寫效率較高，但是因為其是非同步的，即讀寫等操作都是沒有鎖保護的，所以在多線程場景下是不安全的，容易出現(xiàn)數(shù)據(jù)不一致的問題，在單線程場景下非常推薦使用。
以上就是HashMap的介紹，希望對你有所收獲!
