Java HashMap 扩容数组中单链表的位置变化分析

1 HashMap 扩容数组中单链表部分的源代码

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 & oldCap) 判断key的hash在 原有容量的最高位 是否为1。

• 如果为1，则结果为 原有索引 + 一倍旧的容量 ，得出新元素的索引位置。
• 如果为0，则保持原有索引位置不变。

2 举个例子

2.1 索引位置不变的示例

结果为0的代码示例如下：

/**
 * hashMap resize索引位置判断
 */
@Test
public void hashCodeResize(){

    //扩容前
    //hash map 中key
    String key = "hello-hmcxa-9";
    Integer keyHashCodeNum = hash(key);
    System.out.println(getTwoNum(keyHashCodeNum));

    // hash map 中的容量
    Integer capNum = 16;
    System.out.println(getTwoNum(capNum));

    //扩容操作中， (e.hash & oldCap) 演示
    Integer result = keyHashCodeNum & capNum;
    System.out.println(getTwoNum(result));
}

输出

[10010111, 00111100, 11111010, 01100100]
[00000000, 00000000, 00000000, 00010000]
[00000000, 00000000, 00000000, 00000000]

按位与（&） ：当两个操作数的对应位都为1时，结果为1，否则为0。

2.2 相反的示例

如果将key换成 hello-vskvq-3 ，则此段程序会输出如下内容：

[10000110, 10000000, 01001011, 01110100]
[00000000, 00000000, 00000000, 00010000]
[00000000, 00000000, 00000000, 00010000]

因此可以再一次证明， (e.hash & oldCap) 判断key的hash在 原有容量的最高位 是否为1。

3 公共代码

/**
 *获取二进制字符串
 */
public String getTwoNum(Integer number){
    int width = 32; // 目标宽度
    String binary = Integer.toBinaryString(number);
    String paddedBinary = String.format("%" + width + "s", binary).replace(' ', '0');
    List<String> list = Lists.newArrayList();
    StringBuilder item = new StringBuilder();

    for (int i = 1; i < paddedBinary.length()+1; i++) {
        item.append(paddedBinary.charAt(i-1));
        if (i % 8 == 0) {
            list.add(item.toString());
            item = new StringBuilder();
        }

    }
    return list.toString();
}



final int hash(Object key) {
    inth;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}