初始化
- 默认容量大小为10;
- 存储是Object[]数组;
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() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; }
扩容
- 调用grow()函数,新数组容量扩大了是1.5倍;
- 通过System.arraycopy()函数复制数组;
private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1); 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); }
remove()带来的问题
remove移除元素的时候会调用fastRemove()方法
private void fastRemove(int index){ modCount++; intnumMoved=size-index-1; if(numMoved>0) System.arraycopy(elementData,index+1,elementData,index,numMoved); elementData[--size]=null;// Let gc do its work }
理解
- 通过System.arraycopy()方法,导致删除元素时涉及到数组元素的移动;
- 所以for-each + remove()的写法,会导致遇到第一满足删除条件,把该元素从数组中删除;
- 并且后一个元素会移动到当前位置,导致下一次遍历的时候后一个元素没有遍历到,导致无法删除满足条件的第二个元素;
解决办法:
倒序遍历删除的方式
for(int i = list.size(); i >= 0; i--){ String s = list.get(i); if(s.equals("hshuo")){ list.remove(s); } }或者使用迭代器
public static void remove(ArrayList<String> list) { Iterator<String> it = list.iterator(); while (it.hasNext()) { String s = it.next(); if (s.equals("b")) { it.remove(); } } }
参考:
补充
- list 列表的结尾会预留一定的容量空间。
- 向 ArrayList 添加大量元素之前最好先使用ensureCapacity 方法,以减少增量重新分配的次数。
ensureCapacity()
/** 如有必要,增加此 ArrayList 实例的容量,以确保它至少可以容纳由minimum capacity参数指定的元素数。 * * @param minCapacity 所需的最小容量 */ public void ensureCapacity(int minCapacity) { int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) // any size if not default element table ? 0 // larger than default for default empty table. It's already // supposed to be at default size. : DEFAULT_CAPACITY; if (minCapacity > minExpand) { ensureExplicitCapacity(minCapacity); } }
ensureExplicitCapacity()调用grow()进行扩容
private void ensureExplicitCapacity(int minCapacity) { modCount++; // overflow-conscious code if (minCapacity - elementData.length > 0) grow(minCapacity); }
例如:
多添加了list.ensureCapacity(N);
public class EnsureCapacityTest { public static void main(String[] args) { ArrayList<Object> list = new ArrayList<Object>(); final int N = 10000000; list = new ArrayList<Object>(); long startTime1 = System.currentTimeMillis(); list.ensureCapacity(N); for (int i = 0; i < N; i++) { list.add(i); } long endTime1 = System.currentTimeMillis(); System.out.println("使用ensureCapacity方法后:"+(endTime1 - startTime1)); } }