ArrayList扩容机制详解

简介

ArrayList 是 java 集合框架中比较常用的数据结构了。继承自 AbstractList，实现了 List 接口。底层基于数组实现容量大小动态变化。允许 null 的存在。同时还实现了 RandomAccess、Cloneable、Serializable 接口，所以ArrayList 是支持快速访问、复制、序列化的。

扩容机制

1.1首先，创建一个ArrayList对象

ArrayList arrayList = new ArrayList();

底层原理：调用无参构造器

 public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

常量DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的值为“{}”，为空数组

 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

即使用ArrayList()创建ArrayList对象时，并没有初始化底层数组elementData，等到调用add(E e) 方法的时候再初始化elementData，这种”懒加载”模式可以节省内存。

1.2 调用add(E e) 方法

 arrayList.add("test");

执行add方法，添加元素。

public boolean add(E e) {
        // 确认elementData容量是否足够
        ensureCapacityInternal(size + 1);  // 第一次调用add()方法时，size=0
        elementData[size++] = e;
        return true;
    }

先调用ensureCapacityInternal(int minCapacity) 方法,对数组容量进行检查，不够时则进行扩容。

private void ensureCapacityInternal(int minCapacity) {
    // 如果elementData为"{}"即第一次调用add(E e)，重新定义minCapacity的值，赋值为DEFAULT_CAPACITY=10
    // 即第一次调用add(E e)方法时，定义底层数组elementData的长度为10
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
	// 判断是否需要扩容
        ensureExplicitCapacity(minCapacity);
    }

ensureExplicitCapacity(minCapacity) 判断是否需要扩容

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

// 第一次进入时，minCapacity=10,elementData.length=0,对数组进行扩容
// 之后再进入时，minCapacity=size+1，elementData.length=10(每次扩容后会改变)，
// 需要minCapacity>elementData.length成立，才能扩容
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

grow(minCapacity) 对数组进行扩容

private void grow(int minCapacity) {
        // 将数组长度赋值给oldCapacity
        int oldCapacity = elementData.length;
    	// 将oldCapacity右移一位再加上oldCapacity，即相当于newCapacity=1.5oldCapacity(不考虑精度损失)
        int newCapacity = oldCapacity + (oldCapacity >> 1);
    	// 如果newCapacity还是小于minCapacity，直接将minCapacity赋值给newCapacity
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
    	// 特殊情况：newCapacity的值过大，直接将整型最大值赋给newCapacity，
	// 即newCapacity=Integer.MAX_VALUE
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // 将elementData的数据拷贝到扩容后的数组
        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;
    }

结论：

使用ArrayList()创建ArrayList对象时，不会定义底层数组的长度，当第一次调用add(E e) 方法时，初始化定义底层数组的长度为10，之后调用add(E e)时，如果需要扩容，则调用grow(int minCapacity) 进行扩容,长度为原来的1.5倍。

ArrayList还有有参构造器：ArrayList(int initialCapacity)和ArrayList(Collection<? extends E> c)，前者创建可以指定初始容量的集合，后者创建一个包含指定collection元素的集合，两者的底层数组初始化和扩容机制与上述ArrayList()一样，且添加方法add(int index, E e)和add(E e)的扩容机制一样。

Arraylist扩展内容

------本页内容已结束，喜欢请分享------

感谢您的来访，获取更多精彩文章请收藏本站。