手记

Java 8 ArrayList hugeCapacity 函数与 MAX_ARRAY_SIZE

1、背景

今天有一个朋友问到一个为什么 ArrayList 源码扩容方法中,数组长度最大值是 MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8 的问题(真的是MAX_ARRAY_SIZE? )。

并给出下列截图:

2、别急,让我们捋一捋

我们先搞清楚这里几个关键变量的含义:

  • min capacity 这次扩容最小需要的容量
  • old capacity 扩容前原始数组容量
  • newCapacity = oldCapacity + (oldCapacity >> 1) 是预计要扩容到的容量

之前讲过,看源码看不太懂时要多看注释。

    /**
     * The maximum size of array to allocate.
     * Some VMs reserve some header words in an array.
     * Attempts to allocate larger arrays may result in
     * OutOfMemoryError: Requested array size exceeds VM limit
     */
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

这里说 Some VMs reserve some header words in an array. 即有些虚拟机会在数组中保存 header words 头部字。

PS: 数组有点特殊性,数组对象要额外存储数组元素长度在头部,少了这8个长度可能与此有关。

尝试分配大于 MAX_ARRAY_SIZE 长度的数组会导致 OOM (换句话说,超过了该虚拟机的数组长度限制)。

grow 函数的目的是:提高容量以便至少满足最少 minCapacity 容量!!

    /**
     * Increases the capacity to ensure that it can hold at least the
     * number of elements specified by the minimum capacity argument.
     *
     * @param minCapacity the desired minimum capacity
     */
    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

有些虚拟机大于 MAX_ARRAY_SIZE (Integer.MAX -8 )就容易OOM (注意只是有些)

注意前提是 new - MAX_ARRAY_SIZE >0 就意味着 正常情况下新的扩容长度大于了 MAX_ARRAY_SIZE。
此时最大可以扩容到 Integer.MAX,因为数组长度是整数。

因为数组理论上长度就是 Integer.MAX_VALUE 个别JVM 设计上的问题 咱们可以尽量照顾下 但并不是说一定因为个别JVM 就一定不让扩容到 整数最大值长度。

如果再满了 那么对不起 直接到将数组长度设置为整数最大值, 爱咋咋地!

因此,数组最大容量是 Integer.MAX_VALUE (提问的说法有问题) ,在图示情况扩容到 MAX_ARRAY_SIZE 是为了扩容到 MAX_ARRAY_SIZE以上长度就OOM的虚拟机可以尽量不OOM,如果还放不下没办法,对不起了大兄弟!

3 Learn more

你以为这就完了吗?
其实上面的问题并不是重点。
看这这段代码最重点在:
int newCapacity = oldCapacity + (oldCapacity >> 1);

为什么不是扩容到 minCapacity +1?
其实是预先申请这么多的容量,避免频繁扩容,采用了空间换时间思想。

Redis 的动态字符串和这个有点类似,只不过扩容策略有差异 。

那么为什么Redis 动态字符串扩容会有两个处理方式?为什么大于1M 每次增加1M 而且有最大长度限制呢?
1 首先想下 Redis 和 Java中的ArrayList的使用场景。
Redis 通常用作缓存,而且失效时间相对较长(少则几秒钟,多则几分钟,几个小时等)。而ArrayList 通常在某个函数中用,一般来说生命周期很短,出栈后就可以回收。
2 Redis 为啥要有最大值限制。可能是因为通常和使用者不在同一个服务器上,需要通过网络进行传输,如果很大,传输很容易超时,而且Redis 主任务为单线程,很容易阻塞其他任务的执行。
3 小于1M

4、总结

之前一直提倡看源码一定要重视看注释,当大家 JDK 或者其他开源项目源码有困惑时一定要重视看源码。
同样地,当我们写代码时,有些情况容易让别人困惑时,一定要加上注释。

此外,读源码一定要像这位同学一样,多一些思考。
读源码要读源码的设计理念,体现出来的设计思想。
读源码时建议先猜想后验证,即猜想可能的原因,然后再去分析,这样学到更多。


欢迎关注本人的慕课专栏:

2人推荐
随时随地看视频
慕课网APP