這篇文章給大家分享的是有關JDK 1.8中HashMap數據結構的示例分析的內容。小編覺得挺實用的，因此分享給大家做個參考，一起跟隨小編過來看看吧。
JDK 1.8對HashMap361天恒平臺制作，進行了比較大的優化，底層實現由之前的“數組+鏈表”改為“數組+鏈表+紅黑樹”，本文就HashMap的幾個常用的重要方法和JDK 1.8之前的死循環問題展開學習討論。JDK 1.8的HashMap的數據結構如下圖所示，當鏈表節點較少時仍然是以鏈表存在，當鏈表節點較多時（大于8）會轉為紅黑樹。
先了解以下幾個點，有利于更好的理解HashMap的源碼和閱讀本文。
頭節點指的是table表上索引位置的節點，也就是鏈表的頭節點。
根結點（root節點）指的是紅黑樹最上面的那個節點，也就是沒有父節點的節點。
紅黑樹的根結點不一定是索引位置的頭結點。
轉為紅黑樹節點后，鏈表的結構還存在，通過next屬性維持，紅黑樹節點在進行操作時都會維護鏈表的結構，并不是轉為紅黑樹節點，鏈表結構就不存在了。
在紅黑樹上，葉子節點也可能有next節點，因為紅黑樹的結構跟鏈表的結構是互不影響的，不會因為是葉子節點就說該節點已經沒有next節點。
源碼中一些變量定義：如果定義了一個節點p，則pl為p的左節點，pr為p的右節點，pp為p的父節點，ph為p的hash值，pk為p的key值，kc為key的類等等。源碼中很喜歡在if/for等語句中進行賦值并判斷，請注意。
鏈表中移除一個節點只需如下圖操作，其他操作同理。
紅黑樹在維護鏈表結構時，移除一個節點只需如下圖操作（紅黑樹中增加了一個prev屬性），其他操作同理。注：此處只是紅黑樹維護鏈表結構的操作，紅黑樹還需要單獨進行紅黑樹的移除或者其他操作。
源碼中進行紅黑樹的查找時，會反復用到以下兩條規則：1）如果目標節點的hash值小于p節點的hash值，則向p節點的左邊遍歷；否則向p節點的右邊遍歷。2）如果目標節點的key值小于p節點的key值，則向p節點的左邊遍歷；否則向p節點的右邊遍歷。這兩條規則是利用了紅黑樹的特性（左節點<根結點<右節點）。
源碼中進行紅黑樹的查找時，會用dir（direction）來表示向左還是向右查找，dir存儲的值是目標節點的hash/key與p節點的hash/key的比較結果。
/** * The default initial capacity - MUST be a power of two. */static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 默認容量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; // 默認負載因子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; // 鏈表節點轉換紅黑樹節點的閾值, 9個節點轉/** * 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; // 紅黑樹節點轉換鏈表節點的閾值, 6個節點轉/** * 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; // 轉紅黑樹時, 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節點, 繼承自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> {// 紅黑樹節點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);}// ...}不管增加、刪除、查找鍵值對，定位到哈希桶數組的位置都是很關鍵的第一步。前面說過HashMap的數據結構是“數組+鏈表+紅黑樹”的結合，所以我們當然希望這個HashMap里面的元素位置盡量分布均勻些，盡量使得每個位置上的元素數量只有一個，那么當我們用hash算法求得這個位置的時候，馬上就可以知道對應位置的元素就是我們要的，不用遍歷鏈表/紅黑樹，大大優化了查詢的效率。HashMap定位數組索引位置，直接決定了hash方法的離散性能。下面是定位哈希桶數組的源碼：
// 代碼1static final int hash(Object key) { // 計算key的hash值int h;// 1.先拿到key的hashCode值; 2.將hashCode的高16位參與運算return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}// 代碼2int n = tab.length;// 將(tab.length - 1) 與 hash值進行&運算int index = (n - 1) & hash;整個過程本質上就是三步：
拿到key的hashCode值
將hashCode的高位參與運算，重新計算hash值
將計算出來的hash值與(table.length - 1)進行&運算
方法解讀：
對于任意給定的對象，只要它的hashCode()返回值相同，那么計算得到的hash值總是相同的。我們首先想到的就是把hash值對table長度取模運算，這樣一來，元素的分布相對來說是比較均勻的。
但是模運算消耗還是比較大的，我們知道計算機比較快的運算為位運算，因此JDK團隊對取模運算進行了優化，使用上面代碼2的位與運算來代替模運算。這個方法非常巧妙，它通過 “(table.length -1) & h” 來得到該對象的索引位置，這個優化是基于以下公式：x mod 2^n = x & (2^n - 1)。我們知道HashMap底層數組的長度總是2的n次方，并且取模運算為“h mod table.length”，對應上面的公式，可以得到該運算等同于“h & (table.length - 1)”。這是HashMap在速度上的優化，因為&比%具有更高的效率。
在JDK1.8的實現中，還優化了高位運算的算法，將hashCode的高16位與hashCode進行異或運算，主要是為了在table的length較小的時候，讓高位也參與運算，并且不會有太大的開銷。
感謝各位的閱讀！關于“JDK 1.8中HashMap數據結構的示例分析”這篇文章就分享到這里了，希望以上內容可以對大家有一定的幫助，讓大家可以學到更多知識，如果覺得文章不錯，可以把它分享出去讓更多的人看到吧！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
