概要
HashMap在JDK1.8之前的實現方式 數組+鏈表,但是在JDK1.8后對HashMap進行了底層優(yōu)化,改為了由 數組+鏈表+紅黑樹實現,主要的目的是提高查找效率乔询。
如圖所示：
| JDK版本 | 實現方式 | 節(jié)點數>=8 | 節(jié)點數<=6 |
|---|---|---|---|
| 1.8以前 | 數組+單向鏈表 | 數組+單向鏈表 | 數組+單向鏈表 |
| 1.8以后 | 數組+單向鏈表+紅黑樹 | 數組+紅黑樹 | 數組+單向鏈表 |
HashMap
1.繼承關系
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable
2.常量&構造方法
//這兩個是限定值 當節(jié)點數大于8時會轉為紅黑樹存儲
static final int TREEIFY_THRESHOLD = 8;
//當節(jié)點數小于6時會轉為單向鏈表存儲
static final int UNTREEIFY_THRESHOLD = 6;
//紅黑樹最小長度為 64
static final int MIN_TREEIFY_CAPACITY = 64;
//HashMap容量初始大小
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//HashMap容量極限
static final int MAXIMUM_CAPACITY = 1 << 30;
//負載因子默認大小
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//Node是Map.Entry接口的實現類
//在此存儲數據的Node數組容量是2次冪
//每一個Node本質都是一個單向鏈表
transient Node<K,V>[] table;
//HashMap大小,它代表HashMap保存的鍵值對的多少
transient int size;
//HashMap被改變的次數
transient int modCount;
//下一次HashMap擴容的大小
int threshold;
//存儲負載因子的常量
final float loadFactor;
//默認的構造函數
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
//指定容量大小
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//指定容量大小和負載因子大小
public HashMap(int initialCapacity, float loadFactor) {
//指定的容量大小不可以小于0,否則將拋出IllegalArgumentException異常
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
//判定指定的容量大小是否大于HashMap的容量極限
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
//指定的負載因子不可以小于0或為Null昂芜，若判定成立則拋出IllegalArgumentException異常
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
// 設置“HashMap閾值”侠讯，當HashMap中存儲數據的數量達到threshold時弯淘，就需要將HashMap的容量加倍祈纯。
this.threshold = tableSizeFor(initialCapacity);
}
//傳入一個Map集合,將Map集合中元素Map.Entry全部添加進HashMap實例中
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
//此構造方法主要實現了Map.putAll()
putMapEntries(m, false);
}
3.Node單向鏈表的實現
//實現了Map.Entry接口
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;
}
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;
}
//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;
}
}
4.TreeNode紅黑樹實現
static final class TreeNode<K,V> extends LinkedHashMap.LinkedHashMapEntry<K,V> {
TreeNode<K,V> parent; // 紅黑樹的根節(jié)點
TreeNode<K,V> left; //左樹
TreeNode<K,V> right; //右樹
TreeNode<K,V> prev; // 上一個幾點
boolean red; //是否是紅樹
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
/**
* 根節(jié)點的實現
*/
final TreeNode<K,V> root() {
for (TreeNode<K,V> r = this, p;;) {
if ((p = r.parent) == null)
return r;
r = p;
}
}
...
5.Hash的計算實現
//主要是將傳入的參數key本身的hashCode與h無符號右移16位進行二進制異或運算得出一個新的hash值
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
延伸講解
5.1.下面的做了一個例子講解,經過hash函數計算后得到的key的hash值
hash計算.png
5.2那為什么要這么做呢？直接通過key.hashCode()獲取hash不得了嗎?為什么在右移16位后進行異或運算寇荧？
答案 : 與HashMap的table數組下計算標有關系
我們在下面講解的put/get函數代碼塊中都出現了這樣一段代碼
//put函數代碼塊中
tab[i = (n - 1) & hash])
//get函數代碼塊中
tab[(n - 1) & hash])
tab下標計算h計算.png
這樣做的根本原因是當發(fā)生較大碰撞時也用樹形存儲降低了沖突。既減少了系統的開銷
6.HashMap.put的源碼實現
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
//HashMap.put的具體實現
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//判定table不為空并且table長度不可為0,否則將從resize函數中獲取
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//這樣寫法有點繞,其實這里就是通過索引獲取table數組中的一個元素看是否為Nul
if ((p = tab[i = (n - 1) & hash]) == null)
//若判斷成立,則New一個Node出來賦給table中指定索引下的這個元素
tab[i] = newNode(hash, key, value, null);
else { //若判斷不成立
Node<K,V> e; K k;
//對這個元素進行Hash和key值匹配
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode) //如果數組中德這個元素P是TreeNode類型
//判定成功則在紅黑樹中查找符合的條件的節(jié)點并返回此節(jié)點
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else { //若以上條件均判斷失敗执隧，則執(zhí)行以下代碼
//向Node單向鏈表中添加數據
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//若節(jié)點數大于等于8
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
//轉換為紅黑樹
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e; //p記錄下一個節(jié)點
}
}
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;
}
梳理以下HashMap.put函數的執(zhí)行過程
- 1.首先獲取Node數組table對象和長度揩抡，若table為null或長度為0，則調用resize()擴容方法獲取table最新對象镀琉，并通過此對象獲取長度大小
- 2.判定數組中指定索引下的節(jié)點是否為Null峦嗤，若為Null 則new出一個單向鏈表賦給table中索引下的這個節(jié)點
- 3.若判定不為Null,我們的判斷再做分支
-3.1 首先對hash和key進行匹配,若判定成功直接賦予e- 3.2 若匹配判定失敗,則進行類型匹配是否為TreeNode 若判定成功則在紅黑樹中查找符合條件的節(jié)點并將其回傳賦給e
- 3.3 若以上判定全部失敗則進行最后操作,向單向鏈表中添加數據若單向鏈表的長度大于等于8,則將其轉為紅黑樹保存，記錄下一個節(jié)點,對e進行判定若成功則返回舊值
- 4.最后判定數組大小需不需要擴容
7.HashMap.get的源碼實現
//這里直接調用getNode函數實現方法
public V get(Object key) {
Node<K,V> e;
//經過hash函數運算 獲取key的hash值
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;
//判定三個條件 table不為Null & table的長度大于0 & table指定的索引值不為Null
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//判定 匹配hash值 & 匹配key值 成功則返回 該值
if (first.hash == hash &&
((k = first.key) == key || (key != null && key.equals(k))))
return first;
//若 first節(jié)點的下一個節(jié)點不為Null
if ((e = first.next) != null) {
if (first instanceof TreeNode) //若first的類型為TreeNode 紅黑樹
//通過紅黑樹查找匹配值 并返回
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
//若上面判定不成功 則認為下一個節(jié)點為單向鏈表,通過循環(huán)匹配值
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
//匹配成功后返回該值
return e;
} while ((e = e.next) != null);
}
}
return null;
}
梳理以下HashMap.get函數的執(zhí)行過程
- 1.判定三個條件 table不為Null & table的長度大于0 & table指定的索引值不為Null
- 2.判定 匹配hash值 & 匹配key值 成功則返回 該值
- 3.若 first節(jié)點的下一個節(jié)點不為Null
- 3.1 若first的類型為TreeNode 紅黑樹 通過紅黑樹查找匹配值 并返回查詢值
- 3.2若上面判定不成功 則認為下一個節(jié)點為單向鏈表,通過循環(huán)匹配值
8.HashMap擴容原理分析
//重新設置table大小/擴容 并返回擴容的Node數組即HashMap的最新數據
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table; //table賦予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;
}
//若新表大小(oldCap*2)小于數組極限大小 并且 老表大于等于數組初始化大小
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//舊數組大小oldThr 經二進制運算向左位移1個位置 即 oldThr*2當作新數組的大小
newThr = oldThr << 1; // double threshold
}
//若老表中下次擴容大小oldThr大于0
else if (oldThr > 0)
newCap = oldThr; //將oldThr賦予控制新表大小的newCap
else { //若其他情況則將獲取初始默認大小
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//若新表的下表下一次擴容大小為0
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; //將當前表賦予table
if (oldTab != null) { //若oldTab中有值需要通過循環(huán)將oldTab中的值保存到新表中
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {//獲取老表中第j個元素 賦予e
oldTab[j] = null; //并將老表中的元素數據置Null
if (e.next == null) //若此判定成立 則代表e的下面沒有節(jié)點了
newTab[e.hash & (newCap - 1)] = e; //將e直接存于新表的指定位置
else if (e instanceof TreeNode) //若e是TreeNode類型
//分割樹，將新表和舊表分割成兩個樹钓试，并判斷索引處節(jié)點的長度是否需要轉換成紅黑樹放入新表存儲
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null; //存儲與舊索引的相同的節(jié)點
Node<K,V> hiHead = null, hiTail = null; //存儲與新索引相同的節(jié)點
Node<K,V> next;
//通過Do循環(huán) 獲取新舊索引的節(jié)點
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;
}
梳理以下HashMap.resize函數的執(zhí)行過程
- 1.判定數組是否已達到極限大小装黑，若判定成功將不再擴容，直接將老表返回
- 2.若新表大小(oldCap2)小于數組極限大小&老表大于等于數組初始化大小 判定成功則 舊數組大小oldThr 經二進制運算向左位移1個位置 即 oldThr2當作新數組的大小
- 2.1. 若[2]的判定不成功弓熏，則繼續(xù)判定 oldThr （代表 老表的下一次擴容量）大于0恋谭，若判定成功 則將oldThr賦給newCap作為新表的容量
- 2.2 若 [2] 和[2.1]判定都失敗,則走默認賦值 代表 表為初次創(chuàng)建
- 3.確定下一次表的擴容量, 將新表賦予當前表
- 4.通過for循環(huán)將老表中德值存入擴容后的新表中
- 4.1 獲取舊表中指定索引下的Node對象 賦予e 并將舊表中的索引位置數據置空
- 4.2 若e的下面沒有其他節(jié)點則將e直接賦到新表中的索引位置
- 4.3 若e的類型為TreeNode紅黑樹類型
- 4.3.1 分割樹，將新表和舊表分割成兩個樹挽鞠，并判斷索引處節(jié)點的長度是否需要轉換成紅黑樹放入新表存儲
- 4.3.2 通過Do循環(huán) 不斷獲取新舊索引的節(jié)點
- 4.3.3 通過判定將舊數據和新數據存儲到新表指定的位置
- 最后返回值為 擴容后的新表疚颊。
9.HashMap 的treeifyBin講解
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
//做判定 tab 為Null 或 tab的長度小于 紅黑樹最小容量
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
//則通過擴容,擴容table數組大小
resize();
//做判定 若tab索引位置下數據不為空
else if ((e = tab[index = (n - 1) & hash]) != null) {
//定義兩個紅黑樹；分別表示頭部節(jié)點信认、尾部節(jié)點
TreeNode<K,V> hd = null, tl = null;
//通過循環(huán)將單向鏈表轉換為紅黑樹存儲
do {
//將單向鏈表轉換為紅黑樹
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null) //若頭部節(jié)點為Null,則說明該樹沒有根節(jié)點
hd = p;
else {
p.prev = tl; //指向父節(jié)點
tl.next = p; //指向下一個節(jié)點
}
tl = p; //將當前節(jié)點設尾節(jié)點
} while ((e = e.next) != null); //若下一個不為Null,則繼續(xù)遍歷
//紅黑樹轉換后,替代原位置上的單項鏈表
if ((tab[index] = hd) != null)
hd.treeify(tab); // 構建紅黑樹串稀，以頭部節(jié)點定為根節(jié)點
}
}
TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
return new TreeNode<>(p.hash, p.key, p.value, next);
}
梳理以下HashMap.treeifyBin函數的執(zhí)行過程
- 1.做判定 tab 為Null 或 tab的長度小于紅黑樹最小容量， 判定成功則通過擴容,擴容table數組大小
- 2.做判定 若tab索引位置下數據不為空狮杨，判定成功則通過循環(huán)將單向鏈表轉換為紅黑樹存儲
- 2.1 通過Do循環(huán)將當前節(jié)點下的單向鏈表轉換為紅黑樹母截，若下一個不為Null,則繼續(xù)遍歷
- 2.2 構建紅黑樹，以頭部節(jié)點定為根節(jié)點
