HashMap的原理與實現

版本之更迭：

–》JDK 1.7 ： Table數組+ Entry鏈表；

–》JDK1.8 : Table數組+ Entry鏈表/紅黑樹；(為什么要使用紅黑樹？)

一問HashMap的實現原理

• 你看過HashMap源碼嗎，知道底層的原理嗎
• 為什么使用數組+鏈表
• 用LinkedList代替數組可以嗎
• 既然是可以的，為什么不用反而用數組。

重要變量介紹：

ps：都是重要的變量記憶理解一下最好。

• DEFAULT_INITIAL_CAPACITY Table數組的初始化長度： 1 << 4 2^4=16（為什么要是 2的n次方？）
• MAXIMUM_CAPACITY Table數組的最大長度： 1<<30 2^30=1073741824
• DEFAULT_LOAD_FACTOR 負載因子：默認值為0.75。 當元素的總個數>當前數組的長度 * 負載因子。數組會進行擴容，擴容為原來的兩倍（todo：為什么是兩倍？）
• TREEIFY_THRESHOLD 鏈表樹化闕值： 默認值為 8 。表示在一個node（Table）節點下的值的個數大于8時候，會將鏈表轉換成為紅黑樹。
• UNTREEIFY_THRESHOLD 紅黑樹鏈化闕值： 默認值為 6 。 表示在進行擴容期間，單個Node節點下的紅黑樹節點的個數小于6時候，會將紅黑樹轉化成為鏈表。
• MIN_TREEIFY_CAPACITY = 64 最小樹化閾值，當Table所有元素超過該值，才會進行樹化（為了防止前期階段頻繁擴容和樹化過程沖突）。

實現原理：

實現原理圖 我們都知道，在HashMap中，采用數組+鏈表的方式來實現對數據的儲存。

HashMap采?Entry數組來存儲key-value對，每?個鍵值對組成了?個Entry實體，Entry類實際上是?個單向的鏈表結 構，它具有Next指針，可以連接下?個Entry實體。 只是在JDK1.8中，鏈表?度?于8的時候，鏈表會轉成紅?樹！

第一問： 為什么使用鏈表+數組：要知道為什么使用鏈表首先需要知道Hash沖突是如何來的：

答： 由于我們的數組的值是限制死的，我們在對key值進行散列取到下標以后，放入到數組中時，難免出現兩個key值不同，但是卻放入到下標相同的格子中，此時我們就可以使用鏈表來對其進行鏈式的存放。

第二問 我?LinkedList代替數組結構可以嗎？

對于題目的意思是說，在源碼中我們是這樣的

Entry[] table=new Entry[capacity]; // entry就是一個鏈表的節點

現在進行替換，進行如下的實現

List<Entry> table=new LinkedList<Entry>();

是否可以行得通？ 答案當然是肯定的。

第三問 那既然可以使用進行替換處理，為什么有偏偏使用到數組呢？

因為?數組效率最?！ 在HashMap中，定位節點的位置是利?元素的key的哈希值對數組?度取模得到。此時，我們已得到節點的位置。顯然數組的查 找效率?LinkedList?（底層是鏈表結構）。

那ArrayList，底層也是數組，查找也快啊，為啥不?ArrayList? 因為采用基本數組結構，擴容機制可以??定義，HashMap中數組擴容剛好是2的次冪，在做取模運算的效率?。 ?ArrayList的擴容機制是1.5倍擴容（這一點我相信學習過的都應該清楚），那ArrayList為什么是1.5倍擴容這就不在本?說明了。

Hash沖突：得到下標值：

我們都知道在HashMap中 使用數組加鏈表，這樣問題就來了，數組使用起來是有下標的，但是我們平時使用HashMap都是這樣使用的：

HashMap<Integer,String> hashMap=new HashMap<>(); hashMap.put(2,"dd");

可以看到的是并沒有特地為我們存放進來的值指定下標，那是因為我們的hashMap對存放進來的key值進行了hashcode()，生成了一個值，但是這個值很大，我們不可以直接作為下標，此時我們想到了可以使用取余的方法，例如這樣：

key.hashcode()%Table.length；

即可以得到對于任意的一個key值，進行這樣的操作以后，其值都落在0-Table.length-1 中，但是 HashMap的源碼卻不是這樣做？

它對其進行了與操作，對Table的表長度減一再與生產的hash值進行相與：

if ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null);

我們來畫張圖進行進一步的了解；

這里我們也就得知為什么Table數組的長度要一直都為2的n次方，只有這樣，減一進行相與時候，才能夠達到最大的n-1值。

舉個栗子來反證一下：

我們現在 數組的長度為 15 減一為 14 ，二進制表示 0000 1110 進行相與時候，最后一位永遠是0，這樣就可能導致，不能夠完完全全的進行Table數組的使用。違背了我們最開始的想要對Table數組進行最大限度的無序使用的原則，因為HashMap為了能夠存取高效，，要盡量較少碰撞，就是要盡量把數據分配均勻，每個鏈表?度?致相同。

此時還有一點需要注意的是： 我們對key值進行hashcode以后，進行相與時候都是只用到了后四位，前面的很多位都沒有能夠得到使用,這樣也可能會導致我們所生成的下標值不能夠完全散列。

解決方案：將生成的hashcode值的高16位于低16位進行異或運算，這樣得到的值再進行相與，一得到最散列的下標值。

static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}

二問講一講HashMap的get/put過程

• 知道HashMap的put元素的過程是什么樣嗎？
• 知道get過程是是什么樣嗎？
• 你還知道哪些的hash算法？
• 說一說String的hashcode的實現

Put方法

1.對key的hashCode()做hash運算，計算index;

2.如果沒碰撞直接放到bucket?；

3.如果碰撞了，以鏈表的形式存在buckets后；

4.如果碰撞導致鏈表過?(?于等于TREEIFY_THRESHOLD)，就把鏈表轉換成紅?樹(JDK1.8中的改動)；

5.如果節點已經存在就替換old value(保證key的唯?性)

6.如果bucket滿了(超過load factor*current capacity)，就要resize

在得到下標值以后，可以開始put值進入到數組+鏈表中，會有三種情況：

數組的位置為空。

數組的位置不為空，且面是鏈表的格式。

數組的位置不為空，且下面是紅黑樹的格式。

同時 對于Key 和Value 也要經歷一下步驟

• 通過 Key 散列獲取到對于的Table；’
• 遍歷Table 下的Node節點，做更新/添加操作；
• 擴容檢測；

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) // HashMap的懶加載策略，當執行put操作時檢測Table數組初始化。n = (tab = resize()).length;if ((p = tab[i = (n - 1) & hash]) == null) //通過``Hash``函數獲取到對應的Table，如果當前Table為空，則直接初始化一個新的Node并放入該Table中。 tab[i] = newNode(hash, key, value, null);else {Node<K,V> e; K k;//進行值的判斷： 判斷對于是不是對于相同的key值傳進來不同的value，若是如此，將原來的value進行返回if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))e = p;else if (p instanceof TreeNode)// 如果當前Node類型為TreeNode，調用 PutTreeVal 方法。e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);else { //如果不是TreeNode，則就是鏈表，遍歷并與輸入key做命中碰撞。 for (int binCount = 0; ; ++binCount) {if ((e = p.next) == null) {//如果當前Table中不存在當前key，則添加。p.next = newNode(hash, key, value, null);if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st//超過了``TREEIFY_THRESHOLD``則轉化為紅黑樹。treeifyBin(tab, hash);break;}if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k)))) //做命中碰撞，使用hash、內存和equals同時判斷（不同的元素hash可能會一致）。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;if (++size > threshold)//擴容檢測！resize();afterNodeInsertion(evict);return null;}

以上就是HashMap的Put操作，若是對其中的紅黑樹的添加，以及Node鏈表和紅黑樹的轉換過程我們暫時不進行深入的討論，這個流程大概還是可以進行理解，下面來深入討論擴容問題。

resise方法

HashMap 的擴容實現機制是將老table數組中所有的Entry取出來，重新對其Hashcode做Hash散列到新的Table中，可以看到注解Initializes or doubles table size. resize表示的是對數組進行初始化或

進行Double處理。現在我們來一步一步進行分析。

/*** Initializes or doubles table size. If null, allocates in* accord with initial capacity target held in field threshold.* Otherwise, because we are using power-of-two expansion, the* elements from each bin must either stay at same index, or move* with a power of two offset in the new table.** @return the table*/final Node<K,V>[] resize() {//先將老的Table取別名，這樣利于后面的操作。Node<K,V>[] oldTab = table;int oldCap = (oldTab == null) ? 0 : oldTab.length;int oldThr = threshold;int newCap, newThr = 0;//表示之前的數組容量不為空。if (oldCap > 0) {// 如果 此時的數組容量大于最大值if (oldCap >= MAXIMUM_CAPACITY) {// 擴容 闕值為 Int類型的最大值，這種情況很少出現threshold = Integer.MAX_VALUE;return oldTab;}//表示 old數組的長度沒有那么大，進行擴容，兩倍（這里也是有講究的）對闕值也進行擴容else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY)newThr = oldThr << 1; // double threshold}//表示之前的容量是0 但是之前的闕值卻大于零， 此時新的hash表長度等于此時的闕值else if (oldThr > 0) // initial capacity was placed in thresholdnewCap = oldThr;else { // zero initial threshold signifies using defaults//表示是初始化時候，采用默認的 數組長度* 負載因子newCap = DEFAULT_INITIAL_CAPACITY;newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}//此時表示若新的闕值為0 就得用 新容量* 加載因子重新進行計算。if (newThr == 0) {float ft = (float)newCap * loadFactor;newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);}// 開始對新的hash表進行相對應的操作。threshold = newThr;@SuppressWarnings({"rawtypes","unchecked"})Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];table = newTab;if (oldTab != null) {//遍歷舊的hash表，將之內的元素移到新的hash表中。for (int j = 0; j < oldCap/***此時舊的hash表的闕值*/; ++j) {Node<K,V> e;if ((e = oldTab[j]) != null) {//表示這個格子不為空oldTab[j] = null;if (e.next == null)// 表示當前只有一個元素，重新做hash散列并賦值計算。newTab[e.hash & (newCap - 1)] = e;else if (e instanceof TreeNode)// 如果在舊哈希表中，這個位置是樹形的結果，就要把新hash表中也變成樹形結構，((TreeNode<K,V>)e).split(this, newTab, j, oldCap);else { // preserve order//保留 舊hash表中是鏈表的順序Node<K,V> loHead = null, loTail = null;Node<K,V> hiHead = null, hiTail = null;Node<K,V> next;do {// 遍歷當前Table內的Node 賦值給新的Table。next = e.next;// 原索引if ((e.hash & oldCap) == 0) {if (loTail == null)loHead = e;elseloTail.next = e;loTail = e;}// 原索引+oldCapelse {if (hiTail == null)hiHead = e;elsehiTail.next = e;hiTail = e;}} while ((e = next) != null);// 原索引放到bucket里面if (loTail != null) {loTail.next = null;newTab[j] = loHead;}// 原索引+oldCap 放到bucket里面if (hiTail != null) {hiTail.next = null;newTab[j + oldCap] = hiHead;}}}}}return newTab;}

get方法

1.對key的hashCode()做hash運算，計算index;

2.如果在bucket?的第?個節點?直接命中，則直接返回；

3.如果有沖突，則通過key.equals(k)去查找對應的Entry;

4. 若為樹，則在樹中通過key.equals(k)查找，O(logn)；

5. 若為鏈表，則在鏈表中通過key.equals(k)查找，O(n)。

在進行取值時候，因為對于我們傳進來的key值進行了一系列的hash操作，首先，在傳進來 key值時候，先進性hash操作，

final Node<K,V> getNode(int hash, Object key) {Node<K,V>[] tab; Node<K,V> first, e; int n; K k;// 判斷 表是否為空，表重讀是否大于零，并且根據此 key 對應的表內是否存在 Node節點。 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))))// 檢查第一個Node 節點，若是命中則不需要進行do... whirle 循環。return first;if ((e = first.next) != null) {if (first instanceof TreeNode)//樹形結構，采用 對應的檢索方法，進行檢索。return ((TreeNode<K,V>)first).getTreeNode(hash, key);do {//鏈表方法 做while循環，直到命中結束或者遍歷結束。if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))return e;} while ((e = e.next) != null);}}return null;}

containsKey 方法

根據get方法的結果，判斷是否為空，判斷是否包含該key

public boolean containsKey(Object key) {return getNode(hash(key), key) != null;}

還知道哪些hash算法

先說?下hash算法?嘛的，Hash函數是指把?個?范圍映射到?個?范圍。把?范圍映射到?個?范圍的?的往往是為了 節省空間，使得數據容易保存。

?較出名的有MurmurHash、MD4、MD5等等

String中hashcode的實現

public int hashCode() {int h = hash;if (h == 0 && value.length > 0) {char val[] = value;for (int i = 0; i < value.length; i++) {h = 31 * h + val[i];}hash = h;}return h;}

String類中的hashCode計算?法還是?較簡單的，就是以31為權，每?位為字符的ASCII值進?運算，??然溢出來等效 取模。

哈希計算公式可以計為ss[[00]]3311^^((nn–11)) ++ ss[[11]]3311^^((nn–22)) ++ …… ++ ss[[nn–11]]

那為什么以31為質數呢? 主要是因為31是?個奇質數，所以31i=32i-i=(i<<5)-i，這種位移與減法結合的計算相??般的運算快很多

三問 為什么hashmap的在鏈表元素數量超過8時候改為紅黑樹

• 知道jdk1.8中hashmap改了什么嗎。
• 說一下為什么會出現線程的不安全性
• 為什么在解決hash沖突時候，不直接用紅黑樹，而是先用鏈表，再用紅黑樹
• 當鏈表轉為紅黑樹，什么時候退化為鏈表

第一問改動了什么

1.由數組+鏈表的結構改為數組+鏈表+紅?樹。

2. 優化了?位運算的hash算法：h^(h>>>16)

3. 擴容后，元素要么是在原位置，要么是在原位置再移動2次冪的位置，且鏈表順序不變。

注意： 最后?條是重點，因為最后?條的變動，hashmap在1.8中，不會在出現死循環問題。

HashMap的線程不安全性

HashMap 在jdk1.7中 使用 數組加鏈表的方式，并且在進行鏈表插入時候使用的是頭結點插入的方法。

注 ：這里為什么使用 頭插法的原因是我們若是在散列以后，判斷得到值是一樣的，使用頭插法，不用每次進行遍歷鏈表的長度。但是這樣會有一個缺點，在進行擴容時候，會導致進入新數組時候出現倒序的情況，也會在多線程時候出現線程的不安全性。

但是對與 jdk1.8 而言，還是要進行闕值的判斷，判斷在什么時候進行紅黑樹和鏈表的轉換。所以無論什么時候都要進行遍歷，于是插入到尾部，防止出現擴容時候還會出現倒序情況。

所以當在多線程的使用場景中，盡量使用線程安全的ConcurrentHashMap。至于Hashtable而言，使用效率太低。

線程安全

// 擴容 void transfer(Entry[] newTable, boolean rehash) {int newCapacity = newTable.length;for (Entry<K,V> e : table) { // Awhile(null != e) { Entry<K,V> next = e.next; if (rehash) {e.hash = null == e.key ? 0 : hash(e.key); }int i = indexFor(e.hash, newCapacity); e.next = newTable[i];newTable[i] = e;e = next; }

}

}

在jdk1.7若是產生了多線程，例如 thread1，和thread2，同時想要進入到 transfer中，此時會出現如下圖所示的情況：

此時對于我們的1會擁有兩個臨時變量，我們稱為e1與e2。這個時候，線程一會先執行上述的函數，進行數組的翻倍，并且，會進入逆序的狀態， 此時的 臨時變量e1和next1都已經消失，但是對于每個節點上面所擁有的連接不會更改，這個時候，1上還有一個e2臨時變量，2上有一個next2臨時變量。如下圖所示：

完成了線程一的擴容以后，線程二也會創建一個屬于自己的數組，長度也是6。這個時候開始又執行一遍以上的程序。

// 第一遍過來

e.next = newTable[i]; newTable[i] = e; e = next;

此時完成了第一次的循環以后，進入到以上的情況，這個時候 執行e.next = newTable[i]; 寓意為： 2所表示的下一個指向 newTable[i],此時我們就發現了問題的所在，在執行完第一遍循環以后，2所表示的下一下就已經指向了 newTable[i],就是我們的1 ，當然這樣我們就不用動，那我們就不動就好了，然后完成以后就如下圖所示。

// 第二遍來 e.next = newTable[i]; newTable[i] = e; e = next;

這個時候開始第三次的循環，首先執行 Entry<K,V> next = e.next; ，這個時候我們就發現了問題，e2和e2的next2都執行了1，這個時候我們再度，執行以上的語句就會指向一個空的節點，當然空就空了，暫時也還不會出現差錯，但是執行到 e.next = newTable[i];時候，會發現，執行到如下圖所示的情況。這個時候出現了循環鏈表，若是不加以控制，就會耗盡我們的cpu。

第三問為什么不一開始就使用紅黑樹，不是效率很高嗎?

因為紅?樹需要進?左旋，右旋，變?這些操作來保持平衡，?單鏈表不需要。

當元素?于8個當時候，此時做查詢操作，鏈表結構已經能保證查詢性能。

當元素?于8個的時候，此時需要紅?樹來加快查 詢速度，但是新增節點的效率變慢了。

因此，如果?開始就?紅?樹結構，元素太少，新增效率??較慢，?疑這是浪費性能的。

第四問什么時候退化為鏈表

為6的時候退轉為鏈表。中間有個差值7可以防?鏈表和樹之間頻繁的轉換。

假設?下，如果設計成鏈表個數超過8則鏈表轉 換成樹結構，鏈表個數?于8則樹結構轉換成鏈表，

如果?個HashMap不停的插?、刪除元素，鏈表個數在8左右徘徊，就會 頻繁的發?樹轉鏈表、鏈表轉樹，效率會很低。

四問HashMap的并發問題

• HashMap在并發環境下會有什么問題
• 一般是如何解決的

問題的出現

(1)多線程擴容，引起的死循環問題

(2)多線程put的時候可能導致元素丟失

(3)put?null元素后get出來的卻是null

不安全性的解決方案

在之前使用hashtable。 在每一個函數前面都加上了synchronized 但是 效率太低 我們現在不常用了。

使用 ConcurrentHashmap函數，對于這個函數而言 我們可以每幾個元素共用一把鎖。用于提高效率。

五問你一般用什么作為HashMap的key值

• key可以是null嗎，value可以是null嗎
• 一般用什么作為key值
• 用可變類當Hashmap1的Key會有什么問題
• 讓你實現一個自定義的class作為HashMap的Key該如何實現

key可以是null嗎，value可以是null嗎

當然都是可以的，但是對于 key來說只能運行出現一個key值為null，但是可以出現多個value值為null

一般用什么作為key值

?般?Integer、String這種不可變類當HashMap當key，?且String最為常?。

(1)因為字符串是不可變的，所以在它創建的時候hashcode就被緩存了，不需要重新計算。 這就使得字符串很適合作為Map中的鍵，字符串的處理速度要快過其它的鍵對象。 這就是HashMap中的鍵往往都使?字符串。

(2)因為獲取對象的時候要?到equals()和hashCode()?法，那么鍵對象正確的重寫這兩個?法是?常重要的,這些類已 經很規范的覆寫了hashCode()以及equals()?法。

用可變類當Hashmap1的Key會有什么問題

hashcode可能會發生變化，導致put進行的值，無法get出來，如下代碼所示：

HashMap<List<String>,Object> map=new HashMap<>();List<String> list=new ArrayList<>();list.add("hello");Object object=new Object();map.put(list,object);System.out.println(map.get(list));list.add("hello world");System.out.println(map.get(list));

輸出值如下：

java.lang.Object@1b6d3586 null

實現一個自定義的class作為Hashmap的key該如何實現

對于這個問題考查到了下面的兩個知識點

• 重寫hashcode和equals方法需要注意什么？
• 如何設計一個不變的類。

針對問題?，記住下?四個原則即可

(1)兩個對象相等，hashcode?定相等

(2)兩個對象不等，hashcode不?定不等

(3)hashcode相等，兩個對象不?定相等

(4)hashcode不等，兩個對象?定不等

針對問題?，記住如何寫?個不可變類

(1)類添加final修飾符，保證類不被繼承。 如果類可以被繼承會破壞類的不可變性機制，只要繼承類覆蓋?類的?法并且繼承類可以改變成員變量值，那么?旦?類 以?類的形式出現時，不能保證當前類是否可變。

(2)保證所有成員變量必須私有，并且加上final修飾 通過這種?式保證成員變量不可改變。但只做到這?步還不夠，因為如果是對象成員變量有可能再外部改變其值。所以第4 點彌補這個不?。

(3)不提供改變成員變量的?法，包括setter 避免通過其他接?改變成員變量的值，破壞不可變特性。

(4)通過構造器初始化所有成員，進?深拷?(deep copy)

(5) 在getter?法中，不要直接返回對象本?，?是克隆對象，并返回對象的拷? 這種做法也是防?對象外泄，防?通過getter獲得內部可變成員對象后對成員變量直接操作，導致成員變量發?改變

后記

對于HashMap而言，擴容是一個特別消耗內存的操作。所以當程序員在使用HashMap的時候，估算map的大小，初始化的時候給一個大致的數值，避免map進行頻繁的擴容。

負載因子是可以修改的，也可以大于1，但是建議不要輕易修改，除非情況非常特殊。

HashMap是線程不安全的，不要在并發的環境中同時操作HashMap，建議使用ConcurrentHashMap。

原文鏈接：https://blog.csdn.net/weixin_44015043/java/article/details/105346187

總結

以上是生活随笔為你收集整理的hashmap put过程_看完还不懂HashMap算我输（附互联网大厂面试常见问题）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。