ArrayList扩容与缩容机制

你的名字 2023-02-11 03:17 9阅读 0赞

ArrayList集合类是我们面试中经常被问到的一个问题，类似的有ArrayList与LinkedList的区别之类的，而ArrayList与LinkedList的主要区别在于其数据结构的不同，ArrayList的底层是数据类型，而LinkedList是链表类型，从而导致了ArrayList更适用于多查询操作，而LinkedList适用于多删除插入操作；本章主要讲解的是ArrayList的扩容和缩容操作。

## ArrayList扩容 ##

首先，先看看ArrayList的初始化，源码如下：

public ArrayList(int initialCapacity) { 
            if (initialCapacity > 0) {         
            //更根据初始值大小创建数组
                this.elementData = new Object[initialCapacity];
            } else if (initialCapacity == 0) { 
            //默认无规定初始值大小时，会创建一个空数组
            //private static final Object[] EMPTY_ELEMENTDATA = {};
            //待通过add方法时创建初始容量为10的数组
                this.elementData = EMPTY_ELEMENTDATA;
            } else { 
                throw new IllegalArgumentException("Illegal Capacity: "+
                                                   initialCapacity);
            }
        }

add(E e)方法的源码解析

public boolean add(E e) { 
    		//检查是否需要扩容
            ensureCapacityInternal(size + 1);  // Increments modCount!!
            //添加新元素
            elementData[size++] = e;
            return true;
        }
    
    //传入数组最小所需要的长度
    private void ensureCapacityInternal(int minCapacity) { 
            ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
        }
    //检查原先数组是否为空数组，返回数组所需最小长度
    private static int calculateCapacity(Object[] elementData, int minCapacity) { 
    		//判断数组是否为空。
    		//private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { 
                //private static final int DEFAULT_CAPACITY = 10;
                //数组为空时，返回DEFAULT_CAPACITY与minCapacity中大的数，减少扩容次数
                return Math.max(DEFAULT_CAPACITY, minCapacity);
            }
            //直接返回数组所需的最小长度size+1
            return minCapacity;
        }
    
    //判断当前数组长度是否超过添加元素所需的最小长度
    private void ensureExplicitCapacity(int minCapacity) { 
            modCount++;
    
            // overflow-conscious code
            //如果所需最小长度大于当前数组长度
            if (minCapacity - elementData.length > 0)
            	//进行扩容
                grow(minCapacity);
            //否则，不做任何处理
        }
        
    
    private void grow(int minCapacity) { 
            // overflow-conscious code
            int oldCapacity = elementData.length;
            //新数组长度等于旧长度+1/2旧长度
            int newCapacity = oldCapacity + (oldCapacity >> 1);
            //计算newCapacity的大小
            if (newCapacity - minCapacity < 0)
                newCapacity = minCapacity;
            //private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
            if (newCapacity - MAX_ARRAY_SIZE > 0)
                newCapacity = hugeCapacity(minCapacity);
            // minCapacity is usually close to size, so this is a win:
            //拷贝到新数组，数组长度为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缩容 ##

ArrayList没有自动缩容机制。无论是remove方法还是clear方法，它们都不会改变现有数组elementData的长度。但是它们都会把相应位置的元素设置为null，以便垃圾收集器回收掉不使用的元素，节省内存。ArrayList的缩容，需要我们自己手动去调用trimToSize()方法，达到缩容的目的。

/** * Trims the capacity of this <tt>ArrayList</tt> instance to be the * list's current size. An application can use this operation to minimize * the storage of an <tt>ArrayList</tt> instance. */
        public void trimToSize() { 
            modCount++;
            //判断当前容量与数组长度的大小关系
            if (size < elementData.length) { 
            	//如果size小于elementData.length，则将数组拷贝到长度为size的数组中，如果size==0，则将elementData 置为空数组，{}
                elementData = (size == 0)
                  ? EMPTY_ELEMENTDATA
                  : Arrays.copyOf(elementData, size);
            }
        }