概要
HashMap在JDK1.8之前的實(shí)現(xiàn)方式 數(shù)組+鏈表,但是在JDK1.8后對(duì)HashMap進(jìn)行了底層優(yōu)化,改為了由 數(shù)組+鏈表+紅黑樹實(shí)現(xiàn),主要的目的是提高查找效率来累。
如圖所示：
| JDK版本 | 實(shí)現(xiàn)方式 | 節(jié)點(diǎn)數(shù)>=8 | 節(jié)點(diǎn)數(shù)<=6 |
|---|---|---|---|
| 1.8以前 | 數(shù)組+單向鏈表 | 數(shù)組+單向鏈表 | 數(shù)組+單向鏈表 |
| 1.8以后 | 數(shù)組+單向鏈表+紅黑樹 | 數(shù)組+紅黑樹 | 數(shù)組+單向鏈表 |
HashMap
1.繼承關(guān)系
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable
2.常量&構(gòu)造方法
//這兩個(gè)是限定值 當(dāng)節(jié)點(diǎn)數(shù)大于8時(shí)會(huì)轉(zhuǎn)為紅黑樹存儲(chǔ)
static final int TREEIFY_THRESHOLD = 8;
//當(dāng)節(jié)點(diǎn)數(shù)小于6時(shí)會(huì)轉(zhuǎn)為單向鏈表存儲(chǔ)
static final int UNTREEIFY_THRESHOLD = 6;
//紅黑樹最小長(zhǎng)度為 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;
//負(fù)載因子默認(rèn)大小
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//Node是Map.Entry接口的實(shí)現(xiàn)類
//在此存儲(chǔ)數(shù)據(jù)的Node數(shù)組容量是2次冪
//每一個(gè)Node本質(zhì)都是一個(gè)單向鏈表
transient Node<K,V>[] table;
//HashMap大小,它代表HashMap保存的鍵值對(duì)的多少
transient int size;
//HashMap被改變的次數(shù)
transient int modCount;
//下一次HashMap擴(kuò)容的大小
int threshold;
//存儲(chǔ)負(fù)載因子的常量
final float loadFactor;
//默認(rèn)的構(gòu)造函數(shù)
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
//指定容量大小
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//指定容量大小和負(fù)載因子大小
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;
//指定的負(fù)載因子不可以小于0或?yàn)镹ull乐导，若判定成立則拋出IllegalArgumentException異常
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
// 設(shè)置“HashMap閾值”肩民，當(dāng)HashMap中存儲(chǔ)數(shù)據(jù)的數(shù)量達(dá)到threshold時(shí)袱蚓，就需要將HashMap的容量加倍。
this.threshold = tableSizeFor(initialCapacity);
}
//傳入一個(gè)Map集合,將Map集合中元素Map.Entry全部添加進(jìn)HashMap實(shí)例中
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
//此構(gòu)造方法主要實(shí)現(xiàn)了Map.putAll()
putMapEntries(m, false);
}
3.Node單向鏈表的實(shí)現(xiàn)
//實(shí)現(xiàn)了Map.Entry接口
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
//構(gòu)造函數(shù)
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屬性對(duì)比
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紅黑樹實(shí)現(xiàn)
static final class TreeNode<K,V> extends LinkedHashMap.LinkedHashMapEntry<K,V> {
TreeNode<K,V> parent; // 紅黑樹的根節(jié)點(diǎn)
TreeNode<K,V> left; //左樹
TreeNode<K,V> right; //右樹
TreeNode<K,V> prev; // 上一個(gè)幾點(diǎn)
boolean red; //是否是紅樹
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
/**
* 根節(jié)點(diǎn)的實(shí)現(xiàn)
**/
final TreeNode<K,V> root() {
for (TreeNode<K,V> r = this, p;;) {
if ((p = r.parent) == null)
return r;
r = p;
}
}
...
5.Hash的計(jì)算實(shí)現(xiàn)
//主要是將傳入的參數(shù)key本身的hashCode與h無符號(hào)右移16位進(jìn)行二進(jìn)制異或運(yùn)算得出一個(gè)新的hash值
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
延伸講解
5.1.下面的做了一個(gè)例子講解,經(jīng)過hash函數(shù)計(jì)算后得到的key的hash值
5.2那為什么要這么做呢犯建？直接通過key.hashCode()獲取hash不得了嗎?為什么在右移16位后進(jìn)行異或運(yùn)算诸狭？
答案 : 與HashMap的table數(shù)組下計(jì)算標(biāo)有關(guān)系
我們?cè)谙旅嬷v解的put/get函數(shù)代碼塊中都出現(xiàn)了這樣一段代碼
//put函數(shù)代碼塊中
tab[i = (n - 1) & hash])
//get函數(shù)代碼塊中
tab[(n - 1) & hash])
我們知道這段代碼是根據(jù)索引得到tab中節(jié)點(diǎn)數(shù)據(jù),它是如何與hash進(jìn)行與運(yùn)算后得到索引位置呢! 假設(shè)tab.length()=1<<4
這樣做的根本原因是當(dāng)發(fā)生較大碰撞時(shí)也用樹形存儲(chǔ)降低了沖突。既減少了系統(tǒng)的開銷
6.HashMap.put的源碼實(shí)現(xiàn)
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
//HashMap.put的具體實(shí)現(xiàn)
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長(zhǎng)度不可為0,否則將從resize函數(shù)中獲取
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//這樣寫法有點(diǎn)繞,其實(shí)這里就是通過索引獲取table數(shù)組中的一個(gè)元素看是否為Nul
if ((p = tab[i = (n - 1) & hash]) == null)
//若判斷成立,則New一個(gè)Node出來賦給table中指定索引下的這個(gè)元素
tab[i] = newNode(hash, key, value, null);
else { //若判斷不成立
Node<K,V> e; K k;
//對(duì)這個(gè)元素進(jìn)行Hash和key值匹配
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode) //如果數(shù)組中的這個(gè)元素P是TreeNode類型
//判定成功則在紅黑樹中查找符合的條件的節(jié)點(diǎn)并返回此節(jié)點(diǎn)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else { //若以上條件均判斷失敗辟躏，則執(zhí)行以下代碼
//向Node單向鏈表中添加數(shù)據(jù)
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//若節(jié)點(diǎn)數(shù)大于等于8
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
//轉(zhuǎn)換為紅黑樹
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e; //p記錄下一個(gè)節(jié)點(diǎn)
}
}
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) //判斷是否需要擴(kuò)容
resize();
afterNodeInsertion(evict);
return null;
}
梳理以下HashMap.put函數(shù)的執(zhí)行過程
1.首先獲取Node數(shù)組table對(duì)象和長(zhǎng)度谷扣，若table為null或長(zhǎng)度為0，則調(diào)用resize()擴(kuò)容方法獲取table最新對(duì)象，并通過此對(duì)象獲取長(zhǎng)度大小2.判定數(shù)組中指定索引下的節(jié)點(diǎn)是否為Null会涎，若為Null 則new出一個(gè)單向鏈表賦給table中索引下的這個(gè)節(jié)點(diǎn)3.若判定不為Null,我們的判斷再做分支3.1 首先對(duì)hash和key進(jìn)行匹配,若判定成功直接賦予e3.2 若匹配判定失敗,則進(jìn)行類型匹配是否為TreeNode 若判定成功則在紅黑樹中查找符合條件的節(jié)點(diǎn)并將其回傳賦給e3.3 若以上判定全部失敗則進(jìn)行最后操作,向單向鏈表中添加數(shù)據(jù)若單向鏈表的長(zhǎng)度大于等于8,則將其轉(zhuǎn)為紅黑樹保存裹匙，記錄下一個(gè)節(jié)點(diǎn),對(duì)e進(jìn)行判定若成功則返回舊值4.最后判定數(shù)組大小需不需要擴(kuò)容
7.HashMap.get的源碼實(shí)現(xiàn)
//這里直接調(diào)用getNode函數(shù)實(shí)現(xiàn)方法
public V get(Object key) {
Node<K,V> e;
//經(jīng)過hash函數(shù)運(yùn)算 獲取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;
//判定三個(gè)條件 table不為Null & table的長(zhǎng)度大于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é)點(diǎn)的下一個(gè)節(jié)點(diǎn)不為Null
if ((e = first.next) != null) {
if (first instanceof TreeNode) //若first的類型為TreeNode 紅黑樹
//通過紅黑樹查找匹配值 并返回
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
//若上面判定不成功 則認(rèn)為下一個(gè)節(jié)點(diǎn)為單向鏈表,通過循環(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函數(shù)的執(zhí)行過程
1.判定三個(gè)條件 table不為Null & table的長(zhǎng)度大于0 & table指定的索引值不為Null
2.判定 匹配hash值 & 匹配key值 成功則返回 該值
3.若 first節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)不為Null
3.1 若first的類型為TreeNode 紅黑樹 通過紅黑樹查找匹配值 并返回查詢值
3.2若上面判定不成功 則認(rèn)為下一個(gè)節(jié)點(diǎn)為單向鏈表,通過循環(huán)匹配值
8.HashMap擴(kuò)容原理分析
//重新設(shè)置table大小/擴(kuò)容 并返回?cái)U(kuò)容的Node數(shù)組即HashMap的最新數(shù)據(jù)
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table; //table賦予oldTab作為擴(kuò)充前的table數(shù)據(jù)
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
//判定數(shù)組是否已達(dá)到極限大小，若判定成功將不再擴(kuò)容末秃，直接將老表返回
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//若新表大小(oldCap*2)小于數(shù)組極限大小 并且 老表大于等于數(shù)組初始化大小
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//舊數(shù)組大小oldThr 經(jīng)二進(jìn)制運(yùn)算向左位移1個(gè)位置 即 oldThr*2當(dāng)作新數(shù)組的大小
newThr = oldThr << 1; // double threshold
}
//若老表中下次擴(kuò)容大小oldThr大于0
else if (oldThr > 0)
newCap = oldThr; //將oldThr賦予控制新表大小的newCap
else { //若其他情況則將獲取初始默認(rèn)大小
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//若新表的下表下一次擴(kuò)容大小為0
if (newThr == 0) {
float ft = (float)newCap * loadFactor; //通過新表大小*負(fù)載因子獲取
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr; //下次擴(kuò)容的大小
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab; //將當(dāng)前表賦予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個(gè)元素 賦予e
oldTab[j] = null; //并將老表中的元素?cái)?shù)據(jù)置Null
if (e.next == null) //若此判定成立 則代表e的下面沒有節(jié)點(diǎn)了
newTab[e.hash & (newCap - 1)] = e; //將e直接存于新表的指定位置
else if (e instanceof TreeNode) //若e是TreeNode類型
//分割樹概页，將新表和舊表分割成兩個(gè)樹，并判斷索引處節(jié)點(diǎn)的長(zhǎng)度是否需要轉(zhuǎn)換成紅黑樹放入新表存儲(chǔ)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null; //存儲(chǔ)與舊索引的相同的節(jié)點(diǎn)
Node<K,V> hiHead = null, hiTail = null; //存儲(chǔ)與新索引相同的節(jié)點(diǎn)
Node<K,V> next;
//通過Do循環(huán) 獲取新舊索引的節(jié)點(diǎn)
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);
//通過判定將舊數(shù)據(jù)和新數(shù)據(jù)存儲(chǔ)到新表指定的位置
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
//返回新表
return newTab;
}
梳理以下HashMap.resize函數(shù)的執(zhí)行過程
如圖所示：
1.判定數(shù)組是否已達(dá)到極限大小练慕，若判定成功將不再擴(kuò)容惰匙，直接將老表返回2.若新表大小(oldCap2)小于數(shù)組極限大小&老表大于等于數(shù)組初始化大小 判定成功則 舊數(shù)組大小oldThr 經(jīng)二進(jìn)制運(yùn)算向左位移1個(gè)位置 即 oldThr2當(dāng)作新數(shù)組的大小2.1. 若[2]的判定不成功，則繼續(xù)判定 oldThr （代表 老表的下一次擴(kuò)容量）大于0铃将，若判定成功 則將oldThr賦給newCap作為新表的容量2.2 若 [2] 和[2.1]判定都失敗,則走默認(rèn)賦值 代表 表為初次創(chuàng)建3.確定下一次表的擴(kuò)容量, 將新表賦予當(dāng)前表4.通過for循環(huán)將老表中的值存入擴(kuò)容后的新表中4.1 獲取舊表中指定索引下的Node對(duì)象 賦予e 并將舊表中的索引位置數(shù)據(jù)置空4.2 若e的下面沒有其他節(jié)點(diǎn)則將e直接賦到新表中的索引位置4.3 若e的類型為TreeNode紅黑樹類型4.3.1 分割樹项鬼，將新表和舊表分割成兩個(gè)樹，并判斷索引處節(jié)點(diǎn)的長(zhǎng)度是否需要轉(zhuǎn)換成紅黑樹放入新表存儲(chǔ)4.3.2 通過Do循環(huán) 不斷獲取新舊索引的節(jié)點(diǎn)5.最后返回值為 擴(kuò)容后的新表劲阎。
9.HashMap 的treeifyBin講解
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
//做判定 tab 為Null 或 tab的長(zhǎng)度小于 紅黑樹最小容量
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
//則通過擴(kuò)容,擴(kuò)容table數(shù)組大小
resize();
//做判定 若tab索引位置下數(shù)據(jù)不為空
else if ((e = tab[index = (n - 1) & hash]) != null) {
//定義兩個(gè)紅黑樹绘盟；分別表示頭部節(jié)點(diǎn)、尾部節(jié)點(diǎn)
TreeNode<K,V> hd = null, tl = null;
//通過循環(huán)將單向鏈表轉(zhuǎn)換為紅黑樹存儲(chǔ)
do {
//將單向鏈表轉(zhuǎn)換為紅黑樹
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null) //若頭部節(jié)點(diǎn)為Null,則說明該樹沒有根節(jié)點(diǎn)
hd = p;
else {
p.prev = tl; //指向父節(jié)點(diǎn)
tl.next = p; //指向下一個(gè)節(jié)點(diǎn)
}
tl = p; //將當(dāng)前節(jié)點(diǎn)設(shè)尾節(jié)點(diǎn)
} while ((e = e.next) != null); //若下一個(gè)不為Null,則繼續(xù)遍歷
//紅黑樹轉(zhuǎn)換后,替代原位置上的單項(xiàng)鏈表
if ((tab[index] = hd) != null)
hd.treeify(tab); // 構(gòu)建紅黑樹悯仙，以頭部節(jié)點(diǎn)定為根節(jié)點(diǎn)
}
}
TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
return new TreeNode<>(p.hash, p.key, p.value, next);
}
梳理以下HashMap.treeifyBin函數(shù)的執(zhí)行過程
1.做判定 tab 為Null 或 tab的長(zhǎng)度小于紅黑樹最小容量奥此， 判定成功則通過擴(kuò)容,擴(kuò)容table數(shù)組大小2.做判定 若tab索引位置下數(shù)據(jù)不為空，判定成功則通過循環(huán)將單向鏈表轉(zhuǎn)換為紅黑樹存儲(chǔ)2.1 通過Do循環(huán)將當(dāng)前節(jié)點(diǎn)下的單向鏈表轉(zhuǎn)換為紅黑樹雁比，若下一個(gè)不為Null,則繼續(xù)遍歷2.2 構(gòu)建紅黑樹稚虎，以頭部節(jié)點(diǎn)定為根節(jié)點(diǎn)
轉(zhuǎn)載地址：https://mp.weixin.qq.com/s/LxASRnHHseS7o2teydqtFw
