Java8HashMap之tableSizeFor

jiezi

5 年前

基本类型：int 二进制位数：32
包装类：java.lang.Integer
最小值：Integer.MIN_VALUE= -2147483648（- 2 的 31 次方）
最大值：Integer.MAX_VALUE= 2147483647（2 的 31 次方 -1）

java 8 中在创建 hashMap 的时候有个构造函数如下：

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

其中 initialCapacity 是初始容量，这个容量经过 tableSizeFor 加工后就变为了大于输入参数且最近的 2 的整数次幂的数，当然如果输入参数大于 2 ³⁰则会返回 2 ³⁰，因为 int 最大是 2 ³¹- 1 不是 2 的倍数，最大的 2 的次方就是 2 ³⁰。

java8 源码如下：

static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

详解如下：

先来分析有关 n 位操作部分：先来假设 n 的二进制为 01xxx…xxx。接着
对 n 右移 1 位：001xx…xxx，再位或：011xx…xxx
对 n 右移 2 为：00011…xxx，再位或：01111…xxx
此时前面已经有四个 1 了，再右移 4 位且位或可得 8 个 1
同理，有 8 个 1，右移 8 位肯定会让后八位也为 1。
综上可得，该算法让最高位的 1 后面的位全变为 1。
最后再让结果 n +1，即得到了 2 的整数次幂的值了。
由于 int 是 32 位，所以 >>>16 便能满足。

而关于为啥要 int n = cap – 1;
用代码解释吧：

输入如下：

16
8

如果不减去 1 得到的结果为 16 显然不对，输入 8 的时候不小于输入结果的最小 2 的次方应该是 8。那么这里减一的意义就是避免这种情况。

参考文章：
Java8—HashMap 之 tableSizeFor()

Java8HashMap之tableSizeFor

首先

java 8HashMap 构造函数

tableSizeFor 解析