ArrayList扩容的本质就是计算出新的扩容数组的size后实例化,并将原有数组内容复制到新数组中去。
默认情况下,新的容量会是原容量的1.5倍。以JDK1.8为例说明:
一、源码讲解
publicbooleanadd(Ee) { //判断是否可以容纳e,若能,则直接添加在末尾;若不能,则进行扩容,然后再把e添加在末尾ensureCapacityInternal(size+1); // Increments modCount!!//将e添加到数组末尾elementData[size++] =e; returntrue; } // 每次在add()一个元素时,arraylist都需要对这个list的容量进行一个判断。通过ensureCapacityInternal()方法确保当前ArrayList维护的数组具有存储新元素的能力,经过处理之后将元素存储在数组elementData的尾部privatevoidensureCapacityInternal(intminCapacity) { ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); } privatestaticintcalculateCapacity(Object[] elementData, intminCapacity) { //如果传入的是个空数组则最小容量取默认容量与minCapacity之间的最大值if (elementData==DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { returnMath.max(DEFAULT_CAPACITY, minCapacity); } returnminCapacity; } privatevoidensureExplicitCapacity(intminCapacity) { modCount++; // 若ArrayList已有的存储能力满足最低存储要求,则返回add直接添加元素;如果最低要求的存储能力>ArrayList已有的存储能力,这就表示ArrayList的存储能力不足,因此需要调用grow();方法进行扩容if (minCapacity-elementData.length>0) grow(minCapacity); } privatevoidgrow(intminCapacity) { // 获取elementData数组的内存空间长度intoldCapacity=elementData.length; // 扩容至原来的1.5倍intnewCapacity=oldCapacity+ (oldCapacity>>1); //校验容量是否够if (newCapacity-minCapacity<0) newCapacity=minCapacity; //若预设值大于默认的最大值,检查是否溢出if (newCapacity-MAX_ARRAY_SIZE>0) newCapacity=hugeCapacity(minCapacity); // 调用Arrays.copyOf方法将elementData数组指向新的内存空间//并将elementData的数据复制到新的内存空间elementData=Arrays.copyOf(elementData, newCapacity); }
二、面试题:ArrayList扩容机制回答
- ArrayList扩容的本质就是计算出新扩容数组的size后实例化,并将原有数组的内容复制到新数组中去,默认扩容容量是原容量的1.5倍.
- 当调用add方法时,首先调用ensureCapacityInternal方法,传入size+1,判断是否可以容纳元素e,若能,则直接添加到数组的末尾,若不能,则进行扩容,再把e添加在末尾
- 扩容调用的方法为grow,newCapacity扩容至原来的1.5倍,然后检验容量是否足够,如果不够,就使用它指定要扩充的大小minCapacity,然后判断newCapacity是否大于MAX_ARRAY_SIZE,如果大于,就取Integer.MAX_VALUE
- 最后调用Arrays.copyOf方法将elementData数组指向新的内存空间 ,并将elementData的数据复制到新的内存空间