概述
HashMap
作者：CloudMissing
HashMap
写在前面
HashMap 是 java.util 包下的基于 <K，V> 键值对存储的数据结构。HashMap 是集合框架中的重要角色之一，实现了 Map 接口。
HashMap 对大数据量的元素插入有最优的解决方案，由 bins 数组 -> 链表 <=> 平衡树 但由于 LinkedHashMap 子类的存在，HashMap在插入、移除或者连接时，都会提供对应的钩子函数给 LinkedHashMap。
HashMap 通常被当作 分桶哈希表，使用数组来存放这些桶。在桶过大时，桶的内部对象会由 Node 演变为 TreeNode 排序树，类似于 TreeMap 的结构。TreeNodes 节点也会跟 Nodes 节点一样遍历，同时在数量过多时，提供了更快的便利。当桶变小时，还会由 TreeNode 变为 Node。
因为 HashMap 是线程不安全的，所以迭代器返回的都是快速-失败的：如果在创建迭代器后的任何时候对映射进行了结构修改，除了通过迭代器自己的 remove 方法之外的任何方式，迭代器都会抛出 ConcurrentModificationException。因此，面对并发修改，迭代器快速而干净地失败，而不是在未来不确定的时间冒出任意的、不确定的行为。
与 HashTable 的比较
HashMap 大致相当于 HashTable，但是二者也是有一些区别的。
是否允许出现 NULL 值。HashMap 是允许 key 和 value 出现 NULL 值，HashTable 是不允许 key 和 value 出现 NULL 值
tip ：因为 HashTable 实现了 Dictionary 接口，字典的 key 和 value 必须不为 null
是否线程安全。HashMap 是线程不安全的，非同步方法，当然可以使用 Collections.synchronizedMap(new HashMap(…)) 去实现同步。HashTable 是线程安全的，在 PUT 方法时，添加了 Synchonized 关键字
扩容大小不同。HashMap 每次 resize 方法执行之后，旧的容量 左移一位 （newThr = oldThr << 1）就是新的容量。HashTable 每次 rehash 之后，旧的容量 左移一位加一（newCapacity = (oldCapacity << 1) + 1）为新的容量
初始化容量不同。HashMap 的初始化大小为 16，HashTable 的初始化大小为 11。二者的初始化负载因子均为 0.75
静态属性
/**
* The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* 用于调用含容量的构造参数时，判断入参是否大于最大容量
* 入参必须是小于等于 2^30 的 2 的次幂
* 为什么不是 1 << 31 呢？因为最开始的一位是代表符号位，不参与计算
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* The load factor used when none specified in constructor.
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* 用于对树节点的阈值，而非数组。当一个桶内链表的长度达到 8 时，再次插入一个相同散列的对象就会将桶结构演变为树结构。
* 如果树的值小于等于 6 ，那么就会由树结构变换为桶结构（在每次的 remove 方法时），如果太小就执行非树化（ TreeNode.untreeify() ）方法
* 为什么是 8 呢？
* 首先一个 treeNode 的大小就普通 Node 节点的2倍，在 resize 的过程中，会重新散列结果。
* 通过 p.hash & oldCap == 0 来确定扩容两倍之后，是在高位还是地位。因为扩容 2 倍，相当于左移一位
*/
static final int TREEIFY_THRESHOLD = 8;
/**
* 只会在 resize 的时候去使用，在 split 方法中，会去判断，如果当前的树节点小于 6，就会执行去树化方法，而非拆分为上树结构和下树结构
*/
static final int UNTREEIFY_THRESHOLD = 6;
/**
* 哈希表的最小树化容量。
* 如果一个桶的最大长度达到了 TREEIFY_THRESHOLD，但是数组的长度小于 64，那么就会去扩容，然后重新散列，而非树化。
*/
static final int MIN_TREEIFY_CAPACITY = 64;
为什么最大化树阈值为8？
首先一个 treeNode 的大小就普通 Node 节点的2倍，在 resize 的过程中，会重新散列结果。
这个 key 值不能过大，链表的长度过大，也会影响查询速度。这个 key 也不能过小，过小的话，树化所带来的内存消耗也是不小的。假设 m 最大化树阈值为 k，也就是同一个 key 哈希冲突的最大值。问题就可以转换为简单的泊松分布，经过计算，是符合参数位 0.5 的泊松分布。
经过推算，当 k > 8 时，概率就无限接近于 0 ，可以说是忽略不计。
当选择 8 时，既满足了最大化的链表长度，又找到了最小化的扩容或树化长度。（冲突导致地链表长度为 9 的概率几乎为0，如果有了就进行扩容，这样的代价是最小的）。
为什么由树转为链表的阈值为6？
/**
* If the current tree appears to have too few nodes, the bin is converted back to a plain bin. (The test triggers somewhere between * 2 and 6 nodes, depending on tree structure).
**/
测试阶段的最好效果是在 2 和 6 之间的某处，所以小于6时，就可以直接转为链表
为什么最小化树桶容量为64？
为了更好地解决扩容和树化的冲突，该值必须大于 4 * TREEIFY_THRESHOLD = 32， HashMap 的整个容量计算必须是二的倍数，所以最近的值为 64
构造方法
// 如果
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
// 阈值则是给定的表的大小
this.threshold = tableSizeFor(initialCapacity);
}
// 只有容量的构造参数
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
HashMap 在初始化的时候一定要给初始化容量，这样可以减少扩容带来的影响，因为每次扩容就要重新散列，如果数据太多的话，那么重新散列所带来的时间耗费也是巨大的。之所以在强调一下只是想介绍下构造方法中的 tableSizeFor 方法。
// 返回给定容量的最近的 2 的次幂数
static final int tableSizeFor(int cap) {
int n = cap - 1;
/**
* 将 n 与它的右移 1 位、2 位、 4 位、8 位、16 位后的结果取余并加 1 返回
* 举个例子：加入初始化容量为 5（16 进制数据为 100 ）
* 1、n | n >>> 1 = 100 | 010 = 110 = 6
* 2、n | n >>> 2 = 110 | 001 = 111 = 7
* 3、n | n >>> 4 = 111 | 000 = 111 = 7
* 4、n | n >>> 8 = 111 | 000 = 111 = 7
* 5、结果同上
*/
n |= n >>> 1; // n = n | n >>> 1; 将 n 与 n >>> 1 （n 右移 1 位）
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
// 那么 n 的结果最后就为 7 + 1 = 8。也就是离 4 最近的 2 次幂
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
所以在初始化容量的时候，相信也有一定的策略，如果数据不会超过 8 ，那么初始化给 4 < n <= 8 即可。其他结果依此类推。
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;
}
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;
}
}
TreeNode 节点
// 部分代码，当 HashMap 的数据结构变为 Tree 时所存放的 Node 节点
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);
}
/**
* Returns root of tree containing this node.
*/
final TreeNode<K,V> root() {
for (TreeNode<K,V> r = this, p;;) {
if ((p = r.parent) == null)
return r;
r = p;
}
}
}
put 操作
HashMap 的 put 操作是实现的 Map 接口的 put 方法，并且允许 key、value 为 null 的，真正执行的方法为 putVal。
public V put(K key, V value) {
// 会先将 key 的 hash计算出来，对 hash 的分析在下面
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
/**
* HashMap 一共有三次扩容
* 1、当 table 数组为空时，会初始化一次
* 2、当桶的散列对象过多时，也就是链表的长度大于 8 时，并且数组的长度小于最小树化容量（64）时，会触发一次
* 3、当 HashMap 中 key-value 映射数量超过阈值（capicity * loadFactor）时，会触发一次
*/
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
// 如果与操作计算之后的索引位置或者桶的位置没有对象时（没有出现 hash 冲突时），直接添加新 Node
tab[i] = newNode(hash, key, value, null);
else {
// 如果索引位置出现元素/桶内元素非空的情况（出现 hash 冲突）
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
/**
* 1、首先判断二者的 hash 值是否相同，如果 hash 相同，并且 key 也相同。那么就执行覆盖，将该位置的元素替换掉。
* 2、其次会去判断当前桶的结构是否已经演变为了树，如果是，则执行 插入树节点的逻辑（putTreeVal）
* 3、非树结构，而且二者 hash 值不同，那么此时就要演变为链表。
* 3.1 JDK 1.8 之后的链表插入采用的是尾插法，会首先判断 Node.next 是否为空，如果为空，则直接将 Node.next 指向新节点。
* tip：JDK 1.7 的时候会首先拿当前节点的自身去比较，去判断二者的 hash 和 key 是否一致，从而依次向下比较。也就是头插法。 * 头插法在并发情况下扩容会触发死循环，这个会在末尾讲述。
* 3.2 如果插入后的大小变为了 TREEIFY_THRESHOLD（成为树的阈值为 8），会将桶的数据结构变为树。但是变树并不是这一个条件约束。
* 在 treeifyBin 中会判断如果当前数组（table）的长度 < MIN_TREEIFY_CAPACITY（最小的树化容量为 64）
* 则会执行 resize() 而非树化。
*/
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;
// 如果没有做只有当不存在时才插入的限制，或者旧值为 null。会执行覆盖结果。
if (!onlyIfAbsent || oldValue == null)
e.value = value;
// 执行 linkedHashMap 的钩子函数
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
// 执行 linkedHashMap 的钩子函数
afterNodeInsertion(evict);
return null;
}
put 方法的时间复杂度分为一下几种情况
1、没有 hash 冲突。这是最好的一种情况，时间复杂度为 O(1)
2、出现 hash 冲突，但未演变为树。此时的时间复杂度为 O(n)
3、出现 hash 冲突，并且演变为了树。此时的时间复杂度为 O(logN)
TreeNode 的 put
每个数的 root 节点就是一个桶的第一个节点，树在左旋或右旋的过程中可能会丢失root，但是通过 TreeNode.root() 进行恢复父链接（for 循环递归找到 parent 不为 null 的节点）
插入逻辑：首先遍历 root 节点
1、通过当前 TreeNode 节点的 hash 与 targetTreeNode 的 hash 相比较，如果目标节点的 hash 值较小，则插入左子树，否则插入右子树
如果 hash 值相等时，会通过 String 、 Comparable 、identitiyHashCode 进行比较，直到比较出大小
2、如果当前节点的目标左子树或右子树为空，则便利它的左子树或右子树
3、知道能够插入时，执行 balanceInsert（内部包含满足平衡时树所做的左旋或右旋），最后将 root 移到桶的第一个节点
平衡：每一条从根节点到叶子节点路径的长度都相等
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;
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(tab, balanceInsertion(root, x));
return null;
}
}
}
红黑树左旋
红黑树是一种特殊的二叉搜索树，必须满足以下几个特性:
-
每个节点或是黑色或是红色;
-
根节点是黑色;
-
每个叶节点是黑色（叶节点为空节点）;
-
如果一个节点是红色，则它的子节点必须是黑色;
-
从一个节点到该节点的所有叶节点的路径包含相同数目的黑色节点。
以上规则能满足：最长路径不大于最短路径的二倍，避免了二叉树插入的线性问题
逻辑：
红黑树的左旋是相对红节点来说的
红黑树可以变相使用 2-3-4 树理解，当不满足条件是，会进行分裂，两个子节点为红色，父节点为黑色。
当满足子节点为红色，父节点为黑色时，又会触发变色逻辑。父节点变为红色，子节点变为黑色。这就满足了特性3、4
总结为：逆时针旋转两个节点,使得父节点被自己的右孩子取代，而自己却成为了自己的左孩子，原子节点的左孩子，变成了自己的右孩子
红黑树右旋
与左旋相反
红黑树变色
如果一个节点与两个字节点的连接为红色，与父节点的连接为黑色。通过变色。两个与子节点的连接变成黑色，与父节点的连接变成红色
resize 方法
扩容前后容量的对比
初始化时：如果设定了初始化容量大小，则 newCap = 阈值，否则就是默认的 16
如果是链表大于 8 或者超过了阈值时，newCap = oldCap << 1，同时 newThr = oldThr << 1 （但当容量小于默认值 16 时除外，直接取原来的二倍会比 newCap * loadfactor 大，此时会计算二者的乘积，float 强转为 int 类型）例如：2 扩容至 4，通过负载因子和新容量的乘积，得出阈值为 3。直接由原阈值扩容 2 倍为 2，会小于3.
非链表扩容
只是简单的重新散列，hash 和 数组下标进行 & 运算
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
链表的扩容
e.hash & oldCap 目的是为了计算当前 Node 在扩容之后散列的数组下标是高位还是低位。
1、结果为 0 代表 Node 对象会被散列到低位，因为扩容是二进制扩容，也就是左移 1 位，与操作是 1 和 1 结果为 1。根据位运算不足补 0 原则，结果为 0 时，转换为 10 进制，索引自然比 1/2 小。
2、反之依然，如果不为 0 代表最高也为 1，索引自然比 1/2 大，所以放在了高位。同时为了保证顺序，分为了两个链表 hiHead 和 loHead
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
// 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) {
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;
}
}
}
树化的扩容
e.hash & bit（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;
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) {
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);
}
}
}
树化的过程
当某个桶的长度大于8并且桶数组的长度大于64时，就执行树化。首先将 Node 节点转换为 TreeNode 节点，将整个链表组合起来，然后对 head 进行树化。
树节点是有序的，其中 treeNode 左右节点的排序规则为：
1、key 的 hash 值大的在左边，反之在右边
2、如果值相等
1） key 对象没有实现 Compareble 接口，那么就默认二者相等，进行平局拆分顺序
2）key 实现了，但是 key 的父节点没有实现，那么此时也进行平局拆分（首先比较类名，如果还不相等，就返回 key 原始的 hashCode 比较，小于相等就返回 -1，否则就返回 1），判断当前节点在父节点的子节点的位置
tip：key 的 hash 是高 16 位与 低 16 位异或的结果，key 的 hash 散列算法如此
3）如果可以使用 Compareble 比较，那么就返回比较后的结果作为左子树或者右子树
注：树节点插入的排序规则与此逻辑一致
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);
}
final void treeify(Node<K,V>[] tab) {
TreeNode<K,V> root = null;
for (TreeNode<K,V> x = this, next; x != null; x = next) {
next = (TreeNode<K,V>)x.next;
x.left = x.right = null;
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);
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);
}
hash 散列
JDK 1.8 之后 hash 散列带来了性能上的提升，高 16 位参与进了 hash 散列，将高 16 位与 低 16 位进行异或运算（扰动函数），从而使哈希冲突概率降到最低。
static final int hash(Object key) {
int h;
// 高 16 位与低 16 位进行异或运算
/**
* 为什么要采用异或，而不是其他运算呢？
* JVM 层面常用的有四种位运算：与、非、或、异或。每种位运算计算之后的概率不同
* 与（&）：同为 1 才为 1 。那么位运算产生 1 的概率为 25%，0 的概率为 75%，1 和 0 的概率不同，无法做到平衡散列。
* 非（~）：在原位上去反，1 则为 0 ，0 则为 1 。这种方式对解决哈希冲突没有帮助，所以不采用。
* 或（|）：有 1 则为 1 。那么位运算产生 1 的概率为 75%，0 的概率为 25%，1 和 0 的概率同样不同，也无法做到平衡散列
* 异或（^）：不同为 1 相同为 0 。那么位运算产生 1 的概率为 50%，0 的概率为 50%。这样概率相同，能够一定程度上解决哈希冲突
*/
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
JDK 1.8 扩容之后重新散列为什么不需要重新计算 hash 值？而 JDK 1.7 需要？
JDK 1.8 的链表扩容之后的重新散列操作，采用的是将 Node 节点的 hash 值和老容量做与运算。这样只需要关注最高位是 1 或者 0 就确定该节点在新的桶索引下标。举个例子：假如扩容前容量为 8 ，扩容后容量则变为 16 。在进行重新排序时，会依次遍历所有的原数组桶，如果满足链表数据结构，此时将节点的 hash 值同 8（1000） 做与运算，假如节点的 hash 值为 6（110），此时就相当于 1000 & 0110 = 0 ，放到低8位；假如节点的 hash 值为 14 （01110），相当于 01110 & 01000 = 1000 != 0，放到高 8 位，在最后会将低 8 位形成的链表放到新数组的原索引位置（假如为 1 ），高 8 位形成的链表数据放到新数组的新索引位置（此时为 9 ）。然后进行下一个索引位置的桶重新排列。
if (oldTab != null) {
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)
// 树则采用的是分割，也是将 hash 值与旧容量做与操作
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
// 低 8 位的链表
Node<K,V> loHead = null, loTail = null;
// 高 8 位的链表
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
// hash 值和 8 进行与操作
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);
// 将低 8 位形成的链表放到索引为 j（exp：1） 的位置
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// 将低 8 位形成的链表放到索引为 j + oldCap（exp：9） 的位置
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
最后
以上就是傲娇小懒猪为你收集整理的万字深入理解 HashMap 源码，分析解读树化和非树化过程 HashMap HashMap的全部内容，希望文章能够帮你解决万字深入理解 HashMap 源码，分析解读树化和非树化过程 HashMap HashMap所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复