ArrayList源码解析

ArrayList底层使用数组进行存储数据，具有查询速度快、读写速度慢的特性。

add

public boolean add(E e) { //确保数组空间足够 ensureCapacityInternal(size + 1); //默认插入数组最后方 elementData[size++] = e; return true; } private void ensureExplicitCapacity(int minCapacity) { modCount++; // 空间不够需要扩展 if (minCapacity - elementData.length > 0) grow(minCapacity); } /**扩展逻辑*/ private void grow(int minCapacity) { int oldCapacity = elementData.length; //空间拓展为原来的1.5倍 int newCapacity = oldCapacity + (oldCapacity >> 1); if (newCapacity - minCapacity < 0) newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); //将旧的数组数据复制到扩展后的新数组内 elementData = Arrays.copyOf(elementData, newCapacity); }

数组空间的每次扩展都会进行一次数组复制，我们可以通过构造器指定数组大小避免频繁复制数组导致的性能下降。

remove

public E remove(int index) { rangeCheck(index); modCount++; E oldValue = elementData(index); int numMoved = size - index - 1; //大于零说明不是移除的最后一项 if (numMoved > 0) //将移除索引后方的数据拷贝到从索引开始的位置 System.arraycopy(elementData, index+1, elementData, index, numMoved); //最后一位置空 等待GC elementData[--size] = null; return oldValue; }

另一个删除方法是通过对象删除，由于需要先查询索引。因此性能上还是按照索引删除快。

public boolean remove(Object o) { if (o == null) { for (int index = 0; index < size; index++) if (elementData[index] == null) { fastRemove(index); return true; } } else { for (int index = 0; index < size; index++) if (o.equals(elementData[index])) { fastRemove(index); return true; } } return false; }

get

public E get(int index) { rangeCheck(index); return elementData(index); }

可以看到查找直接通过索引即可查询相关数据， 而插入（非尾部插入）和删除均需要复制数组，因此性能要比查询慢。

Iterator

for循环删除元素时会有索引错乱问题，iterator则不会。

首先iterator进行迭代时取下一个元素，把游标移动到当前元素的下一个索引。

public E next() { checkForComodification(); int i = cursor; if (i >= size) throw new NoSuchElementException(); Object[] elementData = ArrayList.this.elementData; if (i >= elementData.length) throw new ConcurrentModificationException(); //游标指向下一个索引 cursor = i + 1; //这里会把当前游标赋值给lastRet return (E) elementData[lastRet = i]; }

进行删除时，删除当前元素后。数组会整体向前移动，当前索引的位置元素就变成了移除前的下一个索引的元素。当前索引重新赋值给游标，下次用next()方法取到的游标仍然是当前索引。

public void remove() { if (lastRet < 0) throw new IllegalStateException(); checkForComodification(); try { ArrayList.this.remove(lastRet); //当前游标对应元素移除后 数组会整体向前移动 当前索引对应的元素就是原来的下一个元素 //因此直接将当前索引赋值给游标 cursor = lastRet; lastRet = -1; expectedModCount = modCount; } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } }