探究HashMap源码中最大容量为什么是2的30次方(1＜＜30)?

曾经终败给现在 2023-10-08 15:52 28阅读 0赞

关于HashMap的详解文章请移步：

链接: [HashMap源码研究——源码一行一行的注释  
][HashMap_]

#### 文章目录 ####

*  为什么是30
 *  为什么是1<<30
 *  为什么容量总能是2的次幂
 *  threshold阈值

在阅读hashmap的源码过程中，我看到了关于hashmap最大容量的限制，并产生了一丝疑问。

/**
         * The maximum capacity, used if a higher value is implicitly specified
         * by either of the constructors with arguments.
         * MUST be a power of two <= 1<<30.
         */
        static final int MAXIMUM_CAPACITY = 1 << 30;

为啥最大容量是 1 << 30?超过会怎么办？  
有个面试题：  
**HashMap最大容量是多少？**  
如果你答2的30次方，面试官极有可能追问：  
**真的吗？**  
假的！这是默认的最大阈值容量，实际上是什么样？  
让我们往下看

## 为什么是30 ##

首先是 << 这个操作符必须要理解  
在一般情况下 1 << x 等于 2^x。这是左移操作符，对二进制进行左移。  
右移正好相反，换句话说就是右移缩小两倍，左移扩大两倍  
来看1 << 30。它代表将1左移30位，也就是0010…0

*  int类型是32位整型，占4个字节。
 *  Java的原始类型里没有无符号类型。 -->所以首位是符号位 正数为0，负数为1
 *  java中存放的是补码，1左移31位的为 16进制的0x80000000代表的是-2147483648–>所以最大只能是30

## 为什么是1<<30 ##

那为什么是 1 << 30，而不是`0x7fffffff`即`Integer.MAX_VALUE`

翻译一下大概就是：如果构造函数传入的值大于该数 ，那么替换成该数。  
就是初始化的时候，如果容量超过这个数，就替换成该数  
我们看看构造函数的调用：

public HashMap(int initialCapacity, float loadFactor) {
        
            if (initialCapacity < 0)   //如果初始容量小于0，抛出异常
                throw new IllegalArgumentException("Illegal initial capacity: " +
                                                   initialCapacity);
            if (initialCapacity > MAXIMUM_CAPACITY)  //如果初始容量超过最大容量（1<<32）
                initialCapacity = MAXIMUM_CAPACITY;  //则使用最大容量作为初始容量
            if (loadFactor <= 0 || Float.isNaN(loadFactor))  //如果负载因子小于等于0或者不是数字，则抛出异常
                throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
            this.loadFactor = loadFactor;                //把负载因子赋值给成员变量loadFactor
    
    //调用tableSizeFor方法计算出不小于initialCapacity的最小的2的幂的结果，并赋给成员变量threshold
            this.threshold = tableSizeFor(initialCapacity); 
        }

其中这一句：

if (initialCapacity > MAXIMUM_CAPACITY)
                initialCapacity = MAXIMUM_CAPACITY;

如果我要存的数目大于 MAXIMUM\_CAPACITY，你还把我的容量缩小成 MAXIMUM\_CAPACITY？

别急，继续看：在扩容resize()方法中有一句：

if (oldCap >= MAXIMUM_CAPACITY) {
        
                    threshold = Integer.MAX_VALUE;
                    return oldTab;
    }

在这里我们可以看到其实 hashmap的“最大容量“是`Integer.MAX_VALUE`，即int的最大值  
上面那个面试题知道怎么说了吗，那是默认最大值，如果超过，最大容量其实是int的最大值

## 为什么容量总能是2的次幂 ##

MAXIMUM\_CAPACITY作为一个2的幂方中最大值，这个值的作用涉及的比较广。其中有一点比较重要的是在hashmap中容量会确保是 2的k次方，即使你传入的初始容量不是 2的k次方，tableSizeFor()方法也会将你的容量置为 2的k次方。这时候MAX\_VALUE就代表了最大的容量值。

/**
         * Returns a power of two size for the given target capacity.
         */
        static final int tableSizeFor(int cap) {
        
            int n = cap - 1;      //容量减1，为了防止初始化容量已经是2的幂的情况，最后有+1运算。
            n |= n >>> 1;         //将n无符号右移一位再与n做或操作
            n |= n >>> 2;         //将n无符号右移两位再与n做或操作
            n |= n >>> 4;         //将n无符号右移四位再与n做或操作
            n |= n >>> 8;         //将n无符号右移八位再与n做或操作
            n |= n >>> 16;        //将n无符号右移十六位再与n做或操作
            //如果入参cap为小于或等于0的数，那么经过cap-1之后n为负数，n经过无符号右移和或操作后仍未负 
            //数,所以如果n<0,则返回1;如果n大于或等于最大容量，则返回最大容量;否则返回n+1
            return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
        }

这个方法就是**获取离你容量最近的一个2的次幂**

## threshold阈值 ##

另外还有一点就是threshold，如果对hashmap有一点了解的人都会知道threshold = 初始容量 \* 加载因子。也就是扩容的 门槛。相当于实际使用的容量。而扩容都是翻倍的扩容。那么当容量到达MAXIMUM\_CAPACITY，这时候再扩容就是 1 << 31 整型溢出。所以Integer.MAX\_VALUE作为最终的容量，但是是一个threshold的身份。

[HashMap_]: https://blog.csdn.net/weixin_44688973/article/details/119865191?spm=1001.2014.3001.5502