Java 8 ArrayList hugeCapacity 函数与 MAX_ARRAY_SIZE

明明如月学长

发布于 2021-08-31 11:27:18

1.1K0

发布于 2021-08-31 11:27:18

文章被收录于专栏：明明如月的技术专栏

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 头部字。

对象头可以看这里： https://cloud.tencent.com/developer/article/1413543 https://stackoverflow.com/questions/26357186/what-is-in-java-object-header

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