摘要：當鏈表長度即將超過閥值，會把鏈表轉化為紅黑樹。然后再判斷是鏈表還是紅黑樹如果值相同，并且相同表示數(shù)組中第一個元素即為相同的將數(shù)組中第一個元素賦值給如果當前元素類型為表示為紅黑樹，返回待存放的。
前提：學習HashMap的底層代碼之前，首先要對數(shù)據(jù)結構要個大致的了解。其中重點了解數(shù)組，鏈表，樹的概念和用法。
一.圖示分析HashMap的結構
(1)圖示為JDK1.8之前的HashMap結構。數(shù)組+鏈表，數(shù)組中的元素為鏈表的頭節(jié)點。如果不同的key對應相同的hash值，則會在頭節(jié)點后形成鏈表。
通過代碼的實現(xiàn)，我們可以分析出：如果在儲存數(shù)據(jù)時，某一個鏈表過長，則會影響查詢性能。（下面會分析put和get方法，解釋鏈表過長如何影響性能）
(2)JDK1.8中進行了優(yōu)化。當鏈表長度即將超過閥值（TREEIFY_THRESHOLD），會把鏈表轉化為紅黑樹。底層實現(xiàn)變?yōu)閿?shù)組+鏈表+紅黑樹
二.通過代碼分析底層結構中元素的結構和原理
（1）數(shù)組和鏈表中的每個元素都是Node對象，它是HashMap的一個內部類并且實現(xiàn)了Map.Entry。其中包含了幾個重要屬性，int hash; K key; V value; Node next;
static class Node implements Map.Entry {
final int hash;//通過key的hashCode方法獲取的hash值。hash值相同的key會在數(shù)組中找到同一個位置
final K key;
V value;
Node next;//指向下一個節(jié)點，儲存了下一個節(jié)點的地址
Node(int hash, K key, V value, Node 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;
}
}
（2）當鏈表長度達到閥值，鏈表轉化為紅黑樹。此時數(shù)組和紅黑樹中的元素是TreeNode
static final class TreeNode extends LinkedHashMap.Entry {
TreeNode parent; // 父節(jié)點
TreeNode left; //左子樹
TreeNode right;//右子樹
TreeNode prev; // needed to unlink next upon deletion
boolean red; //顏色屬性
TreeNode(int hash, K key, V val, Node next) {
super(hash, key, val, next);
}
}
（3）HashMap中幾個常用的屬性和構造方法
public class HashMap extends AbstractMap implements Map, Cloneable, Serializable {
// 序列號
private static final long serialVersionUID = 362498820763181265L;
// 默認的初始容量是16，通過移位運算獲得結果。在計算機底層位運算速度最快
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// 最大容量 2的30次方
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默認的加載因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 鏈表轉紅黑樹的閥值
static final int TREEIFY_THRESHOLD = 8;
// 擴容時紅黑樹轉鏈表的閥值
static final int UNTREEIFY_THRESHOLD = 6;
// 鏈表轉化為紅黑樹對應的table的最小值
static final int MIN_TREEIFY_CAPACITY = 64;
// 存儲節(jié)點的數(shù)組，一定是2的冪次方
transient Node[] table;
//
transient Set> entrySet;
// 數(shù)組中元素的個數(shù)，注意這個不是數(shù)組的長度。
transient int size;
// 修改HashMap的次數(shù)
transient int modCount;
// 閥值，當數(shù)組中的元素大于threshold時HashMap進行擴容 threshold = （數(shù)組長度）capacity * loadFactor
int threshold;
// 填充因子
final float loadFactor;
//無參構造函數(shù)，比較常用
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
}
//一個參數(shù)，數(shù)組容量
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//兩個參數(shù)，數(shù)組容量和加載因子
public HashMap(int initialCapacity, float loadFactor) {
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;
//因為我們的入?yún)⒅付藬?shù)組大小，但是傳入的值可能不滿足HashMap要求。
//因此HashMap使用tableSizeFor保證數(shù)組大小一定是2的n次冪
this.threshold = tableSizeFor(initialCapacity);
}
/**
此方法的目的是：保證有參構造傳入的初始化數(shù)組長度是>=cap的最小2的冪次方。
對n不斷的無符號右移并且位或運算，可以將n從最高位為1開始的所有右側位數(shù)變成1，
最后n+1即成為大于cap的最小2的冪次方。
第一行 n=cap-1 是為了保證如果cap本身就是2^n，那么結果也將是其本身
*/
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
//傳入一個HashMap實例
public HashMap(Map m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
//如果傳入的HashMap中有元素，遍歷它并且把其中的元素put到當前HashMap中
final void putMapEntries(Map m, boolean evict) {
int s = m.size();
if (s > 0) {
if (table == null) { //當前數(shù)組為空
float ft = ((float)s / loadFactor) + 1.0F;
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
if (t > threshold)
threshold = tableSizeFor(t);//計算數(shù)組長度，并且保證長度是2的冪次方
}
else if (s > threshold)
resize();
for (Map.Entry e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict);
}
}
}
}
（4）put方法解析
/**如果key等于null就返回0，因此key為null時的數(shù)據(jù)存儲在數(shù)組中的第一個位置
*如果key不為null，將key的hashCode值賦值給h。然后將h無符號位移16位后再和該key的hashCode值進行異或
*作用：將hashCode的高16位和低16位進行異或，混合hashCode的高位和低位。以此加大低位的隨機性。
*當在計算key的位置時，(n - 1) & hash對數(shù)組長度取模，如果只取低位會造成大量碰撞。所以進行高低位異或。
*/
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/*當多個key的hash值相同時，會形成鏈表。如果此時又在該鏈表上插入一個元素，就要遍歷整個鏈表對比是否有相同的key，如果有則直接
*替換，如果沒有找到鏈表尾部，插入新元素。因此在JDK1.7中鏈表過長，引起效率低下
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
//定義變量
Node[] tab; Node p; int n, i;
//將table數(shù)組賦值給tab，將數(shù)組長度賦值給n。判斷當前map中的table數(shù)組是否為空(第一次肯定為空)
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;//將擴容后的數(shù)組賦值給tab，然后獲取數(shù)組長度賦值給n
if ((p = tab[i = (n - 1) & hash]) == null)//計算key在數(shù)組中的位置，然后判斷該位置是否為null并賦值給p
tab[i] = newNode(hash, key, value, null);//該位置沒有元素，直接創(chuàng)建一個節(jié)點放入
else {//進入下面代碼，表示該位置有元素。然后再判斷是鏈表還是紅黑樹
Node e; K k;
//如果hash值相同，并且key相同表示數(shù)組中第一個元素即為相同的key
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
e = p;將數(shù)組中第一個元素賦值給e
else if (p instanceof TreeNode)//如果當前元素類型為TreeNode表示為紅黑樹，putTreeVal返回待存放的Node。
e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value); e可能為null
else {//鏈表結構，遍歷鏈表找到插入的位置
for (int binCount = 0; ; ++binCount) {
//遍歷至鏈表尾部，如果沒有相同的key，則插入尾部一個節(jié)點
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//插入后，如果鏈表長度大于等于樹化的閥值，將鏈表轉化為紅黑樹
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//鏈表中找到相同的key直接跳出循環(huán)
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // e不為null，代表存在相同的key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;//將新值直接覆蓋老值
afterNodeAccess(e);//一個空方法
return oldValue;//返回老值
}
}
//代碼走到這里說明，數(shù)組中新增了一個Node
++modCount;//修改HashMap的次數(shù)
if (++size > threshold)//如果增加節(jié)點后，數(shù)組中元素的個數(shù)大于了擴容的閥值，則進行擴容
resize();
afterNodeInsertion(evict);//一個空方法
return null;//第一次增加節(jié)點，返回null
}
（5）get方法解析
//調用getNode方法返回一個Node節(jié)點并賦值給e。如果e為null，則返回null。否則返回Node節(jié)點中的value屬性
public V get(Object key) {
Node e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
//hash(key)計算獲取hash，即key位于數(shù)組中的位置
final Node getNode(int hash, Object key) {
Node[] tab; Node first, e; int n; K k;
//取值前保證當前map中的table不為null，并且該key所在數(shù)組中的Node不為null，如果不滿足條件直接返回null
if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k))))//先檢查第一個Node
return first;//如果第一個Node滿足條件，證明這個就是我們要找的元素，直接返回
if ((e = first.next) != null) {//上面條件不滿足，則從紅黑樹，鏈表中找元素
if (first instanceof TreeNode)//如果該節(jié)點屬于TreeNode，則從紅黑樹中查找
return ((TreeNode)first).getTreeNode(hash, key);
do {//遍歷鏈表找到相同的key則返回元素，否則跳出循環(huán)，返回null
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
（6）resize方法解析
//resize（）是HashMap實現(xiàn)擴容機制的核心。在put方法中出現(xiàn)兩次，第一次初始化數(shù)組時，第二次數(shù)組元素達到閥值時。
//將原來數(shù)組中的元素重新hash到新的位置。新的位置和原位置相同，或者是原來位置的兩倍
final Node[] resize() {
Node[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
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
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
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[] newTab = (Node[])new Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode)e).split(this, newTab, j, oldCap);
else { // preserve order
Node loHead = null, loTail = null;
Node hiHead = null, hiTail = null;
Node next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
未完待續(xù)
文章版權歸作者所有，未經(jīng)允許請勿轉載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉載請注明本文地址：http://systransis.cn/yun/75134.html
