深入解析JDK1.8后的HashMap底层存储
前言
这次分享总结很多内容，保姆级注释，有空会将一些核心东西拆开分享
HashMap底层存储数据的结构变化：
JDK1.7底层是由 【数组】 & 【链表】组成的，单向链表Entry挂在数组上。JDK1.8后底层则变为【数组】 & 【链表】、【红黑树】，特殊情况下（数组容量大于等于64后，链表的节点数超过了8个），将该链表转换为红黑树
满足红黑树的条件：
1、每个节点要么是红色，要么是黑色
2、根节点一定是黑色的
3、每个叶子节点一定是黑色的（最后都会指向 NIL/NULL 的叶子节点）
4、如果一个节点是红色，那么它的左右子节点一定都是黑色的
5、从任意一个节点到叶子节点，所经过的黑色节点的数量一样多
源码解析
全局变量
transient Node<K,V>[] table; //当前使用的数组
int threshold; //当前使用的阈值
final float loadFactor; //当前使用的加载因子
transient int modCount; //结构变更次数
transient int size; //k-v对数
对于源码解析的方向是先从HashMap的构造函数开始，到put数据方法
构造函数
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
//默认加载因子
//值含义：数组容量的长度到达其容量长度的0.75倍的时候，就会被扩容
//类似水库中的安全水位线的意思
static final float DEFAULT_LOAD_FACTOR = 0.75f;
.
final float loadFactor;
.
public HashMap() {
// all other fields defaulted
//初始化加载因子参数值为0.75f
//元素所占的空间达到加载因⼦的规定值的时候，那么就会执⾏扩容。
this.loadFactor = DEFAULT_LOAD_FACTOR;
}
}
好奇心驱使引出，默认加载因子为何设置成0.75，不是0.6，0.7,0.8这个问题
通过查阅相关资料，得出关键词——泊松分布。大概理解为，在理想情况下，默认加载因子配合hash算法得到的hash码可以使数组中的节点数量遵循泊松分布。可以尽量避免数组节点上的链表长度，避免HashMap的查询时间复杂度从O(1)变成O(n)
视线回到put方法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
//--------------------------------------------------------
/**
* Implements Map.put and related methods
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value 如果是true，不改变现有的value
* @param evict if false, the table is in creation mode. 如果是false, table为创建模式
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i; //tab 存储链表的数组，p 为链表节点， 数字 n,i
if ((tab = table) == null || (n = tab.length) == 0) //第一步、赋值 tab 为table数组 ， n 为tab的数组长度
n = (tab = resize()).length; //如果都为null,对table数组进行初始化并构建
if ((p = tab[i = (n - 1) & hash]) == null) //第二步、 向数组中插入元素
tab[i] = newNode(hash, key, value, null); //没有哈希冲突，给tab数组对应索引位置赋值
else { //发生哈希冲突，HashMap是如何处理的？
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);
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;
}
}
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;
}
putVal方法中分为三大步
1、创建table数组
2、向table数组中赋值，对哈希冲突与不冲突两种情况的处理
3、判断容量大小是否超过阈值，对其扩容操作
针对putVal三大步进行详细剖析
1、创建table数组
if ((tab = table) == null || (n = tab.length) == 0) //赋值 tab 为table数组 ， n 为tab的数组长度
n = (tab = resize()).length; //如果数组为null，长度为0,对table数组进行初始化并构建
对HashMap数组是否null，或者长度为0时，执行resize（）扩容方法
来看看resize方法的源码
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table; //创建旧table数组
int oldCap = (oldTab == null) ? 0 : oldTab.length; //旧容量
int oldThr = threshold; //旧阈值
int newCap, newThr = 0; //新容量，阈值
if (oldCap > 0) {
// 最大容量 MAXIMUM_CAPACITY = 1 << 30 == 1073741824(2的30次方)
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && //新容量扩容原来的2倍（oldCap << 1）
// 默认初始化容量 DEFAULT_INITIAL_CAPACITY = 1 << 4 == 16
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold //新阈值扩容原来的2倍
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
//oldCap == 0 && oldThr == 0
newCap = DEFAULT_INITIAL_CAPACITY;
//新阈值赋值为默认初始容量 * 默认加载因子（16 * 0.75） = 12
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;
//创建newTab数组
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
//oldTab为null，则直接返回新创建数组
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) { //遍历旧table数组，进行数据迁移操作
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e; //重新计算新table数组中的位置，并迁移赋值
else if (e instanceof TreeNode)
//对象为TreeNode时进行分裂操作
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order 维护顺序
Node<K,V> loHead = null, loTail = null;//定义头尾node
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next; //下个node
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;
//将低位链表放到新table下标处
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
//将高位链表放到新table[j + oldCap]处
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
resize方法逻辑判断虽多，主要分为两部分：
1、取旧容量，阈值，对新容量，阈值重新赋值，并扩容
2、对于oldTab 不为 null 的逻辑处理为 旧table数组以及链表或红黑树向扩容后新table数组数据迁移过程，数组长度变化，导致hash寻址的时候有些元素位置变化，进而拆分链表，分裂红黑树操作。红黑树长度分裂后长度小到一定程度，会转换回链表，后续深入讲解链表，红黑树相互转换
2、向table数组中插入元素
分两种情况插入：无哈希冲突，发生哈希冲突
2.1 、没有发生哈希冲突
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null); //没有哈希冲突，给tab数组对应索引位置赋值
通过（n - 1）& hash来寻找地址，找索引位置
2.2 、发生哈希冲突
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k)))) //判断索引位置值与待插入值是否相同
e = p; //讲旧node赋值给e
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);
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;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value; //将新值value覆盖旧value
afterNodeAccess(e); //将红黑树root节点放到链表队首并放到数组中
return oldValue;
}
}
2.2.1 冲突节点与待插入节点key相同
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k)))) //判断索引位置值与待插入值是否相同
e = p; //讲旧node赋值给e
//
//
//
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value; //将新值value覆盖旧value
afterNodeAccess(e);
return oldValue;
}
不涉及到链表、红黑树时，将旧node赋值为e，新值value赋值给旧value
注意：在put方法中的onlyAbsent设置为false，运行覆盖旧value，反之不可覆盖。
2.2.2 向红⿊树中插⼊元素
else if (p instanceof TreeNode) //红黑树处理哈希冲突
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
.
.
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);
}
TreeNode包含两部分：
1、树结构（⽗节点：parent，左⼦节点：left，右⼦节点：right）
2、链表结构（前指针：prev，后指针：next）
public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>{
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
}
//hashMap中
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
.
.
}
继续看详细putTreeVal方法
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
int h, K k, V v) {
Class<?> kc = null;
boolean searched = false;
TreeNode<K,V> root = (parent != null) ? root() : this; //寻址root根节点
for (TreeNode<K,V> p = root;;) {
int dir, ph; K pk;
//先确定待插入节点在树的什么位置，左侧，右侧，还是本身位置
if ((ph = p.hash) > h)
dir = -1; //左侧
else if (ph < h)
dir = 1; //右侧
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0) {
if (!searched) {
TreeNode<K,V> q, ch;
searched = true;
if (((ch = p.left) != null &&
(q = ch.find(h, k, kc)) != null) ||
((ch = p.right) != null &&
(q = ch.find(h, k, kc)) != null))
return q;
}
dir = tieBreakOrder(k, pk);
}
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
Node<K,V> xpn = xp.next;
TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
if (dir <= 0)
xp.left = x;
else
xp.right = x;
xp.next = x;
x.parent = x.prev = xp;
if (xpn != null)
((TreeNode<K,V>)xpn).prev = x; //作为子节点插入相应位置
//moveRootToFront将最新的root插入到数组中
moveRootToFront(tab, balanceInsertion(root, x)); //balanceInsertion平衡红黑树插入
return null;
}
}
}
通过上面分析可以将putTreeVal方法分为五步：
1、寻址根节点
2、确定插入位置
3、构造TreeNode插入对应位置
4、红黑树平衡调整
5、moveRootToFront
2.2.2.1 寻址根节点
parent代表父节点，可知p = tab[i]，就是table数组中i位置上元素
TreeNode<K,V> root = (parent != null) ? root() : this; //寻址root根节点
如果p的父节点为null，说明自身为root根节点，如果不为null，继续遍历查找
2.2.2.2 确定插入位置
*在for循环中根据p节点的哈市值与待插入元素的hash值，如果p节点哈希值大，则待插入值元素在p节点左侧，判断相反则反之。
2.2.2.3 构造TreeNode插入对应位置
可以看出dir参数等于 -1 时为左侧，反之为右侧。局部变量 x表示待插入的树节点，xp表示x节点的parent节点， xpn表示xp的next节点，后置节点。逻辑过程，将xp双向next互指xpn——>xp双向pre互指x双向next互指xpn
2.2.2.4 红黑树平衡调整
看一下balanceInsertion方法
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
TreeNode<K,V> x) {
x.red = true; //初始化待插入元素为红色
for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
if ((xp = x.parent) == null) { //判断是否有父节点元素，没有直接返回自身，并改为黑色
x.red = false;
return x;
}
else if (!xp.red || (xpp = xp.parent) == null) //判断父节点是否为黑色，或者没有祖父节点，直接返回root节点
return root;
//--------------平衡插入逻辑--------------------
if (xp == (xppl = xpp.left)) { //判断x的父节点元素是在祖父节点左侧
if ((xppr = xpp.right) != null && xppr.red) { //判断祖父节点的左右节点如果都是红色节点
xppr.red = false; //将这两个节点颜色变为黑色，祖父节点变为红色
xp.red = false;
xpp.red = true;
x = xpp;
}
else {
if (x == xp.right) {
root = rotateLeft(root, x = xp); //向左旋转
xpp = (xp = x.parent) == null ? null : xp.parent;
}
if (xp != null) {
xp.red = false;
if (xpp != null) {
xpp.red = true;
root = rotateRight(root, xpp); //向右旋转
}
}
}
}
else { //x的父节点在祖父节点右侧
if (xppl != null && xppl.red) { //祖父节点的左右子节点如果都为红色节点
xppl.red = false; //将这两个节点都变为黑色，祖父节点变为红色
xp.red = false;
xpp.red = true;
x = xpp;
}
else {
if (x == xp.left) {
root = rotateRight(root, x = xp); //右旋操作
xpp = (xp = x.parent) == null ? null : xp.parent;
}
if (xp != null) {
xp.red = false;
if (xpp != null) {
xpp.red = true;
root = rotateLeft(root, xpp); //左旋
}
}
}
}
}
}
平衡逻辑分两部分
部分一：
如果x的父节点在祖父节点的左侧，操作类型为：变色
操作条件：如果祖父节点的右节点（/左节点）是红色的，操作类型为：旋转 & 变色
部分二：
如果x的父节点在祖父节点的右侧，操作类型为：变色
操作条件：如果祖父节点的左节点（/右节点）是红色的，操作类型为：旋转 & 变色
变色场景一
变色场景二
旋转 + 变色 场景一
旋转 + 变色 场景二
2.2.2.5 moveRootToFront
先从方法名分析，将root移动到整条双向链表的头部，并放入到数组中
看一下 moveRootToFront方法
static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
int n;
if (root != null && tab != null && (n = tab.length) > 0) {
int index = (n - 1) & root.hash; //判断table数组中存储的元素是不是最新的root节点
TreeNode<K,V> first = (TreeNode<K,V>)tab[index];
if (root != first) { //如果不是，重塑双向链表的链接，
Node<K,V> rn;
tab[index] = root;
TreeNode<K,V> rp = root.prev; //把root放链表头位置，并插入到table数组中
if ((rn = root.next) != null)
((TreeNode<K,V>)rn).prev = rp;
if (rp != null)
rp.next = rn;
if (first != null)
first.prev = root;
root.next = first;
root.prev = null;
}
assert checkInvariants(root); //最终检验整个红黑树结构
}
}
2.2.3 向单向链表中插⼊元素
看一下源码部分
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
.
.
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
//如果没有与待插入key相同的节点，创建新Node，放入链表末尾
p.next = newNode(hash, key, value, null);
//如果达到红黑树阈值（TREEIFY_THRESHOLD == 8），满足条件后转换为红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
//如果发现链表中有key相同元素，直接取出，根据onlyAbsent来决定是否覆盖旧value
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
.
.
}
.
.
}
2.2.3.1 treeifyBin方法逻辑
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
//如果table数组长度小于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 {
//将链表Node转换为红黑树TreeNode结构
TreeNode<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方法中的split方法最后来看一下—((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
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;
//由于TreeNode结构中，有树结构，也有双向链表结构，可通过该双向链表去遍历红黑树每个节点
for (TreeNode<K,V> e = b, next; e != null; e = next) {
//循环体中逻辑：进行扩容后，hash寻址会发生变化
//通过重新计算将原有红黑树也拆分高低位双向链表
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) {
// UNTREEIFY_THRESHOLD = 6 非树阈值为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);
}
}
}
相比前面逻辑untreeify方法逻辑就很简单
final Node<K,V> untreeify(HashMap<K,V> map) {
Node<K,V> hd = null, tl = null;
//遍历node链表，重新组装成链表
for (Node<K,V> q = this; q != null; q = q.next) {
Node<K,V> p = map.replacementNode(q, null);
if (tl == null)
hd = p;
else
tl.next = p;
tl = p;
}
return hd;
}
// For conversion from TreeNodes to plain nodes
Node<K,V> replacementNode(Node<K,V> p, Node<K,V> next) {
return new Node<>(p.hash, p.key, p.value, next);
}
下面的treeify方法大概看一下
final void treeify(Node<K,V>[] tab) {
TreeNode<K,V> root = null;
//遍历双向链表中的TreeNode
for (TreeNode<K,V> x = this, next; x != null; x = next) {
next = (TreeNode<K,V>)x.next;
x.left = x.right = null;
//循环第一次进来，默认第一个TreeNode为root
if (root == null) {
x.parent = null;
x.red = false;
root = x;
}
else {
K k = x.key;
int h = x.hash;
Class<?> kc = null;
for (TreeNode<K,V> p = root;;) {
//确定插入位置是左是右
int dir, ph;
K pk = p.key;
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
dir = tieBreakOrder(k, pk);
//将节点x插入到树中
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
x.parent = xp;
if (dir <= 0)
xp.left = x;
else
xp.right = x;
//红黑树平衡方法
root = balanceInsertion(root, x);
break;
}
}
}
}
moveRootToFront(tab, root);
}
最后将链表转换为红黑树方法treeifyBin
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
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 {
TreeNode<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);
}
}
总结
前辈留我们的东西，值得我们深入体会与学习，第一次分享，有不太准确的地方，还希望交流学习。