Map讀寫實現(xiàn)邏輯說明
前一篇博文 JDK容器學(xué)習(xí)之HashMap (一) ： 底層存儲結(jié)構(gòu)分析 分析了HashMap的底層存儲數(shù)據(jù)結(jié)構(gòu)
通過
put(k,v)方法的分析，說明了為什么Map底層用數(shù)組進(jìn)行存儲，為什么Node內(nèi)部有一個next節(jié)點(diǎn)骇扇，這篇則將集中在讀寫方法的具體實現(xiàn)上
本片博文將關(guān)注的重點(diǎn)：
- 通過key獲取
value的實現(xiàn)邏輯 - 新增一個kv對的實現(xiàn)邏輯
-
table數(shù)組如何自動擴(kuò)容 - 如何刪除一個kv對（刪除kv對之后欢伏，數(shù)組長度是否會縮水 ？）
1. 根據(jù)key索引
get(key)作為map最常用的方法之一歌焦，根據(jù)key獲取映射表中的value淮捆，通常時間復(fù)雜度為o(1)
在分析之前，有必要再把HashMap的數(shù)據(jù)結(jié)構(gòu)撈出來看一下
結(jié)構(gòu)描述
根據(jù)上面的結(jié)構(gòu)憋飞，如果讓我們自己來實現(xiàn)這個功能霎苗，對應(yīng)的邏輯應(yīng)該如下：
- 計算key的hash值
- 根據(jù)hash確定在
table數(shù)組中的位置 - 判斷數(shù)組的Node對象中key是否等同與傳入的key
- 若不是，則一次掃描
next節(jié)點(diǎn)的key榛做，直到找到為止
jdk實現(xiàn)如下
public V get(Object key) {
Node<K,V> e;
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;
// 判斷條件 if 內(nèi)部邏輯如下
// table 數(shù)組已經(jīng)初始化（即非null唁盏，長度大于0）
// 數(shù)組中根據(jù)key查到的Node對象非空
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && // always check first node
((k = first.key) == key
|| (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
if (first instanceof TreeNode)
// 紅黑樹中查找
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {// 遍歷鏈表
if (e.hash == hash &&
((k = e.key) == key
|| (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
上面的邏輯算是比較清晰，再簡單的劃一下重點(diǎn)
- 通過key定位table數(shù)組中索引的具體邏輯
hash(key) & (table.length - 1)- key的hash值與(數(shù)組長度-1)進(jìn)行按位與检眯，計算得到下標(biāo)
- 判斷Node是否為所查找的目標(biāo)邏輯
node.hash == hash(key) && (node.key == key || (key!=null && key.equals(node.key))- 首先是hash值必須相等
-
and == or equals- key為同一個對象
- or Node的key等價于傳入的key
- TreeNode 是個什么鬼
上面的邏輯中厘擂，當(dāng)出現(xiàn)hash碰撞時，會判斷數(shù)組中的Node對象是否為 TreeNode锰瘸，如果是則調(diào)用 TreeNode.getTreeNode(hash,key) 方法
那么這個TreeNode有什么特殊的地方呢刽严？
2. TreeNode 分析
TreeNode依然是HashMap的內(nèi)部類, 不同于Node的是，它繼承自LinkedHashMap.Entry避凝，相比較與Node對象而言舞萄，多了兩個屬性before, after
1. 數(shù)據(jù)結(jié)構(gòu)
TreeNode對象中，包含的數(shù)據(jù)如下（將父類中的字段都集中在下面了）
// Node 中定義的屬性
final int hash;
final K key;
V value;
Node<K,V> next;
// ---------------
// LinkedHashMap.Entry 中的屬性
Entry<K,V> before, after;
// ---------------
// TreeNode 中定義的屬性
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;
2. 內(nèi)部方法
方法比較多管削，實現(xiàn)也不少倒脓，但是看看方法名以及注釋，很容易猜到這是個什么東西了
紅黑樹
具體方法實現(xiàn)身略（對紅黑樹實現(xiàn)有興趣的含思，就可以到這里來膜拜教科書的實現(xiàn)方式）
3. TreeNode 方式的HashMap存儲結(jié)構(gòu)
普通的Node就是一個單向鏈表崎弃，因此HashMap的結(jié)構(gòu)就是上面哪種
TreeNode是一顆紅黑樹的結(jié)構(gòu)，所以對上面的圖走一下簡單的改造含潘，將單向鏈表改成紅黑樹即可
newTech
3. 添加kv對
博文 JDK容器學(xué)習(xí)之HashMap (一) ： 底層存儲結(jié)構(gòu)分析 對于添加kv對的邏輯進(jìn)行了說明饲做，因此這里將主要集中在數(shù)組的擴(kuò)容上
擴(kuò)容的條件： 默認(rèn)擴(kuò)容加載因子為(0.75)，臨界點(diǎn)在當(dāng)HashMap中元素的數(shù)量等于table數(shù)組長度加載因子,長度擴(kuò)為原來的2倍*
數(shù)組擴(kuò)容方法, 實現(xiàn)比較復(fù)雜遏弱，先擼一把代碼盆均，并加上必要注釋
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table; // 持有舊數(shù)組的一份引用
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
// 容量超過上限，直接返回漱逸，不用再繼續(xù)分配
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
// 新的數(shù)組長度設(shè)置為原數(shù)組長度的兩倍
// 新的閥值為舊閥值的兩倍缀踪，
newThr = oldThr << 1; // double threshold
} else if (oldThr > 0) {
// initial capacity was placed in threshold
newCap = oldThr;
} else {
// 首次初始化
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 = newTab;
if (oldTab != null) {
// 下面是將舊數(shù)組中的元素，塞入新的數(shù)組中
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null) {
// 若Node節(jié)點(diǎn)沒有出現(xiàn)hash碰撞虹脯，則直接塞入新的數(shù)組
newTab[e.hash & (newCap - 1)] = e;
} else if (e instanceof TreeNode) {
// 對于出現(xiàn)hash碰撞驴娃，且紅黑樹結(jié)構(gòu)時，需要重新分配
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
} else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
// 新的位置相比原來的新增了 oldCap
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;
}
上面的邏輯主要劃分為兩塊
- 新的數(shù)組長度確定循集，并初始化新的數(shù)組
- 將原來的數(shù)據(jù)遷移到新的數(shù)組中
- 遍歷舊數(shù)組元素
- 若Node沒有尾節(jié)點(diǎn)(Next為null)唇敞，則直接塞入新的數(shù)組
- 判斷Node的數(shù)據(jù)結(jié)構(gòu)，紅黑樹和鏈表邏輯有區(qū)分
- 對于鏈表格式，新的坐標(biāo)要么是原來的位置疆柔，要么是原來的位置+原數(shù)組長度咒精，鏈表順序不變
說明
這個擴(kuò)容的邏輯還是比較有意思的，最后面給一個測試case旷档，來看一下擴(kuò)容前后的數(shù)據(jù)位置
4. 刪除元素
刪除的邏輯和上面的大致類似模叙，顯示確定節(jié)點(diǎn)，然后從整個數(shù)據(jù)結(jié)構(gòu)中移除引用
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
// 刪除的前置條件：
// 1. 數(shù)組已經(jīng)初始化
// 2. key對應(yīng)的Node節(jié)點(diǎn)存在
if ((tab = table) != null && (n = tab.length) > 0
&& (p = tab[index = (n - 1) & hash]) != null) {
Node<K,V> node = null, e; K k; V v;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k)))) {
// 數(shù)組中的Node節(jié)點(diǎn)即為目標(biāo)
node = p;
} else if ((e = p.next) != null) {
// hash碰撞鞋屈，目標(biāo)可能在鏈表or紅黑樹中
// 便利鏈表or紅黑樹范咨，確定目標(biāo)
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
if (node != null &&
(!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
// 找到目標(biāo)節(jié)點(diǎn)，直接從數(shù)組or紅黑樹or鏈表中移除
// 不改變Node節(jié)點(diǎn)的內(nèi)容
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p)
tab[index] = node.next;
else
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}
測試
上面的幾個常用方法的邏輯大致相同厂庇，核心都是在如何找到目標(biāo)Node節(jié)點(diǎn)渠啊，其中比較有意思的一點(diǎn)是數(shù)組的擴(kuò)容，舊元素的遷移邏輯权旷，下面寫個測試demo來演示一下
首先定義一個Deom對象替蛉，覆蓋hashCode方法，確保第一次重新分配數(shù)組時拄氯，正好需要遷移
public static class Demo {
public int num;
public Demo(int num) {
this.num = num;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Demo demo = (Demo) o;
return num == demo.num;
}
@Override
public int hashCode() {
return num % 3 + 16;
}
}
@Test
public void testMapResize() {
Map<Demo, Integer> map = new HashMap<>();
for(int i = 1; i < 12; i++) {
map.put(new Demo(i), i);
}
// 下面這一行執(zhí)行躲查，并不會觸發(fā)resize方法
map.put(new Demo(12), 12);
// 執(zhí)行下面這一行，會觸發(fā)HashMap的resize方法
// 因為 hashCode值 & 16 == 1译柏，所以新的位置會是原來的位置+16
map.put(new Demo(13), 13);
}
實際演示示意圖
showdemo.gif
小結(jié)
1. 根據(jù)Key定位Node節(jié)點(diǎn)
- key計算hash镣煮，hash值對數(shù)組長度取余即為數(shù)組中的下標(biāo)
- 即
hash & (len - 1) === hash % len
- 即
- 以數(shù)組中Node為鏈表頭or紅黑樹根節(jié)點(diǎn)遍歷，確認(rèn)目標(biāo)節(jié)點(diǎn)
- 判斷邏輯：
- hash值相同
key1 == key2 or key1.quals(key2)
2. 擴(kuò)容邏輯
- 當(dāng)添加元素后艇纺，數(shù)組的長度超過閥值，實現(xiàn)擴(kuò)容
- 初始容量為16邮弹，閥值為12
- 計算新的數(shù)組長度黔衡，并初始化
- 新的長度為原來的長度 * 2
- 新的閥值為 新的長度 *
loadFactor;loadFactory一般為 0.75
- 將原來的數(shù)據(jù)遷移到新的數(shù)組
- 原位置不變
(hash % 原長度 == 0) - 原位置 + 原數(shù)組長度
(hash % 原長度 == 1)
- 原位置不變
3. 其他
- jdk1.8 之后，當(dāng)鏈表長度超過閥值（8）后腌乡，轉(zhuǎn)為紅黑樹
- 新增元素盟劫，在添加完畢之后，再判斷是否需要擴(kuò)容
- 刪除元素不會改變Node對象本身与纽，只是將其從Map的數(shù)據(jù)結(jié)構(gòu)中 摘 出來
- Map如何退化為鏈表
- 一個糟糕的hashCode方法即可模擬實現(xiàn)侣签，如我們上面的測試用例
- 紅黑樹會使這種退化的效果不至于變得那么糟糕
相關(guān)博文
關(guān)注更多
掃一掃二維碼，關(guān)注 小灰灰blog
https://static.oschina.net/uploads/img/201709/22221611_Fdo5.jpg
