【源码】ArrayList源码

前言构造方法add插入元素get(int index)获取元素contains(Object o)判断元素是否存在remove(int index)根据下标移除元素remove(Object o)移除元素removeAll(Collection c)

前言

作为最常用的集合之一，有必要读一下源码。 ArrayList，基于数组实现，因此元素的读取速度十分快，因为数组在内存的上地址连续，但是插入删除涉及到数组元素的移动，因此效率较低。

构造方法

// 空（默认）构造方法 public ArrayList() { super(); this.elementData = EMPTY_ELEMENTDATA; } // 存储数据的数组 transient Object[] elementData; // 默认初始化的空数组 private static final Object[] EMPTY_ELEMENTDATA = {}; // 接受集合参数构造，赋值size并将参数集合copy到存储数组 public ArrayList(Collection<? extends E> c) { elementData = c.toArray(); size = elementData.length; if (elementData.getClass() != Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); }

构造方法比较简单，我们平时最常用的默认构造，初始化内部数组为空数组。

add插入元素

public boolean add(E e) { ensureCapacityInternal(size + 1); elementData[size++] = e; return true; } private void ensureCapacityInternal(int minCapacity) { // 发现如果初始化为空，则默认扩容至10 if (elementData == EMPTY_ELEMENTDATA) { minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } ensureExplicitCapacity(minCapacity); } private static final int DEFAULT_CAPACITY = 10; private void ensureExplicitCapacity(int minCapacity) { modCount++; // 预计容量大于当前容量则进行扩容 if (minCapacity - elementData.length > 0) grow(minCapacity); } private void grow(int minCapacity) { // 旧容量 int oldCapacity = elementData.length; // 位运算 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); } // 指定位置插入 public void add(int index, E element) { // 检查下标是否越界 rangeCheckForAdd(index); // 同上 ensureCapacityInternal(size + 1); // Increments modCount!! // native方法 System.arraycopy(elementData, index, elementData, index + 1, size - index); // 复制，长度+1 elementData[index] = element; size++; }

插入元素第一件事就是根据插入后的长度判断是否需要扩容，由于默认构造为空数组，因此第一次插入会发生一次扩容。在指定位置的元素插入会涉及整个元素的移动，因此调用的是native方法，效率较高。

get(int index)获取元素

public E get(int index) { // 检查数组下标 rangeCheck(index); // return elementData[index] return elementData(index); }

contains(Object o)判断元素是否存在

public boolean contains(Object o) { return indexOf(o) >= 0; }

remove(int index)根据下标移除元素

public E remove(int index) { // 检查下标 rangeCheck(index); // 修改数+1 modCount++; // 取出要移除的元素 E oldValue = elementData(index); // 如果非最后一个元素，调用native方法复制数组 int numMoved = size - index - 1; if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); // 如果是最后一个元素，直接将其指向null，等待GC回收 elementData[--size] = null; // 返回被移除的元素 return oldValue; }

remove(Object o)移除元素

// 遍历匹配后调用fastRemove（index） 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; } // fastRemove逻辑基本跟remove相同 private void fastRemove(int index) { modCount++; int numMoved = size - index - 1; if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); elementData[--size] = null; }

removeAll(Collection c)

public boolean removeAll(Collection<?> c) { Objects.requireNonNull(c); return batchRemove(c, false); } // 一段比较巧妙的算法 private boolean batchRemove(Collection<?> c, boolean complement) { final Object[] elementData = this.elementData; int r = 0, w = 0; boolean modified = false; try { for (; r < size; r++) if (c.contains(elementData[r]) == complement) elementData[w++] = elementData[r]; } finally { // 这个判断分支看不懂 if (r != size) { System.arraycopy(elementData, r, elementData, w, size - r); w += size - r; } // 实现元素移除 if (w != size) { // clear to let GC do its work for (int i = w; i < size; i++) elementData[i] = null; modCount += size - w; size = w; modified = true; } } return modified; }