为什么 HashMap 长度必须是 2 的 n 次幂

Java 面试 大约 725 字

2 的 n 次幂

1后面n0

如:

2^3 = 1000

2^6 = 1000000

取索引的算法

取索引的算法是对hash值取模:hash%length,而直接取模%性能比位运算差,所以借助2n次幂减去1并做与运算,就等价于取模:hash&(length-1)

JDK1.8 后扩容

JDK1.8后的扩容也是有一定技巧,直接和原先长度进行与运算,如果为0,还是在当前所以位置,如果不等于0(等于1),索引就等于当前索引加上原先数组长度的位置。

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);

减少哈希碰撞

哈希碰撞就是不同的对象算出来的哈希值一样了,让数组均匀分配。

阅读 112 · 发布于 2021-10-22

————        END        ————

扫描下方二维码关注公众号和小程序↓↓↓

扫描二维码关注我
昵称:
随便看看 换一批