ArrayList扩容处理

古城微笑少年丶 2022-04-13 14:12 213阅读 0赞

ArrayList是基于动态数组实现的一个数据结构，如果添加元素时，元素个数超过list的容量大小时，会涉及到扩容。

ArrayList的扩容是如何做的，跟着代码走最容易懂。

/**
         * 添加元素在list尾部
         *
         * @param e 待添加元素
         * @return 返回添加成功标识
         */
        public boolean add(E e) {
            // 确保内部容量增加
            ensureCapacityInternal(size + 1);  // Increments modCount!!
            elementData[size++] = e;
            return true;
        }
    
    
        /**
         * 确保list内部容量可以容纳增加的一个元素
         * 上面方法中给定list的size + 1 作为最小容量大小，因为size <= list容量capacity
         * size + 1 作为容量是绝对可以满足要求的
         */
        private void ensureCapacityInternal(int minCapacity) {
            ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
        }
    
        /**
         * 计算动态数组容量
         * 对于给定的动态数组和最小容量值，计算list需要的容量大小
         */
        private static int calculateCapacity(Object[] elementData, int minCapacity) {
            // 如果动态数组为空
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
                // 则取默认容量10 和 最小容量之间大的一个，作为需要的容量返回
                return Math.max(DEFAULT_CAPACITY, minCapacity);
            }
            // 动态数组非空时，直接反馈传进来的最小容量，因为最小容量已经等于size + 1了
            return minCapacity;
        }
    
        /**
         * 计算明确容量
         * 对于给定的动态数组和最小容量值，计算list需要的容量大小
         */
        private void ensureExplicitCapacity(int minCapacity) {
            // list结构被修改次数加1
            modCount++;
    
            // 如果容量最小值大于动态数组长度，则需要扩容
            if (minCapacity - elementData.length > 0)
                grow(minCapacity);
        }
    
        /**
         * 扩充list容量，确保list至少可以容纳minCapacity个元素
         * @param minCapacity the desired minimum capacity
         */
        private void grow(int minCapacity) {
            // 定义原容量长度
            int oldCapacity = elementData.length;
            // 新容量扩大到原容量的1.5倍，右移一位相关于原数值除以2，加上原容量长度
            int newCapacity = oldCapacity + (oldCapacity >> 1);
            // 第一次存放元素时，minCapacity为10，而通过上面计算出来的newCapacity为0
            if (newCapacity - minCapacity < 0)
                // 这时 取新的容量为minCapacity
                newCapacity = minCapacity;
            // 如果新容量超过最大数组长度
            if (newCapacity - MAX_ARRAY_SIZE > 0)
                // 进行超大容量处理，并将结果作为最大容量
                newCapacity = hugeCapacity(minCapacity);
            // 将原elementData数组元素拷贝到新的容量为newCapacity的数组中
            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无参构造方法默认容量为10
 *  如果添加的元素超出当前list容量，list容量扩充一半
 *  ArrayList最大容量不超过Integer的最大值

代码测试

/**
         * ArrayList容量测试
         * @throws Exception
         * @throws SecurityException
         */
        public static void arrayListCapacity() throws Exception, SecurityException {
        	// 默认容量测试
        	List<Object> list = new ArrayList<Object>();
        	Field size = list.getClass().getDeclaredField("size");
        	Field elementDataField = list.getClass().getDeclaredField("elementData");
        	size.setAccessible(true);
        	elementDataField.setAccessible(true);
        	
        	Object[] elementData;
        	
        	for (int i=0; i<30; i++) {
        		Object o = new Object();
        		list.add(o);
        		if (i==9 || i==10 || i==11 || i==14 || i==15 || i==22 || i==23 ) {
            		elementData = (Object[])elementDataField.get(list);
            		System.out.println("i=" + i + ",size=" + size.get(list) + ",动态数组地址" + elementData + ",elementData=" + elementData.length);
        		}
        	}
        	
        	System.out.println("**********分割线***********");
        	
        	// 指定容量测试
        	List<Object> list2 = new ArrayList<Object>(6);
        	Field size2 = list2.getClass().getDeclaredField("size");
        	Field elementDataField2 = list2.getClass().getDeclaredField("elementData");
        	size2.setAccessible(true);
        	elementDataField2.setAccessible(true);
        	
        	Object[] elementData2;
        	
        	for (int i=0; i<30; i++) {
        		Object o = new Object();
        		list2.add(o);
        		if (i==5 || i==6 || i==9 || i==13 || i==19 || i==28 || i==29 ) {
            		elementData2 = (Object[])elementDataField2.get(list2);
            		System.out.println("i=" + i + ",size=" + size2.get(list) + ",动态数组地址" + elementData2 + ",elementData=" + elementData2.length);
        		}
        	}
        }

运行结果

i=9,size=10,动态数组地址[Ljava.lang.Object;@6d06d69c,elementData=10
    i=10,size=11,动态数组地址[Ljava.lang.Object;@7852e922,elementData=15
    i=11,size=12,动态数组地址[Ljava.lang.Object;@7852e922,elementData=15
    i=14,size=15,动态数组地址[Ljava.lang.Object;@7852e922,elementData=15
    i=15,size=16,动态数组地址[Ljava.lang.Object;@4e25154f,elementData=22
    i=22,size=23,动态数组地址[Ljava.lang.Object;@70dea4e,elementData=33
    i=23,size=24,动态数组地址[Ljava.lang.Object;@70dea4e,elementData=33
    **********分割线***********
    i=5,size=30,动态数组地址[Ljava.lang.Object;@5c647e05,elementData=6
    i=6,size=30,动态数组地址[Ljava.lang.Object;@33909752,elementData=9
    i=9,size=30,动态数组地址[Ljava.lang.Object;@55f96302,elementData=13
    i=13,size=30,动态数组地址[Ljava.lang.Object;@3d4eac69,elementData=19
    i=19,size=30,动态数组地址[Ljava.lang.Object;@42a57993,elementData=28
    i=28,size=30,动态数组地址[Ljava.lang.Object;@75b84c92,elementData=42
    i=29,size=30,动态数组地址[Ljava.lang.Object;@75b84c92,elementData=42

通过测试，可以得出如下结论  
1、ArrayList在存放元素超出现有数组大小时会自动扩容  
2、每次扩容大小为当前容量的一半取(如无法整除则取整数位)  
3、扩容后，会将当前数组中的所有元素拷贝到新的扩容数组中  
4、默认容量和指定容量的ArrayList扩容规则相同