JDK 1.8中HashMap數(shù)據(jù)結(jié)構(gòu)的示例分析

這篇文章給大家分享的是有關(guān)JDK 1.8中HashMap數(shù)據(jù)結(jié)構(gòu)的示例分析的內(nèi)容。小編覺得挺實(shí)用的，因此分享給大家做個(gè)參考，一起跟隨小編過來看看吧。

概述

JDK 1.8對(duì)HashMap361天恒平臺(tái)制作，進(jìn)行了比較大的優(yōu)化，底層實(shí)現(xiàn)由之前的“數(shù)組+鏈表”改為“數(shù)組+鏈表+紅黑樹”，本文就HashMap的幾個(gè)常用的重要方法和JDK 1.8之前的死循環(huán)問題展開學(xué)習(xí)討論。JDK 1.8的HashMap的數(shù)據(jù)結(jié)構(gòu)如下圖所示，當(dāng)鏈表節(jié)點(diǎn)較少時(shí)仍然是以鏈表存在，當(dāng)鏈表節(jié)點(diǎn)較多時(shí)（大于8）會(huì)轉(zhuǎn)為紅黑樹。

幾個(gè)點(diǎn)：

先了解以下幾個(gè)點(diǎn)，有利于更好的理解HashMap的源碼和閱讀本文。

1. 頭節(jié)點(diǎn)指的是table表上索引位置的節(jié)點(diǎn)，也就是鏈表的頭節(jié)點(diǎn)。

2. 
   

3. 根結(jié)點(diǎn)（root節(jié)點(diǎn)）指的是紅黑樹最上面的那個(gè)節(jié)點(diǎn)，也就是沒有父節(jié)點(diǎn)的節(jié)點(diǎn)。

4. 
   

5. 紅黑樹的根結(jié)點(diǎn)不一定是索引位置的頭結(jié)點(diǎn)。

6. 
   

7. 轉(zhuǎn)為紅黑樹節(jié)點(diǎn)后，鏈表的結(jié)構(gòu)還存在，通過next屬性維持，紅黑樹節(jié)點(diǎn)在進(jìn)行操作時(shí)都會(huì)維護(hù)鏈表的結(jié)構(gòu)，并不是轉(zhuǎn)為紅黑樹節(jié)點(diǎn)，鏈表結(jié)構(gòu)就不存在了。

8. 
   

9. 在紅黑樹上，葉子節(jié)點(diǎn)也可能有next節(jié)點(diǎn)，因?yàn)榧t黑樹的結(jié)構(gòu)跟鏈表的結(jié)構(gòu)是互不影響的，不會(huì)因?yàn)槭侨~子節(jié)點(diǎn)就說該節(jié)點(diǎn)已經(jīng)沒有next節(jié)點(diǎn)。

10. 
    

11. 源碼中一些變量定義：如果定義了一個(gè)節(jié)點(diǎn)p，則pl為p的左節(jié)點(diǎn)，pr為p的右節(jié)點(diǎn)，pp為p的父節(jié)點(diǎn)，ph為p的hash值，pk為p的key值，kc為key的類等等。源碼中很喜歡在if/for等語句中進(jìn)行賦值并判斷，請(qǐng)注意。

12. 
    

13. 鏈表中移除一個(gè)節(jié)點(diǎn)只需如下圖操作，其他操作同理。

14. 
    

15. 紅黑樹在維護(hù)鏈表結(jié)構(gòu)時(shí)，移除一個(gè)節(jié)點(diǎn)只需如下圖操作（紅黑樹中增加了一個(gè)prev屬性），其他操作同理。注：此處只是紅黑樹維護(hù)鏈表結(jié)構(gòu)的操作，紅黑樹還需要單獨(dú)進(jìn)行紅黑樹的移除或者其他操作。

16. 
    

17. 源碼中進(jìn)行紅黑樹的查找時(shí)，會(huì)反復(fù)用到以下兩條規(guī)則：1）如果目標(biāo)節(jié)點(diǎn)的hash值小于p節(jié)點(diǎn)的hash值，則向p節(jié)點(diǎn)的左邊遍歷；否則向p節(jié)點(diǎn)的右邊遍歷。2）如果目標(biāo)節(jié)點(diǎn)的key值小于p節(jié)點(diǎn)的key值，則向p節(jié)點(diǎn)的左邊遍歷；否則向p節(jié)點(diǎn)的右邊遍歷。這兩條規(guī)則是利用了紅黑樹的特性（左節(jié)點(diǎn)<根結(jié)點(diǎn)<右節(jié)點(diǎn)）。

18. 
    

19. 源碼中進(jìn)行紅黑樹的查找時(shí)，會(huì)用dir（direction）來表示向左還是向右查找，dir存儲(chǔ)的值是目標(biāo)節(jié)點(diǎn)的hash/key與p節(jié)點(diǎn)的hash/key的比較結(jié)果。

基本屬性

/** * The default initial capacity - MUST be a power of two. */static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 默認(rèn)容量16/** * The maximum capacity, used if a higher value is implicitly specified * by either of the constructors with arguments. * MUST be a power of two <= 1<<30. */static final int MAXIMUM_CAPACITY = 1 << 30;    // 最大容量/** * The load factor used when none specified in constructor. */static final float DEFAULT_LOAD_FACTOR = 0.75f; // 默認(rèn)負(fù)載因子0.75/** * The bin count threshold for using a tree rather than list for a * bin.  Bins are converted to trees when adding an element to a * bin with at least this many nodes. The value must be greater * than 2 and should be at least 8 to mesh with assumptions in * tree removal about conversion back to plain bins upon * shrinkage. */static final int TREEIFY_THRESHOLD = 8; // 鏈表節(jié)點(diǎn)轉(zhuǎn)換紅黑樹節(jié)點(diǎn)的閾值, 9個(gè)節(jié)點(diǎn)轉(zhuǎn)/** * The bin count threshold for untreeifying a (split) bin during a * resize operation. Should be less than TREEIFY_THRESHOLD, and at * most 6 to mesh with shrinkage detection under removal. */static final int UNTREEIFY_THRESHOLD = 6;   // 紅黑樹節(jié)點(diǎn)轉(zhuǎn)換鏈表節(jié)點(diǎn)的閾值, 6個(gè)節(jié)點(diǎn)轉(zhuǎn)/** * The smallest table capacity for which bins may be treeified. * (Otherwise the table is resized if too many nodes in a bin.) * Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts * between resizing and treeification thresholds. */static final int MIN_TREEIFY_CAPACITY = 64; // 轉(zhuǎn)紅黑樹時(shí), table的最小長度/** * Basic hash bin node, used for most entries.  (See below for * TreeNode subclass, and in LinkedHashMap for its Entry subclass.) */static class Node<K,V> implements Map.Entry<K,V> {  // 基本hash節(jié)點(diǎn), 繼承自Entryfinal 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;}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;}}/** * Entry for Tree bins. Extends LinkedHashMap.Entry (which in turn * extends Node) so can be used as extension of either regular or * linked node. */static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {// 紅黑樹節(jié)點(diǎn)TreeNode<K,V> parent;  // red-black tree linksTreeNode<K,V> left;TreeNode<K,V> right;TreeNode<K,V> prev;    // needed to unlink next upon deletionboolean red;TreeNode(int hash, K key, V val, Node<K,V> next) {super(hash, key, val, next);}// ...}

定位哈希桶數(shù)組索引位置

不管增加、刪除、查找鍵值對(duì)，定位到哈希桶數(shù)組的位置都是很關(guān)鍵的第一步。前面說過HashMap的數(shù)據(jù)結(jié)構(gòu)是“數(shù)組+鏈表+紅黑樹”的結(jié)合，所以我們當(dāng)然希望這個(gè)HashMap里面的元素位置盡量分布均勻些，盡量使得每個(gè)位置上的元素?cái)?shù)量只有一個(gè)，那么當(dāng)我們用hash算法求得這個(gè)位置的時(shí)候，馬上就可以知道對(duì)應(yīng)位置的元素就是我們要的，不用遍歷鏈表/紅黑樹，大大優(yōu)化了查詢的效率。HashMap定位數(shù)組索引位置，直接決定了hash方法的離散性能。下面是定位哈希桶數(shù)組的源碼：

// 代碼1static final int hash(Object key) { // 計(jì)算key的hash值int h;// 1.先拿到key的hashCode值; 2.將hashCode的高16位參與運(yùn)算return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}// 代碼2int n = tab.length;// 將(tab.length - 1) 與 hash值進(jìn)行&運(yùn)算int index = (n - 1) & hash;

整個(gè)過程本質(zhì)上就是三步：

1. 拿到key的hashCode值

2. 
   

3. 將hashCode的高位參與運(yùn)算，重新計(jì)算hash值

4. 
   

5. 將計(jì)算出來的hash值與(table.length - 1)進(jìn)行&運(yùn)算

方法解讀：

對(duì)于任意給定的對(duì)象，只要它的hashCode()返回值相同，那么計(jì)算得到的hash值總是相同的。我們首先想到的就是把hash值對(duì)table長度取模運(yùn)算，這樣一來，元素的分布相對(duì)來說是比較均勻的。

但是模運(yùn)算消耗還是比較大的，我們知道計(jì)算機(jī)比較快的運(yùn)算為位運(yùn)算，因此JDK團(tuán)隊(duì)對(duì)取模運(yùn)算進(jìn)行了優(yōu)化，使用上面代碼2的位與運(yùn)算來代替模運(yùn)算。這個(gè)方法非常巧妙，它通過 “(table.length -1) & h” 來得到該對(duì)象的索引位置，這個(gè)優(yōu)化是基于以下公式：x mod 2^n = x & (2^n - 1)。我們知道HashMap底層數(shù)組的長度總是2的n次方，并且取模運(yùn)算為“h mod table.length”，對(duì)應(yīng)上面的公式，可以得到該運(yùn)算等同于“h & (table.length - 1)”。這是HashMap在速度上的優(yōu)化，因?yàn)?amp;比%具有更高的效率。

在JDK1.8的實(shí)現(xiàn)中，還優(yōu)化了高位運(yùn)算的算法，將hashCode的高16位與hashCode進(jìn)行異或運(yùn)算，主要是為了在table的length較小的時(shí)候，讓高位也參與運(yùn)算，并且不會(huì)有太大的開銷。

感謝各位的閱讀！關(guān)于“JDK 1.8中HashMap數(shù)據(jù)結(jié)構(gòu)的示例分析”這篇文章就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，讓大家可以學(xué)到更多知識(shí)，如果覺得文章不錯(cuò)，可以把它分享出去讓更多的人看到吧！