ArraryList是怎样进行扩容的

  • Post author:
  • Post category:其他



概述:


arrarList默认大小是10,当集合个数大于容量的时候,就会以1.5倍容量去进行扩容,如果还不够大就在扩容后的1.5倍再扩容。扩容后要对原来的集合进行cope到新的集合中。

(在add()方法中调用确保内部容量方法,传入参数当前元素个数加一,当它大于实际数组大小的时候就调用grow()方法进行扩容。扩容是右移一位,进行扩容1.5倍,不够再进行扩容,通过copeof()方法进行数组的复制。)


详细:


为了说明说明这个问题,我们直接来看ArrayList的源码。

首先看ArrayList中的add方法

  public boolean add(E e) {
        ensureCapacityInternal(size + 1); 
        elementData[size++] = e;
        return true;
    }

从add方法中可以看到,它首先调用了一个ensureCapacityInternal方法,然后再将新的元素加到数组末尾,最后size + 1;

size表示的是执行添加之前的元素个数,并非ArrayList的容量,容量应该是数组elementData的长度

其中这个ensureCapacityInternal的作用就是判断容量是否足够,如果不够,则进行扩容。

那我们再去看以下这个ensureCapacityInternal方法

  private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

可以看到在这个方法中调用了两个其他的方法,那我们在一个一个去看一下

首先是calculateCapacity方法

private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }

可以看到这个方法首先进行了一个判断,如果elementData为空的话,就取DEFAULT_CAPACITY(默认值为10)和minCapacity(即上面传过来的size + 1)中的较大值,如果不为空,则直接返回minCapacity;

然后我们再回头去看`ensureExplicitCapacity“方法

  private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

在这个方法中,我们判断了elementData.length即数组的长度是否小于我们所需的最小容量minCapacity,如果小于这个容量,我们就调用grow方法进行扩容,并且我们可以看到,这个过程是有可能发生溢出的。

让我们一起来看看grow方法的源码

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

可以看到在这个方法中,它创建了一个名为newCapacity的变量,且这个变量的大小为数组长度的1.5倍。然后grow方法将newCapacity和 minCapacity进行比较,如果newCapacity还是小于minCapacity的话,就将minCapacity的值赋给newCapacity。最后将原来数组的元素拷贝到一个新的,大小为newCapacity的数组中。

但是当newCapacity的值大于MAX_ARRAY_SIZE即ArrayList的最大长度的时候,就会调用hugeCapacity方法进行进一步处理。

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

在hugeCapacity方法中,它先对minCapacity进行了判断,如果minCapacity小于0,则抛出OutOfMemoryError异常。若不满足条件,就比较minCapacity和MAX_ARRAY_SIZE的大小,若大于,就返回Integer的最大值(0x7fffffff),若不大于,则返回MAX_ARRAY_SIZE.

至此,ArrayList的扩容过程就结束了。

最后有几个细节

在JDK8中,使用无参构造方法,它的默认容量是10

新的数组容量是原来的1.5倍或所需的最小大小minCapacity,此时的minCapacity一定大于原来数组的1.5倍数

ArrayList最大容量不超过Integer的最大值



版权声明:本文为whlqunzhu原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。