目录

目录.png

---

源码分析

是否允许空, 是否允许重复数据, 是否有序, 是否线程安全

关 注 点	结论
是否允许空	允许
是否允许重复数据	允许
是否有序	有序
是否线程安全	非线程安全

构造函数

• 创建 ArrayList 的时候直接给元素对象开辟一个指定的容量大小
• 如果直接 new 一个空的构造函数的 ArrayList 内部直接创建一个默认空的对象数组，实际添加时再分配

add源码

// 尾部插入，效率高
public boolean add(E e) {
    // 会先判断是否要扩容，也会对modCount增加
    ensureCapacityInternal(size + 1);  
    elementData[size++] = e;
    return true;
}

// 头插或者中间插入效率低
public void add(int index, E element) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    //检查是否需要扩容
    ensureCapacityInternal(size + 1);  
    //将需要插入的 index 位置往后移动一位, 所以如果只是尾部插入效率也还好
    System.arraycopy(elementData, index, elementData, index + 1, size - index);
    //在 数组的 index 位置直接存入 元素
    elementData[index] = element;
    size++;
}

// 因为后面还调用了ensureExplicitCapacity所以此方法名叫ensureCapacityInternal
private void ensureCapacityInternal(int minCapacity) {
    // 如果当前元素数据为空的时候
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        // 和默认的扩容容量比较，取出最大值。
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
   // 第一次还是空的数组时，minCapacity = 10，elementData.length = 0. 需要扩容
   // 第二次数组就被初始化了，add一次minCapacity从1开始增加1，elementData.length的值为第一次赋值的10
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}
// grow扩容
private void grow(int minCapacity) {
    // 扩容1.5倍 使用Arrays.copyOf扩容
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    elementData = Arrays.copyOf(elementData, newCapacity);
}

remove

• 由于需要将删除位置后面的元素向前挪动，也会设计数组复制，所以操作较慢

public E remove(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

    modCount++;
    E oldValue = (E) elementData[index];
    
    int numMoved = size - index - 1;
    if (numMoved > 0)
        //将index后面的元素向前挪动一位
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    // 置空引用
    elementData[--size] = null; 
    //返回被删除的元素
    return oldValue;
}

查询

• 直接返回指定下标的数组元素，操作快速。

序列化优化

// 因为扩容的原因里面有很多空的元素，所以禁止序列化
transient Object[] elementData;

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]);
    }
    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
}

迭代器模式fail-fast

• ArrayList的迭代器中

private class Itr implements Iterator<E> {
    // 使用迭代器时会初始化expectedModCount，如果期间有多线程修改会改变modCount值从而引起fail-fast
    int expectedModCount = modCount;
    public E next() {
        checkForComodification();
        // 省略一些代码
    }
    
    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}

Comparator 排序比较

 public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        list.add(33);
        list.add(5);
        list.add(4);
        list.sort(Integer::compare);
        list.stream().forEach(System.out::println);
    }

---

参考文章

• 图解集合1：ArrayList
• java-----ArrayList的fail-fast机制学习
• 源码分析 (一) ArrayList JDK 1.8 源码分析