面試必會：HashMap 實現原理解讀
- 2020 年 3 月 6 日
- 筆記
點擊上方 好好學java ，選擇 星標 公眾號
重磅資訊、乾貨，第一時間送達今日推薦：用好Java中的枚舉，真的沒有那麼簡單！個人原創+1博客：點擊前往，查看更多
作者：馮立彬 blog.csdn.net/fenglibing/article/details/91565912
HashMap是Java開發當中使用得非常多的一種數據結構，因為其可以快速的定位到需要查找到數據，其最快的速度可以達到O(1)，最差的時候也可以達到O(n)。本文以Java8中的HashMap做為分析原型，因為不同的JDK版本中的HashMap，可能存在着底層實現上的不一樣。
HashMap是通過數組存儲所有的數據，每個元素所存放數組的下標，是根據該存儲元素的key的Hash值與該數組的長度減去1做與運算，如下所示：
index = (length_of_array - 1) & hash_of_the_key;
數組中存放元素的數據結構使用了Node和TreeNode兩種數據結構，在單個Hash值對應的存儲元素小於8個時，默認值為Node的單向鏈表形式存儲，當單個Hash值存儲的元素大於8個時，其會使用TreeNode的數據結構存儲。
因為在單個Hash值對應的元素小於等於8個時，其查詢時間最差為O(8)，但是當單個Hash值對應的元素大於8個時，再通過Node的單向鏈表的方式進行查詢，速度上就會變得更慢了；這個時候HashMap就會將Node的普通節點轉為TreeNode（紅黑樹）進行存儲，這是由於TreeNode佔用的空間大小約為常規節點的兩倍，但是其查詢速度可以得到保證，這個是通過空間換時間了。當TreeNode中包括的元素變得比較少時，為了存儲空間的佔用，也會轉換為Node節點單向鏈表的方式實現，它們之間可以互相轉換的。
Node：
static class Node<K,V> implements Map.Entry<K,V> { final int hash; final K key; V value; Node<K,V> next; Node(int hash, K key, V value, Node<K,V> next) { this.hash = hash; this.key = key; this.value = value; this.next = next; } ...... }
可以看到每個Node中包括了4個屬性，分別為：
hash值：當前Node的Hash值 key：當前Node的key value:當前Node的value next:表示指向下一個Node的指針，相同hash值的Node，通過next進行遍歷查找
TreeNode：
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> { TreeNode<K,V> parent; // red-black tree links TreeNode<K,V> left; TreeNode<K,V> right; TreeNode<K,V> prev; // needed to unlink next upon deletion boolean red; TreeNode(int hash, K key, V val, Node<K,V> next) { super(hash, key, val, next); } ...... }
可以看到TreeNode使用的是紅黑樹（Red Black Tree）的數據結構，紅黑樹是一種自平衡二叉查找樹，在進行插入和刪除操作時通過特定操作保持二叉查找樹的平衡，從而獲得較高的查找性能，即使在最壞情況運行時間也是非常良好的，並且在實踐中是非常高效的，它可以在O(log n)時間內做查找、插入和刪除等操作，這裡的n 是樹中元素的數目。
以下是一張關於HashMap存儲結構的示意圖：
寫入數據（一切皆在注釋中）
其方法如下：
//寫入數據 public V put(K key, V value) { //首先根據hash方法，獲取對應key的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; //判斷用戶存放元素的數組是否為空 if ((tab = table) == null || (n = tab.length) == 0) //為空則進行初使化，並將初使化後的數組賦值給變量tab，數組的長值賦值給變量n n = (tab = resize()).length; //判斷根據hash值與數組長度減1求與得到的下標， //從數組中獲取元素並將其賦值給變量p(後續該變量p可以繼續使用)，並判斷該元素是否存在 if ((p = tab[i = (n - 1) & hash]) == null) //如果不存在則創建一個新的節點，並將其放到數組對應的下標中 tab[i] = newNode(hash, key, value, null); else {//根據數組的下標取到了元素，並且該元素p且不為空，下面要判斷p元素的類型是Node還是TreeNode Node<K,V> e; K k; //判斷該數組對應下標取到的第一值是不是與正在存入值的hash值相同、 //key相等（可能是對象，也可能是字符串），如果相等，則將取第一個值賦值給變量e if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; //判斷取的對象是不是TreeNode，如果是則執行TreeNode的put方法 else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); else {//是普通的Node節點， //根據next屬性對元素p執行單向鏈表的遍歷 for (int binCount = 0; ; ++binCount) { //如果被遍歷的元素最後的next為空，表示後面沒有節點了，則將新節點與當前節點的next屬性建立關係 if ((e = p.next) == null) { //做為當前節點的後面的一個節點 p.next = newNode(hash, key, value, null); //判斷當前節點的單向鏈接的數量（8個）是不是已經達到了需要將其轉換為TreeNode了 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st //如果是則將當前數組下標對應的元素轉換為TreeNode treeifyBin(tab, hash); break; } //判斷待插入的元素的hash值與key是否與單向鏈表中的某個元素的hash值與key是相同的，如果是則退出 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } //判斷是否找到了與待插入元素的hash值與key值都相同的元素 if (e != null) { // existing mapping for key V oldValue = e.value; //判斷是否要將舊值替換為新值 if (!onlyIfAbsent || oldValue == null) //滿足於未指定不替換或舊值為空的情況，執行將舊值替換為新值 e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; if (++size > threshold) resize(); afterNodeInsertion(evict); return null; }
Hash值的計算方法：
// 計算指定key的hash值，原理是將key的hash code與hash code無符號向右移16位的值，執行異或運算。 // 在Java中整型為4個位元組32位，無符號向右移16位，表示將高16位移到低16位上，然後再執行異或運行，也 // 就是將hash code的高16位與低16位進行異或運行。 // 小於等於65535的數，其高16位全部都為0，因而將小於等於65535的值向右無符號移16位，則該數就變成了 // 32位都是0，由於任何數與0進行異或都等於本身，因而hash code小於等於65535的key，其得到的hash值 // 就等於其本身的hash code。 static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }
計算邏輯如下圖所示：
讀取數據（一切皆在注釋中）
public V get(Object key) { Node<K,V> e; //根據Key獲取元素 if ((e = getNode(hash(key), key)) == null) return null; if (accessOrder) afterNodeAccess(e); return 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語句的第一個判斷條件 if ((tab = table) != null //將數組賦值給變量tab，將判斷是否為null && (n = tab.length) > 0 //將數組的長值賦值給變量n && (first = tab[(n - 1) & hash]) != null) {//判斷根據hash和數組長度減1的與運算，計算出來的的數組下標的第一個元素是不是為空 //判斷第一個元素是否要找的元素，大部份情況下只要hash值太集中，或者元素不是很多，第一個元素往往都是需要的最終元素 if (first.hash == hash && // always check first node ((k = first.key) == key || (key != null && key.equals(k)))) //第一個元素就是要找的元素，因為hash值和key都相等，直接返回 return first; if ((e = first.next) != null) {//如果第一元素不是要找到的元，則判斷其next指向是否還有元素 //有元素，判斷其是否是TreeNode if (first instanceof TreeNode) //是TreeNode則根據TreeNode的方式獲取數據 return ((TreeNode<K,V>)first).getTreeNode(hash, key); do {//是Node單向鏈表，則通過next循環匹配，找到就退出，否則直到匹配完最後一個元素才退出 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } while ((e = e.next) != null); } } //沒有找到則返回null return null; }
