底層源碼分析-HashMap源碼詳解
- HashMap JDK7 與JDK8的差異
- HashMap put()詳解
- HashMap resize()詳解
- HashMap域
- HashMap重要方法
-
- put(K key, V value)
- treeifyBin()樹化
- resize() 擴容
- split() 擴容樹的分發方式
-
HashMap JDK7 與JDK8的差異
資料結構的改變
- JDK8新增了紅黑樹的資料結構（解決Hash沖突連結清單過長）
插入方法中的改變
- JDK7中連結清單的插入是用的頭插法，而JDK8中則改為了尾插法。是為了擴容的資料轉移
- JDK8中的因為使用了紅黑樹保證了插入和查詢了效率，是以實際上JDK8中的Hash算法實作的複雜度降低了
- JDK 8的hash函數比JDK 7的簡單減少CPU的損耗
擴容中的改變
- JDK8中數組擴容的條件也發了變化，**隻會判斷是否目前元素個數是否查過了門檻值，**而不再判斷目前put進來的元素對應的數組下标位置是否有值。還有一個就是樹化時候低于64 個的時候。
- JDK 7中擴容是一個一個轉移 而JDK8 中是先周遊連結清單 分成兩個直接去轉移
- 擴容的過程中JDK7中有可能會重新對key進行哈希（重新Hash跟哈希種子有關系），而JDK8中沒有這部分邏輯
HashMap put()詳解
- 通過key計算出一個hashcode ，如果table=null，建立table。
- 通過hashcode與“與操作”計算出一個數組下标 注意:這裡需要數組長度是2的幂次。
- 判斷數組下标對應的位置，是不是空，如果是空則把new一個entry直接存在該數組位置。
- 如果該下标對應的位置不為空，則需要把new一個entry插入到連結清單中(JDK 8 是插傳入連結表或者樹)。
- 并且還需要判斷該連結清單中是否存在相同的key，如果存在，則更新value，并且傳回oldValue。
- 如果是JDK7，則使用頭插法
- 如果是JDK8，則會周遊連結清單，并且在周遊連結清單的過程中，統計目前連結清單的元素個數，如果超過8個，則先把連結清單轉變為紅黑樹.(變為紅黑樹還有另一個條件:看數組長度是不是達到64 )
- 如果添加成功，size大于加載因子，擴容
HashMap resize()詳解
- HashMap的擴容指的就是數組的擴容， 因為數組占用的是連續記憶體空間，是以數組的擴容其實隻能新開一個新的數組，然後把老數組上的元素轉移到新數組上來，這樣才是數組的擴容
- 在HashMap中也是一樣，先建立一個2倍數組大小的數組
- 然後周遊老數組上的每一個位置，如果這個位置上是一個連結清單，就把這個連結清單上的元素轉移到新數組上去
- 在這個過程中就需要周遊連結清單，當然jdk7，和jdk8在這個實作時是有不一樣的，jdk7就是簡單的周遊連結清單上的每一個元素，然後按每個元素的hashcode結合新數組的長度重新計算得出一個下标，而重新得到的這個數組下标很可能和之前的數組下标是不一樣的，這樣子就達到了一種效果，就是擴容之後，某個連結清單會變短，這也就達到了擴容的目的，縮短連結清單長度，提高了查詢效率
- 而在jdk8中，因為涉及到紅黑樹，這個其實比較複雜，jdk8中其實還會用到一個雙向連結清單來維護紅黑樹中的元素，是以jdk8中在轉移某個位置上的元素時，會去判斷如果這個位置是一個紅黑樹，那麼會周遊該位置的雙向連結清單，周遊雙向連結清單統計哪些元素在擴容完之後還是原位置，哪些元素在擴容之後在新位置，這樣周遊完雙向連結清單後，就會得到兩個子連結清單，一個放在原下标位置，一個放在新下标位置，如果原下标位置或新下标位置沒有元素，則紅黑樹不用拆分，否則判斷這兩個子連結清單的長度，如果不小于6，則轉成紅黑樹放到對應的位置，否則轉化為單向連結清單放到對應的位置。
- 元素轉移完了之後，在把新數組對象指派給HashMap的table屬性，老數組會被回收到。
HashMap域
- DEFAULT_INITIAL_CAPACITY = 1 << 4; Hash表預設初始容量
- MAXIMUM_CAPACITY = 1 << 30; 最大Hash表容量
- DEFAULT_LOAD_FACTOR = 0.75f；預設加載因子
- TREEIFY_THRESHOLD = 8；連結清單轉紅黑樹門檻值
- UNTREEIFY_THRESHOLD = 6；紅黑樹轉連結清單門檻值
- MIN_TREEIFY_CAPACITY = 64；連結清單轉紅黑樹時hash表最小容量門檻值，達不到優先擴容。
HashMap重要方法
put(K key, V value)
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//判斷是否為空 如果是則new出table //表的懶加載
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//如果找到的位置是空那麼直接建立
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
//如果不是空那麼 有兩種資料結構,一種是連結清單另一種是紅黑樹
Node<K,V> e; K k;
if (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 {
for (int binCount = 0; ; ++binCount) {
//如果到了尾節點
if ((e = p.next) == null) {
//尾插法 ()
p.next = newNode(hash, key, value, null);
//如果長度大于8 就去 變紅黑樹
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//如果已經存有這個key 退出循環
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//e != null 的意思就是沒有周遊到最後就退出循環，也就是有一樣的值 就覆寫并且傳回 老數字
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
//控制通路順序的函數
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
//控制插入順序的函數
afterNodeInsertion(evict);
return null;
}
treeifyBin()樹化
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
//如果目前Hash表容量小于64 會選擇擴容而不是紅黑樹
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
//把原來的連結清單變為一條雙向連結清單
<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
// 将這個連結清單樹化
hd.treeify(tab);
}
}
resize() 擴容
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
//記錄老Hash表大小，和 加載因子
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
//若老Hash表不是Null
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<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
//之前是初始化新table的 屬性
table = newTab;
if (oldTab != null) {
//循環周遊Hash的table
for (int j = 0; j < oldCap; ++j) {
Node<K,V> 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<K,V>)e).split(this, newTab, j, oldCap);
//如果是連結清單則
else {
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
//周遊 連結清單,因為擴容後原來的連結清單會因為hash不一樣被拆成2個是以 先成兩條鍊再去添加到新table中去
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;
}
split() 擴容樹的分發方式
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
TreeNode<K,V> b = this;
// Relink into lo and hi lists, preserving order
TreeNode<K,V> loHead = null, loTail = null;
TreeNode<K,V> hiHead = null, hiTail = null;
int lc = 0, hc = 0;
//因為我們的書也還是雙向連結清單，循環分兩連結清單
for (TreeNode<K,V> e = b, next; e != null; e = next) {
next = (TreeNode<K,V>)e.next;
e.next = null;
if ((e.hash & bit) == 0) {
if ((e.prev = loTail) == null)
loHead = e;
else
loTail.next = e;
loTail = e;
++lc;
}
else {
if ((e.prev = hiTail) == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
++hc;
}
}
if (loHead != null) {
//如果小于等于6 那麼鍊化
if (lc <= UNTREEIFY_THRESHOLD)
tab[index] = loHead.untreeify(map);
else {
tab[index] = loHead;
//如果有一個是空的 就把另一個直接放入
if (hiHead != null) // (else is already treeified)
loHead.treeify(tab);
}
}
if (hiHead != null) {
if (hc <= UNTREEIFY_THRESHOLD)
tab[index + bit] = hiHead.untreeify(map);
else {
tab[index + bit] = hiHead;
if (loHead != null)
hiHead.treeify(tab);
}
}
}
三級目錄
![Java String.format方法的簡單使用[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)