Java Map 扩容时,为什么推荐是2的幂

JAVA herman 784浏览
公告:“业余草”微信公众号提供免费CSDN下载服务(只下Java资源),关注业余草微信公众号,添加作者微信:codedq,发送下载链接帮助你免费下载!
本博客日IP超过2000,PV 3000 左右,急需赞助商。
极客时间所有课程通过我的二维码购买后返现24元微信红包,请加博主新的微信号:codedq,之前的微信号好友位已满,备注:返现
受密码保护的文章请关注“业余草”公众号,回复关键字“0”获得密码
所有面试题(java、前端、数据库、springboot等)一网打尽,请关注文末小程序
视频教程免费领

关于 Java 集合的面试题网上也有很多,很多都是基于源码的解毒。但有时候面试官会出其不意,问一些设计方面的问题。

比如,我们今天标题要讨论的,Java 中常见的 HashMap 等 Map 类集合,在扩容时,为什么是 2 倍,而不是 1.5 倍,3 倍,10 倍等。这么设计有什么意义吗?

当 map 中包含的 Entry 的数量大于等于 threshold = loadFactor * capacity 的时候,且新建的 Entry 刚好落在一个非空的桶上,此刻触发扩容机制,将其容量扩大为 2 倍。

这个 2 是有一些特殊的意义的。我们先从一些源码中看出这些设计的巧妙之处。

/**
 * The default initial capacity - MUST be a power of two.
 */
static final int DEFAULT_INITIAL_CAPACITY = 16;
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);

    // Find a power of 2 >= initialCapacity 找到一个大于等于初始容量的且是2的幂的数作为实际容量
    int capacity = 1;
    while (capacity < initialCapacity)
        capacity <<= 1;

    this.loadFactor = loadFactor;
    threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
    table = new Entry[capacity];
    useAltHashing = sun.misc.VM.isBooted() &&
            (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
    init();
}

通过以上我们知道 HashMap 的容量必须是 2 的幂,那么为什么要这么设计呢?答案当然是为了性能。在 HashMap 通过键的哈希值进行定位桶位置的时候,调用了一个 indexFor(hash, table.length); 方法。

/**
 * Returns index for hash code h.
 */
static int indexFor(int h, int length) {
    return h & (length-1);
}

可以看到这里是将哈希值 h 与桶数组的 length-1(实际上也是 map 的容量-1)进行了一个与操作得出了对应的桶的位置,h & (length-1)。

但是为什么不采用 h % length 这种计算方式呢?

那是因为 Java 中的 %、/ 操作比 & 慢 10 倍左右,因此采用 & 运算会提高性能。

通过限制 length 是一个 2 的幂数,h & (length-1) 和 h % length 结果是一致的。这就是为什么要限制容量必须是一个 2 的幂的原因。

举个简单的例子说明这两个操作的结果一致性:

假设有个 hashcode 是 311,对应的二进制是(1 0011 0111)。

length 为 16,对应的二进制位 (1 0000)。

  • %操作:311 = 16*19 + 7;所以结果为7,二进制位(0111);
  • &操作:(1 0011 0111) & (0111) = 0111 = 7, 二进制位(0111)

1 0011 0111 = (1 0011 0000) + (0111) = (12^4 + 1 2^5 + 02^6 + 02^7 + 12^8 ) + 7 = 2^4(1 + 2 + 0 + 0 + 16) + 7 = 16 * 19 + 7; 和 % 操作一致。

如果 length 是一个 2 的幂的数,那么 length-1 就会变成一个 mask, 它会将 hashcode 低位取出来,hashcode 的低位实际就是余数,和取余操作相比,与操作会将性能提升很多。

参考资料

业余草公众号

最后,欢迎关注我的个人微信公众号:业余草(yyucao)!可加作者微信号1:xmtxtt(5000人已满),微信号2:xttblog(5000人已满),微信号3:codedq(超3800)。备注:“1”,添加博主微信拉你进微信群。备注错误不会同意好友申请。再次感谢您的关注!后续有精彩内容会第一时间发给您!原创文章投稿请发送至532009913@qq.com邮箱。商务合作也可添加作者微信进行联系!

本文原文出处:业余草: » Java Map 扩容时,为什么推荐是2的幂