最近開始在閱讀一些源碼之類的學習茄茁，趁著周末魂贬，今天詳細學習了一些HashMap底層的知識，遂記錄下來裙顽。有很多理解或者描述不當之處付燥，望請指正。
一愈犹、數(shù)據(jù)底層結(jié)構(gòu)圖
首先放一張HashMap底層結(jié)構(gòu)圖键科，由于現(xiàn)在JDK幾乎都用8及以上了，因此本文記錄的都是基于JDK8的HashMap漩怎。
在JDK8以后勋颖，HashMap底層采用數(shù)組+鏈表+紅黑樹的形式來進行存儲。
HashMap底層用一個數(shù)組來存放節(jié)點勋锤，節(jié)點在數(shù)組中的位置是由一個特殊的算法計算出來的（下文會提到）授帕。如果兩個節(jié)點計算出來的hash值相同核无，那么就將新的節(jié)點以鏈表的形式宵呛，連接在已存在的節(jié)點的后面油猫。如果同一位置的節(jié)點數(shù)超過8個，那么會將鏈表改成紅黑樹的形式進行存儲谈宛。
這樣說有點抽象次哈，結(jié)合源碼一起看吧。
二吆录、HashMap源碼解讀
首先我們來看HashMap中的基本單位窑滞，節(jié)點，包括鏈表節(jié)點和紅黑樹節(jié)點。
鏈表節(jié)點：
/**
* Basic hash bin node, used for most entries. (See below for
* TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
*/
//map內(nèi)的存儲單位哀卫，以節(jié)點方式存儲巨坊，有hash,key,value,nextNode四個屬性
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
//node的構(gòu)造方法
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; }
//重寫Node的hashCode方法，用默認的hashCode方法計算出key的hashCode聊训，
//再和value的hashCode進行異或操作作為node的hashCode
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
//重寫Node的equals方法
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;
}
}
每個節(jié)點都有hash,key,value,Node<K,V> next四個屬性抱究，hash是該節(jié)點的hash值恢氯，next是此節(jié)點的下一個節(jié)點带斑。hash是此節(jié)點的hash值。在這個內(nèi)部靜態(tài)類中勋拟，重寫了hashCode()和equals()方法勋磕。計算hash值的方法是用默認的hashCode方法計算出key的hashCode，再和value的hashCode進行異或操作作為node的hash碼敢靡。
樹節(jié)點的屬性：
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
}
每個樹節(jié)點有父節(jié)點挂滓，左節(jié)點，右節(jié)點等屬性啸胧。構(gòu)造器則是和Node一樣赶站，需要hash,key,value,next等參數(shù)。
接下來看HashMap的插入方法纺念。
public V put(K key, V value) {
//直接調(diào)用putVal方法
return putVal(hash(key), key, value, false, true);
}
底層是通過putVal()方法進行插值贝椿，繼續(xù)看putVal()方法，打了很多注釋陷谱，應該看得懂～
屬性說明：
table:Node<K,V>[]烙博，底層存儲節(jié)點的數(shù)組
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//如果當前存node的數(shù)組tab是空的
if ((tab = table) == null || (n = tab.length) == 0)
//調(diào)用resize()方法對tab進行擴容，把長度返回給n
n = (tab = resize()).length;
//計算新的節(jié)點在table中的位置烟逊，算法是用數(shù)組長度n-1來和哈希進行與運算（目前還不懂這個算法有啥好處）
//如果那個位置是空的渣窜，就直接插入新的node
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
//如果那個位置有節(jié)點了
else {
Node<K,V> e; K k;
//p代表計算出來新節(jié)點應該存放位置的節(jié)點
//如果需要添加的node的key已經(jīng)存在了
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
//把p的值賦給e，也就是直接把table[i]的值給新插入的元素宪躯，在后面會替換掉value
e = p;
//如果key不存在的情況
//先判斷p是不是樹節(jié)點
else if (p instanceof TreeNode)
//是樹節(jié)點的話乔宿，用傳入的參數(shù)，插入一個新節(jié)點访雪，并賦值給e
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
//是鏈表節(jié)點的話
else {
for (int binCount = 0; ; ++binCount) {
//如果table[i]的下一個節(jié)點是空的
if ((e = p.next) == null) {
//把table[i]的下一個節(jié)點設置為要插入的節(jié)點
p.next = newNode(hash, key, value, null);
//如果table[i]那個位置上已經(jīng)存在的node數(shù)量大于等7了详瑞，說明鏈表要轉(zhuǎn)換成紅黑樹了
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
//替換鏈表結(jié)構(gòu)改為紅黑樹結(jié)構(gòu)
treeifyBin(tab, hash);
break;
}
//如果key已經(jīng)存在了，就直接把e的值賦值給table[i]上那個節(jié)點
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//如果map中已經(jīng)存在要新添加的節(jié)點的key了
if (e != null) { // existing mapping for key
V oldValue = e.value;
//判斷已存在的key對應的value是否為空冬阳，是的話直接覆蓋值
if (!onlyIfAbsent || oldValue == null)
e.value = value;
//回調(diào)方法
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
//如果數(shù)組中的節(jié)點數(shù)大于閥值了蛤虐，擴容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
在上面源碼中，計算節(jié)點在table中位置的算法是i = (n - 1) & hash]肝陪，在底層源碼中驳庭，定義的HashMap的容量只能是2的次冪數(shù)，如果不是，也算強制通過resize()轉(zhuǎn)換成2的高次冪饲常。
/**
* The default initial capacity - MUST be a power of two.
*/
//初始化容量蹲堂，16，必須是2的次冪
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
在n-1后贝淤，這個數(shù)的二進制數(shù)就全是1了柒竞，再和hash值進行&操作，這操作好像很騷播聪，我還沒能get到它具體騷在哪里朽基，只是覺得這種方式運算起來好像很簡單，計算出來的位置离陶，直接能夠截取hash值(n-1)對應的二進制位數(shù)長度的低位稼虎。
結(jié)合源碼和上面的結(jié)構(gòu)圖，應該能對HashMap結(jié)構(gòu)以及JDK是如何實現(xiàn)它的有了一點點了解～
無奈我語言表達能力過差招刨，不能像其他博主一樣很生動形象的將自己意思表達出來霎俩，只能上圖和源碼了emmmm希望今年能多寫點學習筆記，把自己學習到的知識記錄分享沉眶。
小感想
通過閱讀源碼打却，能夠稍微得了解一些大觸們的編程世界，除了感嘆那些精巧的算法和設計谎倔，源碼里有很多值得學習的思想柳击。
最后...一句雞湯，只有努力永遠不會辜負你传藏。
