目錄

• 概述
• 內(nèi)部字段及構(gòu)造方法
• 哈希值與索引計(jì)算
• 存儲(chǔ)元素
• 擴(kuò)容
• 刪除元素
• 查找元素
• 總結(jié)

概述

??在上文我們基于JDK7分析了HashMap的實(shí)現(xiàn)源碼，介紹了HashMap的加載因子loadFactor、閾值threshold概念以及增刪元素的機(jī)制。JDK8在JDK7的基礎(chǔ)上對(duì)HashMap的實(shí)現(xiàn)進(jìn)行了進(jìn)一步的優(yōu)化，最主要的改變就是新增了紅黑樹作為底層數(shù)據(jù)結(jié)構(gòu)。

HashMap數(shù)據(jù)結(jié)構(gòu)

??首先我們回憶一下JDK7中HashMap的實(shí)現(xiàn)，HashMap是以數(shù)組和單鏈表構(gòu)成，當(dāng)出現(xiàn)哈希沖突時(shí)，沖突的元素在桶中依次形成單鏈表，數(shù)據(jù)結(jié)構(gòu)如下：

JDK7中哈希沖突時(shí)使用鏈表存儲(chǔ)沖突元素，當(dāng)出現(xiàn)大量哈希沖突元素，那么在單鏈表查找一個(gè)元素的復(fù)雜度為O(N)，為了優(yōu)化出現(xiàn)大量哈希沖突元素的查找問題，JDK8中規(guī)定：當(dāng)單鏈表存儲(chǔ)元素個(gè)數(shù)超過閾值TREEIFY_THRESHOLD（8）時(shí)，將單鏈表轉(zhuǎn)換為紅黑樹，紅黑樹查找元素復(fù)雜度為O(logN),提高了查找效率，JDK8中HashMap的存儲(chǔ)結(jié)構(gòu)：

內(nèi)部字段及構(gòu)造方法

Node類

??使用Node類存儲(chǔ)鍵值對(duì)元素。

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;}}

TreeNode類

??TreeNode是構(gòu)成紅黑樹的基本元素。

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;//構(gòu)造一個(gè)樹結(jié)點(diǎn)TreeNode(int hash, K key, V val, Node<K,V> next) {super(hash, key, val, next);}}

內(nèi)部字段

//數(shù)組初始容量，為16static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16//數(shù)組最大容量static final int MAXIMUM_CAPACITY = 1 << 30;//默認(rèn)加載因子static final float DEFAULT_LOAD_FACTOR = 0.75f;//單鏈表轉(zhuǎn)化為紅黑樹的閾值static final int TREEIFY_THRESHOLD = 8;/*** 主要用于resize()擴(kuò)容過程中, 當(dāng)對(duì)原來的紅黑樹根據(jù)hash值拆分成兩條鏈表后,* 如果拆分后的鏈表長(zhǎng)度 <=UNTREEIFY_THRESHOLD, 那么就采用鏈表形式管理hash值沖突;* 否則, 采用紅黑樹管理hash值沖突.*/static final int UNTREEIFY_THRESHOLD = 6;/*** 當(dāng)集合中的容量大于這個(gè)值時(shí)，表中的桶才能進(jìn)行樹化 ，否則桶內(nèi)元素太多時(shí)會(huì)擴(kuò)容，* 而不是樹形化 為了避免進(jìn)行擴(kuò)容、樹形化選擇的沖突，這個(gè)值不能小于 4 * TREEIFY_THRESHOLD*/static final int MIN_TREEIFY_CAPACITY = 64;//第一次使用是初始化，數(shù)組長(zhǎng)度總是2的冪次transient Node<K,V>[] table;transient int size;int threshold;final float loadFactor;

構(gòu)造方法

public HashMap(int initialCapacity, float loadFactor) {//檢查參數(shù)合法性if (initialCapacity < 0)throw new IllegalArgumentException("Illegal initial capacity: " +initialCapacity);if (initialCapacity > MAXIMUM_CAPACITY)initialCapacity = MAXIMUM_CAPACITY;if (loadFactor <= 0 || Float.isNaN(loadFactor))throw new IllegalArgumentException("Illegal load factor: " +loadFactor);this.loadFactor = loadFactor;//這里只是初始化，最終賦值在resize方法里this.threshold = tableSizeFor(initialCapacity);}

哈希值與索引計(jì)算

hash(Object key)

??在JDK1.8的實(shí)現(xiàn)中，優(yōu)化了高位運(yùn)算的算法，通過hashCode()的高16位異或低16位實(shí)現(xiàn)的：(h = k.hashCode()) ^ (h >>> 16)，主要是從速度、功效、質(zhì)量來考慮的，這么做可以在數(shù)組table的length比較小的時(shí)候，也能保證考慮到高低Bit都參與到Hash的計(jì)算中，同時(shí)不會(huì)有太大的開銷。
??這個(gè)方法非常巧妙，它通過h & (table.length -1)來得到該對(duì)象的保存位，而HashMap底層數(shù)組的長(zhǎng)度總是2的n次方，這是HashMap在速度上的優(yōu)化。當(dāng)length總是2的n次方時(shí)，h& (length-1)運(yùn)算等價(jià)于對(duì)length取模，也就是h%length，但是&比%具有更高的效率。計(jì)算過程如下圖：

static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}//jdk1.7的源碼，jdk1.8沒有這個(gè)方法，但是實(shí)現(xiàn)原理一樣的//根據(jù)hash值和table數(shù)組長(zhǎng)度計(jì)算鍵值對(duì)存儲(chǔ)位置的索引static int indexFor(int h, int length) { return h & (length-1); //第三步 取模運(yùn)算}

存儲(chǔ)元素

put(K key, V value)

public V put(K key, V value) {return putVal(hash(key), key, value, false, true);}/*** Implements Map.put and related methods* @param hash hash for key* @param key the key 鍵* @param value the value to put 值* @param onlyIfAbsent if true, don't change existing value 表示不要更改現(xiàn)有值* @param evict if false, the table is in creation mode. false表示table處于創(chuàng)建模式* @return previous value, or null if none*/final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {//使用局部變量tab而不是類成員，方法棧上訪問更快Node<K,V>[] tab; Node<K,V> p; int n, i;//如果table為null或者長(zhǎng)度為0，則進(jìn)行初始化if ((tab = table) == null || (n = tab.length) == 0)//擴(kuò)容n = (tab = resize()).length;//散列到對(duì)應(yīng)的桶中，如果桶為空則直接放到桶中即可if ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null);else {//else分支表示散列到的桶中元素不為空Node<K,V> e; K k;//桶中鏈表的根節(jié)點(diǎn)的key就是要插入的鍵值對(duì)的keyif (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))e = p;//如果是紅黑樹，插入到紅黑樹中else if (p instanceof TreeNode)e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);//插入到單鏈表中else {//遍歷鏈表，并統(tǒng)計(jì)桶中鍵值對(duì)元素?cái)?shù)量for (int binCount = 0; ; ++binCount) {//該Key在鏈表中不存在，插入末尾 此時(shí)e為nullif ((e = p.next) == null) {p.next = newNode(hash, key, value, null);//單鏈表元素個(gè)數(shù)超過TREEIFY_THRESHOLD，樹化if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);break;//注意從這里break出來的e為null}//該Key已經(jīng)在鏈表中if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))//注意從這里break出來的e不為nullbreak;p = e;}}// e != null，說明該Key已經(jīng)在存在于HashMap中,在這個(gè)桶中if (e != null) { // existing mapping for keyV oldValue = e.value;//根據(jù)onlyIfAbsent和oldif (!onlyIfAbsent || oldValue == null)e.value = value;afterNodeAccess(e);return oldValue;}}++modCount;//超過閾值，就進(jìn)行擴(kuò)容if (++size > threshold)resize();afterNodeInsertion(evict);return null;}

擴(kuò)容

resize( )

??resize方法相對(duì)比較復(fù)雜，但是有比較巧妙，因?yàn)橐紤]數(shù)據(jù)結(jié)構(gòu)的不同怎么把元素從老的table中放到擴(kuò)容后的table中。主要的思路也就是兩步：先根據(jù)老的table的長(zhǎng)度決定擴(kuò)容后table的長(zhǎng)度，以及新的閾值threshold；在桶中數(shù)據(jù)不為空的情況下，把桶中的數(shù)據(jù)遷移到新的table數(shù)組中，這里就要考慮在桶中只有一個(gè)元素（沒有發(fā)生哈希沖突）、桶中元素以單鏈表形式存儲(chǔ)（發(fā)生哈希沖突但是不超過8個(gè)）、桶中元素以紅黑樹形式存儲(chǔ)（哈希沖突元素個(gè)數(shù)超過8個(gè)）。只有一個(gè)元素，直接根據(jù)哈希值和新的table數(shù)組長(zhǎng)度計(jì)算出新的索引，紅黑樹調(diào)用split方法，這里我們重點(diǎn)分析一下怎么把桶中的單鏈表遷移到新桶中，從而體會(huì)到JDK的巧妙設(shè)計(jì)。

??resize的擴(kuò)容策略是每次擴(kuò)容2倍（newThr = oldThr << 1），為了把單鏈表元素遷移到新的桶中，并不是向JDK7那樣直接根據(jù)哈希值散列得到新的索引值，經(jīng)過觀測(cè)可以發(fā)現(xiàn)，我們使用的是2次冪的擴(kuò)展(指長(zhǎng)度擴(kuò)為原來2倍)，所以，元素的位置要么是在原位置，要么是在原位置再移動(dòng)2次冪的位置。看下圖可以明白這句話的意思，n為table的長(zhǎng)度，圖（a）表示擴(kuò)容前的key1和key2兩種key確定索引位置的示例，圖（b）表示擴(kuò)容后key1和key2兩種key確定索引位置的示例，其中hash1是key1對(duì)應(yīng)的哈希與高位運(yùn)算結(jié)果。

元素在重新計(jì)算hash之后，因?yàn)閚變?yōu)?倍，那么n-1的mask范圍在高位多1bit(紅色)，因此新的index就會(huì)發(fā)生這樣的變化：

因此，我們?cè)跀U(kuò)充HashMap的時(shí)候，不需要像JDK1.7的實(shí)現(xiàn)那樣重新計(jì)算hash，只需要看看原來的hash值新增的那個(gè)bit是1還是0就好了，是0的話索引沒變，是1的話索引變成“原索引+oldCap”

final Node<K,V>[] resize() {//使用oldTab指向原來的hash表，通常方法內(nèi)都使用局部變量，局部變量在方法棧上，而對(duì)象的成員在堆上//方法棧的訪問比堆更高效//記錄擴(kuò)容前table數(shù)組，閾值，長(zhǎng)度Node<K,V>[] oldTab = table;int oldCap = (oldTab == null) ? 0 : oldTab.length;int oldThr = threshold;int newCap, newThr = 0;if (oldCap > 0) {//原來的容量已經(jīng)很大了，超過了MAXIMUM_CAPACITY無法再調(diào)整if (oldCap >= MAXIMUM_CAPACITY) {threshold = Integer.MAX_VALUE;return oldTab;}//容量加倍else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY)newThr = oldThr << 1; // double threshold}//oldCap < 0,oldThr > 0,table空間尚未分配，初始化分配空間//舊閥值大于0，則將新容量直接等于就閥值else if (oldThr > 0) // initial capacity was placed in thresholdnewCap = oldThr;//閥值等于0，oldCap也等于0（集合未進(jìn)行初始化）else { // zero initial threshold signifies using defaultsnewCap = DEFAULT_INITIAL_CAPACITY;//threshhold=capacity*load_factornewThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}//計(jì)算新的閥值上限if (newThr == 0) {float ft = (float)newCap * loadFactor;newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);}threshold = newThr;@SuppressWarnings({"rawtypes","unchecked"})Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];table = newTab;//原來的表中有內(nèi)容，表明這是一次擴(kuò)容，需要將Entry散列到新的位置if (oldTab != null) {for (int j = 0; j < oldCap; ++j) {//遍歷所有binNode<K,V> e;if ((e = oldTab[j]) != null) {//舊桶中元素置為null，方便GColdTab[j] = null;//該桶中只有一個(gè)節(jié)點(diǎn)，直接散列到新的位置if (e.next == null)newTab[e.hash & (newCap - 1)] = e;else if (e instanceof TreeNode)//該桶中是一顆紅黑樹，通過紅黑樹的split方法處理//待會(huì)再看split方法((TreeNode<K,V>)e).split(this, newTab, j, oldCap);else { // preserve orderNode<K,V> loHead = null, loTail = null;Node<K,V> hiHead = null, hiTail = null;Node<K,V> next;do {next = e.next;// 與oldCap按位相與，判斷結(jié)果是一還是零if ((e.hash & oldCap) == 0) {if (loTail == null)loHead = e;elseloTail.next = e;loTail = e;}else {if (hiTail == null)hiHead = e;elsehiTail.next = e;hiTail = e;}} while ((e = next) != null);//原索引if (loTail != null) {loTail.next = null;newTab[j] = loHead;}//原索引+oldCapif (hiTail != null) {hiTail.next = null;newTab[j + oldCap] = hiHead;}}}}}return newTab;}

刪除元素

remove(Object key)

public V remove(Object key) {Node<K,V> e;return (e = removeNode(hash(key), key, null, false, true)) == null ?null : e.value;}final Node<K,V> removeNode(int hash, Object key, Object value,boolean matchValue, boolean movable) {Node<K,V>[] tab; Node<K,V> p; int n, index;//tab不為空，p指向根據(jù)hash散列到桶中第一個(gè)節(jié)點(diǎn)if ((tab = table) != null && (n = tab.length) > 0 &&(p = tab[index = (n - 1) & hash]) != null) {Node<K,V> node = null, e; K k; V v;//第一個(gè)節(jié)點(diǎn)就命中if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))node = p;else if ((e = p.next) != null) {//在紅黑樹中查找目標(biāo)節(jié)點(diǎn)if (p instanceof TreeNode)node = ((TreeNode<K,V>)p).getTreeNode(hash, key);//在單鏈表中查找目標(biāo)節(jié)點(diǎn)else {do {if (e.hash == hash &&((k = e.key) == key ||(key != null && key.equals(k)))) {node = e;break;}p = e;} while ((e = e.next) != null);}}//找到目標(biāo)節(jié)點(diǎn)且符合移除的條件if (node != null && (!matchValue || (v = node.value) == value ||(value != null && value.equals(v)))) {//紅黑樹移除if (node instanceof TreeNode)((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);//單鏈表移除//移除的節(jié)點(diǎn)是單鏈表首節(jié)點(diǎn)else if (node == p)tab[index] = node.next;//移除的節(jié)點(diǎn)不是單鏈表首節(jié)點(diǎn)elsep.next = node.next;++modCount;--size;afterNodeRemoval(node);return node;}}return null;}

查找元素

get(Object key)

public V get(Object key) {Node<K,V> e;return (e = getNode(hash(key), key)) == null ? null : 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 ((tab = table) != null && (n = tab.length) > 0 &&(first = tab[(n - 1) & hash]) != null) {//hash值對(duì)應(yīng)的桶中第一個(gè)元素//第一個(gè)元素符合查找條件if (first.hash == hash && // always check first node((k = first.key) == key || (key != null && key.equals(k))))return first;if ((e = first.next) != null) {//紅黑樹查找if (first instanceof TreeNode)return ((TreeNode<K,V>)first).getTreeNode(hash, key);do {//單鏈表查找if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))return e;} while ((e = e.next) != null);}}return null;}

總結(jié)

??JDK8使用了紅黑樹優(yōu)化了HashMap的性能，即使發(fā)生了大量的哈希碰撞也能夠以O(shè)(logN)查找到元素，不會(huì)影響到服務(wù)器的性能。

轉(zhuǎn)載于:https://www.cnblogs.com/rain4j/p/9536570.html

新人創(chuàng)作打卡挑戰(zhàn)賽發(fā)博客就能抽獎(jiǎng)！定制產(chǎn)品紅包拿不停！

總結(jié)

以上是生活随笔為你收集整理的JDK源码分析(三)——HashMap 下（基于JDK8）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。