ArrayList扩容机制-java黑洞网

本站消息

站长简介/公众号

出租广告位,需要合作请联系站长

我是小豆丁

574

文章

278096

访问

+关注

分类

暂无分类

日期归档

2024-11(1)

ArrayList扩容机制

发布于2021-05-29 21:11 阅读(1036) 评论(0) 点赞(4) 收藏(1)

ArrayList简介：

ArrayList实现了List接口它是一个可调整大小的数组可以用来存放各种形式的数据。并提供了包括CRUD在内的多种方法可以对数据进行操作但是它不是线程安全的，ArrayList按照插入的顺序来存放数据。

1.成员变量


    // 默认给定的初始容量
    private static final int DEFAULT_CAPACITY = 10;
 
    // 无参构造器中所使用到的空数组实例
    private static final Object[] EMPTY_ELEMENTDATA = {};
 
    // 有参构造器中所使用到的空数组实例
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
 
    // 数据元素集合
    transient Object[] elementData;
 
    //当前数组的长度
    private int size;

2.构造方法


   /**
    * 构造一个初始容量为10的空列表
    */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }   
    
   /**
    * 构造一个具有指定容量大小的空列表
    */
    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }
   
   /**
    * 构造一个包含指定集合的元素的列表
    */
    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

3.扩容机制

ArrayList扩容的核心从ensureCapacityInternal方法说起。

可以看到前面介绍成员变量的提到的ArrayList有两个默认的空数组：

DEFAULTCAPACITY_EMPTY_ELEMENTDATA：是用来使用默认构造方法时候返回的空数组。如果第一次添加数据的话那么数组扩容长度为DEFAULT_CAPACITY=10。

EMPTY_ELEMENTDATA：出现在需要用到空数组的地方，其中一处就是使用自定义初始容量构造方法时候如果你指定初始容量为0的时候就会返回。

从下面可以看到如果是使用了空数组EMPTY_ELEMENTDATA话，那么不会返回默认的初始容量。


//判断当前数组是否是默认构造方法生成的空数组，如果是的话minCapacity=10反之则根据原来的值传入下一个方法去完成下一步的扩容判断
    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }
    //minCapacitt表示修改后的数组容量，minCapacity = size + 1 
    private void ensureCapacityInternal(int minCapacity) {
        //判断看看是否需要扩容
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

下面谈谈ensureExplicitCapacity方法（modCount设计到Java的快速报错机制后面会谈到），可以看到如果修改后的数组容量大于当前的数组长度那么就需要调用grow进行扩容，反之则不需要。


//判断当前ArrayList是否需要进行扩容
    private void ensureExplicitCapacity(int minCapacity) {
        //快速报错机制
        modCount++;
 
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

最后看下ArrayList扩容的核心方法grow()，下面将针对三种情况对该方法进行解析：


private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1); // 扩容至1.5倍
        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;
  }

1>当前数组是由默认构造方法生成的空数组并且第一次添加数据。

此时从方法 calculateCapacity中可以看出，minCapacity== 10，当数组长度大于10的时候才会进入到grow方法中进行扩容（按照当前容量的1.5倍进行扩容）；

2>当前数组是由自定义初始容量构造方法创建并且指定初始容量为0。

此时minCapacity == 1，elementData.length == 0，

方法grow中，minCapacity ==1 oldCapacity == 0 newCapacity < 0 =》newCapacity = 1

minCapacity == 2 oldCapacity == 1 newCapacity == 1.5 =》newCapacity = 2

minCapacity == 3 oldCapacity == 2 newCapacity == 3 =》newCapacity = 3

minCapacity == 4 oldCapacity == 3 newCapacity == 4.5 =》newCapacity = 4.5

minCapacity == 5 oldCapacity == 4 newCapacity == 6 =》newCapacity = 6

那么根据下面逻辑可以看到最后数组的容量会从0变成1。根据上述算法前四次扩容每次都 +1，在第5次添加数据进行扩容的时候才是按照当前容量的1.5倍进行扩容。
3>当扩容量（newCapacity）大于ArrayList数组定义的最大值后会调用hugeCapacity来进行判断。如果minCapacity已经大于Integer的最大值（溢出为负数）那么抛出OutOfMemoryError（内存溢出）否则的话根据与MAX_ARRAY_SIZE的比较情况确定是返回Integer最大值还是MAX_ARRAY_SIZE。这边也可以看到ArrayList允许的最大容量就是Integer的最大值（-2的31次方~2的31次方减1）。