JDK1.8 HashMap 扩容 对链表(长度小于默认的8)处理时重新定位的过程

关于HashMap的扩容过程,请参考源码或百度。

我想记录的是1.8 HashMap扩容是对链表中节点的Hash计算分析.

对术语先明确一下:

hash计算指的确定节点在table[index]中的链表位置index,不是节点的hash值。

 Node<K,V> loHead = null, loTail = null; //这两个是记录重新hash计算后仍在原位置(设为index)的节点
Node<K,V> hiHead = null, hiTail = null; //这两个是记录重新hash计算后在原位置加上原容量 的位置的节点(index + old capacity)

那么问题来了 , 怎么就确定 扩容前的 链表节点  在 扩容后的位置 是 当前位置或者+old capacity的位置 ?

先看 put 节点时 对key查找在table位置的计算方法,在putVal中有这么一行(红色部分):

 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)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {

其中 (n-1) & hash 就是在table中的位置(n即capacity),暂时将这个记为 oldIndex = (n-1) & hash (公式1);

再来看扩容时的代码,代码有点多,我删去一些不影响理解的还是看红色部分:

 final Node<K,V>[] resize() {
Node<K,V>[] 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;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
} threshold = newThr; Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
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)
((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) {
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; (公式4)
}
}
}
}
}
return newTab;
}

为了简单(二进制可以短点)起见,以 oldCapacity = 8 为例,扩容后 capacity = 16

newCap = oldCap << 1 : 新的容量capacity= 8<<1 = 16
newTab[e.hash & (newCap - 1)] , 红色部分即 原节点在 新table中的位置 , 暂时记为 newIndex = e.hash & (newCap - 1) (公式2)

hoHead,hoTail,hiHead,hiTail 不多说,上面有说明。 那么 这个下面这个判断条件,就决定了节点在扩容以后的位置

(e.hash & oldCap) == 0  (公式3)

最后再看是如何分配者两个链表的,一个原位置,一个j+oldCap位置。

下面分析是如何这么确定的:

总结上面所描述的,有下列几个变量

oldCapacity 用 n 代替

oldIndex = (n-1) & hash (公式1)

newIndex = (n*2 -1) & hash (公式2)

condition = n & hash (公式3)

几个值之间的关系:

if(condition == 0) 那么  newIndex 等于 oldIndex

else                              newIndex 等于 oldIndex + n

里面有一个隐含条件: n 是 2 的整数倍(也是满足关系的必要条件)

当n = 8 时, 其二进制 b1 = 1000 ,  减去1 之后(7) 得到的二进制 b2 = 0111

扩容后, 即n*2 = 16的二进制是 10000 , 减去1之后(15) 得到的二进制是 b3 = 01111

假如hash的二进制是hash = 10111 ,

  10111 &  1000 (b1)  = 0     == conditon

  10111 &  0111 (b2)  = 111  == oldIndex

  10111 & 01111 (b3) = 111  == newIndex

  可以发现,   当 condtion 为0 时, hash的二进制 的 第4位 必然为 0 ,高位无所谓什么值 ,

hash &b2 (111) 结果必然是hash低三位的值,hash & b2 (1111) ,由于hash第4位为0 ,那么结果必然仍是hash低三位的值。

  所以,当condition为0时, newIndex 必然等于 oldIndex

假如hash的二进制是hash = 11111,

    11111 & 1000 (b1) = 1000      == condition = 8

    11111 &  0111 (b2) = 00111    == oldIndex = 7

    11111 & 01111 (b3) = 01111    == newIndex = 15

     发现了吗? oldIndex 和 newIndex 差的就是 一个第 4 位的1 ,那么这个1 就是 2^4 = 8 , 也就是 oldCapacity (2^4) 的值。

无论多长的hash值,关键的一个二进制 在 第 x 位 (2^x = oldCapacity), 也就是这一位决定了 扩容前后的位置。

由于这样计算呢, java1.8中的HashMap 可以 不用在扩容的时候 一直往头节点插 (有环回的逻辑所以在多线程扩容的时候才会出现 闭环链 ),

1.8中对链表只有往后添加节点,没有环回的逻辑, 也就不可能在多线程的时候出现闭环链。

虽然时间复杂度是一样的,但是更机智了。

上一篇:Spark mllib多层分类感知器在情感分析中的实际应用


下一篇:django 模型层(2)