Java 集合框架系列四：JDK 1.8 ArrayList 详解-向日葵屋

ArrayList 继承关系

$外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-XG2c3R4h-1599553042477)(G:\\学习记录\\Java 集合框架\\images\\微信截图\_20200830201146.png)$
ArrayList 是 JDK 1.2 提供的 List 实现类，继承了 AbstractList 抽象类，实现了 Cloneable、Serializable、RandomAccess、List 接口。

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable { 
}

ArrayList 实现了 Cloneable 接口说明 ArrayList 是可以拷贝的，看到 ArrayList 重写了 Object#clone 方法，ArrayList 的默认实现是浅拷贝，但是拷贝不会复制元素本身，只会复制元素的引用。拷贝后的 ArrayList 和原 ArrayList 的引用不相同，但是都持有了对相同元素的引用。

public Object clone() { 
        try { 
            ArrayList<?> v = (ArrayList<?>) super.clone();
            v.elementData = Arrays.copyOf(elementData, size);
            v.modCount = 0;
            return v;
        } catch (CloneNotSupportedException e) { 
            // this shouldn't happen, since we are Cloneable
            throw new InternalError(e);
        }
    }

ArrayList 实现了 RandomAccess 表示 ArrayList 的元素是允许随机访问的。所以 ArrarList 允许通过索引访问元素，访问速度是很快。

类文档解读

老规矩，先通过 ArrayList 的类文档了解一下能得到哪些信息。

ArrayList 是大小可变的有序列表，内部是一个容量可以动态增长的 Object 类型的数组。因其底层数据结构是数组，所以它是占据一块连续的内存空间。可以根据下标以 O(1) 的时间复杂度读写元素，因此时间效率很高。但是数组也有缺点，对数组进行添加和删除元素时由于需要移动元素，所以添加和删除元素的复杂度是 O(n)，ArrayList 空间效率不高。
由于数组的容量有限，所以在容量不满足容纳新元素时会发生扩容操作，由于扩容需要大量移动数组的数据，所以这是很耗费性能的地方，建议在构建 ArrayList 时指定合适的集合容量以减少扩容次数，或者在添加大量元素前手动调用 java.util.ArrayList#ensureCapacity 方法扩容，注意该方法是 ArrayList 的 API，所以可能需要强转操作。
ArrayList 允许添加 null 元素，而且 ArrayList 是允许重复数据的，所以 ArrayList 可能存在多个 null 元素。
ArrayList 是非线程安全的，如果希望使用线程安全的 List 可以通过List list = Collections.synchronizedList(new ArrayList(...));方法获取线程安全的 List。
ArrayList 返回的迭代器是 fail-fast 策略的，如果在迭代过程中存在线程对 ArrayList 进行结构修改会抛出 ConcurrentModificationException。

ArrayList API

成员变量

// 默认容量
    private static final int DEFAULT_CAPACITY = 10;
    // 用于默认大小的共享空数组实例，当用户指定初始容量是0时使用
    private static final Object[] EMPTY_ELEMENTDATA = { };
    // 用于默认大小的共享空数组实例 需要将其与 EMPTY_ELEMENTDATA 区分开以了解添加第一个元素时要扩容的大小
    // 在调用无参构造方法构建 ArrayList 时使用
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = { };
    // 存储 ArrayList 元素的数组缓冲区，数组的长度是 ArrayList 的容量，
    // 任何一个 elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的空数组
    // 在添加一个元素时会将数组的容量扩展为 DEFAULT_CAPACITY
    transient Object[] elementData; 
    // 元素的数量 不一定和 elementData 的长度相等
    private int size;
    // 最大容量
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

构造方法

// 无参构造方法，会将 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 静态变量赋值给 elementData。
    public ArrayList() { 
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    // 指定初始容量
    public ArrayList(int initialCapacity) { 
        if (initialCapacity > 0) { 
            // 指定的初始容量 > 0 则初始化 elementData 数组
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) { 
            // EMPTY_ELEMENTDATA 表示用户指定初始容量是 0
            this.elementData = EMPTY_ELEMENTDATA;
        } else { 
            // < 0 抛出异常
            throw new IllegalArgumentException("Illegal Capacity: "+  initialCapacity);
        }
    }
    // 将指定的 Collection 中的元素添加到当前 ArrayList
    public ArrayList(Collection<? extends E> c) { 
        // 转换为数组 如果 c 是 null 则抛出 NullPointerException
        elementData = c.toArray();
        if ((size = elementData.length) != 0) { 
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else { 
            // 如果数组的长度是0，则将 EMPTY_ELEMENTDATA 赋给 elementData
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

ArrayList#size

public int size() { 
        return size;
    }

ArrayList#isEmpty

public boolean isEmpty() { 
        return size == 0;
    }

ArrayList#add(E)

在列表的末尾添加一个新元素。

public boolean add(E e) { 
        // 判断当前数组是否能够容纳新元素，传递 size + 1
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        // 将数组的 size++ 赋值且长度 +1
        elementData[size++] = e;
        return true;
    }
    private void ensureCapacityInternal(int minCapacity) { 
        // 如果 elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA，即通过无参构造方法创建的 ArrayList 实例
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { 
            // 从 DEFAULT_CAPACITY 和 minCapacity 找一个最大值作为容量
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        ensureExplicitCapacity(minCapacity);
    }
    private void ensureExplicitCapacity(int minCapacity) { 
        // 对修改计算器 + 1
        modCount++;
        // 如果当前需要的容量大于 elementData 数组长度需要扩容
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
    // 扩容
    private void grow(int minCapacity) { 
        // 当前 elementData 数组的长度
        int oldCapacity = elementData.length;
        // 新数组的长度： oldCapacity >> 1 是当前数组长度的一半 如 10 就是 5,5 就是 2，然后加上当前数组的长度，也就是 1.5 倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        // 如果新数组的长度仍然小于 minCapacity 则使用 minCapacity（需要的长度） 作为新数组的长度，者意味着下次添加元素要再次扩容
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        // 如果新数组长度大于 MAX_ARRAY_SIZE 需要重新选取数组长度 Integer.MAX_VALUE OR MAX_ARRAY_SIZE OR 抛出 OutOfMemoryError
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // 创建新数组并将原数组元素复制，最后赋值给 elementData
        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#add(int, E)

在此列表的指定位置插入指定的元素，将指定位置的后续元素向右移动。

public void add(int index, E element) { 
        // 检查是否越界
        rangeCheckForAdd(index);
        // 判断是否需要扩容，同 add(E)
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        // 将 index 后面的元素向后移动一位。
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        // 将元素插入到 index 位置
        elementData[index] = element;
        // 长度加 1
        size++;
    }
    private void rangeCheckForAdd(int index) { 
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

ArrayList#addAll(java.util.Collection<? extends E>)

按照指定集合的迭代器返回的顺序，将指定集合中的所有元素追加到此列表的末尾。此方法添加的是指定集合的元素引用。

public boolean addAll(Collection<? extends E> c) { 
        // 调 toArray 方法
        Object[] a = c.toArray();
        int numNew = a.length;
        // 判断当前集合长度 + 指定集合长度是否需要扩容
        ensureCapacityInternal(size + numNew);  // Increments modCount
        // 将指定集合元素添加到当前集合末尾
        System.arraycopy(a, 0, elementData, size, numNew);
        // 长度增加
        size += numNew;
        return numNew != 0;
    }

ArrayList#addAll(int, java.util.Collection<? extends E>)

从指定位置开始，将指定集合中的所有元素插入此列表。将当前位于该位置的元素（如果有）和后续元素向右移动。新元素将按照指定集合的迭代器返回的顺序出现在列表中。

public boolean addAll(int index, Collection<? extends E> c) { 
        // 越界检查
        rangeCheckForAdd(index);
        Object[] a = c.toArray();
        int numNew = a.length;
        // 判断是否需要扩容
        ensureCapacityInternal(size + numNew);  // Increments modCount
        // 判断需要移动的元素数量
        int numMoved = size - index;
        if (numMoved > 0)
            System.arraycopy(elementData, index, elementData, index + numNew,
                             numMoved);
        System.arraycopy(a, 0, elementData, index, numNew);
        size += numNew;
        return numNew != 0;
    }

ArrayList#get

public E get(int index) { 
        rangeCheck(index);
        return elementData(index);
    }
    // 越界检查
    private void rangeCheck(int index) { 
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
    E elementData(int index) { 
        // 通过数组下标访问
        return (E) elementData[index];
    }

ArrayList#set

public E set(int index, E element) { 
        // 越界检查
        rangeCheck(index);
        // 当前元素
        E oldValue = elementData(index);
        // 替换新元素
        elementData[index] = element;
        // 返回旧元素
        return oldValue;
    }

ArrayList#contains

public boolean contains(Object o) { 
        // 判断 indexOf 是否 > 0
        return indexOf(o) >= 0;
    }

ArrayList#indexOf

通过 for 循环正序遍历数组元素并通过元素的 equals 方法进行比较，找到就返回 index，找不到返回 -1。

public int indexOf(Object o) { 
        if (o == null) { 
            for (int i = 0; i < size; i++)
                if (elementData[i]==null)
                    return i;
        } else { 
            for (int i = 0; i < size; i++)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }

ArrayList#lastIndexOf

通过 for 循环逆序遍历数组元素并通过元素的 equals 方法进行比较，找到就返回 index，找不到返回 -1。

public int lastIndexOf(Object o) { 
        if (o == null) { 
            for (int i = size-1; i >= 0; i--)
                if (elementData[i]==null)
                    return i;
        } else { 
            for (int i = size-1; i >= 0; i--)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }

ArrayList#remove(int)

删除此列表中指定位置的元素。向左移动后续元素。

public E remove(int index) { 
        // 越界检查
        rangeCheck(index);
        // modCount + 1
        modCount++;
        // 取出需要删除的元素
        E oldValue = elementData(index);
        // 如果删除的元素不是最后一个就需要将索引后面的元素向左移动一个位置
        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,numMoved);
        // 将最后一个元素设为 null
        elementData[--size] = null; // clear to let GC do its work
        // 返回需要删除的元素
        return oldValue;
    }

ArrayList#remove(java.lang.Object)

移除第一个 equals 为 true 的元素的 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;
    }
    // 私有删除方法，跳过边界检查且不返回移除的值。
    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; // clear to let GC do its work
    }

ArrayList#clear

// 清空 ArrayList
    public void clear() { 
        modCount++;
        // 循环
        for (int i = 0; i < size; i++)
            // 赋 null 以便 GC
            elementData[i] = null;
        size = 0;
    }

ArrayList#subList

该方法返回的是 SubList 对象，是 ArrayList 的一个内部类，该对象继承了 AbstractList，实现了 RandomAccess。

public List<E> subList(int fromIndex, int toIndex) { 
        subListRangeCheck(fromIndex, toIndex, size);
        return new SubList(this, 0, fromIndex, toIndex);
    }
    private class SubList extends AbstractList<E> implements RandomAccess { 
        private final AbstractList<E> parent;
        private final int parentOffset;
        private final int offset;
        int size;
        SubList(AbstractList<E> parent,
                int offset, int fromIndex, int toIndex) { 
            this.parent = parent;
            this.parentOffset = fromIndex;
            this.offset = offset + fromIndex;
            this.size = toIndex - fromIndex;
            this.modCount = ArrayList.this.modCount;
        }
    }

ArrayList#sort

public void sort(Comparator<? super E> c) { 
        final int expectedModCount = modCount;
        // 使用 Arrays.sort 对 elementData 排序
        Arrays.sort((E[]) elementData, 0, size, c);
        if (modCount != expectedModCount) { 
            throw new ConcurrentModificationException();
        }
        // 此方法也会将 modCount + 1。
        modCount++;
    }

ArrayList#ensureCapacity

建议存放大量元素前先调此方法手动扩容，避免自动频繁扩容影响性能。

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);
        }
    }

Itr 和 ListIterator

Itr 和 ListIterator 是 ArrayList 的内部类，分别实现了 Iterator 和 ListIterator 接口。

private class Itr implements Iterator<E> { }
private class ListItr extends Itr implements ListIterator<E> { }

ArrayList 的遍历方式

普通 for 循环

for(int i = 0;i < list.size();++i){
}
增加 for 循环

for(Str s:list){
}
迭代器遍历

ListIterator it = list.listIterator();
while(it.hasNext()){
```
it.next();
```
}

ArrayList 删除元素的方式

List<String> list = new ArrayList<String>();
        list.add("jj");
        list.add("kk");
        list.add("kk");
        list.add("rr");
        list.add("kk");
        /* * 方式一 * 当kk元素没有连续存储时，就不能全部删除集合中的kk元素 因为每删除一次元素，集合长度变小， * 但是迭代的下标没变 */
        for (int i = 0; i < list.size(); i++) { 
            System.out.println(i);
            if (list.get(i).equals("kk")) { 
                list.remove(i);
            }
        }
        /* * 方式二 * 不管kk元素是否连续，都可以全部删除 */
        for (int i = 0; i < list.size(); i++) { 
            if ("kk".equals(list.get(i))) { 
                list.remove(i);
                --i;// 删除了元素，迭代的下标也跟着改变
            }
        }
        /* * 方式三 * 不管值为"c"的元素在list中是否连续，都可以把值为"c"的元素全部删除 需保证没有其他线程同时在修改 */
        Iterator<String> iterator = list.iterator();
        while (iterator.hasNext()) { 
            String str = iterator.next();
            if ("kk".equals(str)) { 
                iterator.remove();
            }
        }

其他实现方法

ArrayList不仅实现了List中定义的所有功能，还实现了clone、writeObject与readObject等方法。这些方法都需要与存储的数据配合，否则结果将是错误的或者克隆得到的数据只是浅拷贝，或者数据本身不支持序列化等，这些我们定义数据时注意到即可。我们主要看下其在序列化时自定义了哪些东西。

//这里就能解开我们的迷惑了，elementData被transient修饰，也就是不会参与序列化
//这里我们看到数据是一个个写入的，并且将size也写入了进去
private void writeObject(java.io.ObjectOutputStream s)
    throws java.io.IOException{ 
    // Write out element count, and any hidden stuff
    int expectedModCount = modCount;
    s.defaultWriteObject();
    // Write out size as capacity for behavioural compatibility with clone()
    s.writeInt(size);
        // Write out all elements in the proper order.
    for (int i=0; i<size; i++) { 
        s.writeObject(elementData[i]);
    }
    //modCount的作用在此体现，如果序列化时进行了修改操作，就会抛出异常
    if (modCount != expectedModCount) { 
        throw new ConcurrentModificationException();
    }
}

readObject是一个相反的过程，就是把数据正确的恢复回来，并将elementData设置好即可。

private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException { 
        elementData = EMPTY_ELEMENTDATA;
        // Read in size, and any hidden stuff
        s.defaultReadObject();
        // Read in capacity
        s.readInt(); // ignored
        if (size > 0) { 
            // be like clone(), allocate array based upon size not capacity
            ensureCapacityInternal(size);
            Object[] a = elementData;
            // Read in all elements in the proper order.
            for (int i=0; i<size; i++) { 
                a[i] = s.readObject();
            }
        }
    }