ArrayList源码分析（JDK 1.8）

一、介绍

ArrayList其本质就是数据结构中的动态数组，是一个能够内部进行扩容的数组。所以它拥有数组所拥有的特性，在时间上，通过下标直接访问，速度极快；在空间上，在内存中占连续的一段空间且创建数组时必须指定确定的容量，因此指定的容量往往大于预期的容量，造成空间浪费。

特性上数组在查找上效率高，在插入和删除时便会很麻烦且耗时，因为删除和插入需要移动目标元素之后的所有数组元素，才能使数组产生空隙供目标元素插入或消除目标元素删除产生的一个空隙。

二、源码流程分析

友情提示：注释为个人理解，原英文注释可自行翻看源码，有大段解释文字在代码注释上哦，手机访问时点击代码可横屏显示，观看更舒适。

1、首先认识一下这个类的相关变量

    // 默认初始化容量，也就是创建数组时如果没有指定ArrayList的大小默认为10
    private static final int DEFAULT_CAPACITY = 10;

	// 空数组实例常量，容量为0时给ArrayList数组变量赋值
    private static final Object[] EMPTY_ELEMENTDATA = {};

	// 默认空数组实例常量，容量为默认容量时给ArrayList数组变量赋值
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

	// 实际数组变量，transient表示变量不能自动序列化
	// 实现Serializable为自动序列化，实现Externalizable手动序列化，与transient关键字无关
    transient Object[] elementData; // non-private to simplify nested class access

    // 数组当前元素总数的大小，小于数组总容量
    private int size;

2、我们从new ArrayList()开始看它的生平经历

	// 如果实例化时不设置初值，数组为默认容量空数组
	public ArrayList() {
		this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
	}

	// 如果容量大于0，new一个该容量的数组，容量等于0，数组设置为空数组，否则就抛出异常
    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);
        }
    }

	// ArrayList提供了集合类作为构造函数参数
	// 由于集合类toArray方法可能被重写，故返回值不一定是Object数组，需要判断
    public ArrayList(Collection<? extends E> c) {
        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 {
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

3、探究ArrayList的常用方法

首先得先看它的扩容机制

扩容的最外层是确定内部容量方法，这个内部的意思其实可以理解为是ArrayList之前自己埋的“坑”，前面不指定容量时是用默认空数组赋值给数组变量的，那么如果容量不够，首先应该判断是不是默认的那个空数组，如果是则应该先将数组容量扩容到默认的容量10，之后容量大于10了就用扩容机制解决

    // 如果是默认空数组，返回minCapacity和默认容量的较大值，minCapacity即当前要求的最小容量
	private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }
	private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

然后就是扩容机制了，modCount记录修改次数，该变量继承于AbstractList，每当集合结构发生变化时(例如添加和删除操作)该变量加一，用于解决遍历数组时若发生结构变化导致结果不如预期的情况。expectedModCount初始值为modCount，每当发生结构变化时expectedModCount变化，若modCount与expectedModCount值不一致则抛出ConcurrentModificationException异常，这种问题在操作多线程时极易出现，这里简单介绍一下

扩容时newCapacity（新容量）为以前的1.5倍，若新容量比minCapacity（要求的最小容量）还小，则直接将newCapacity设置为minCapacity，若newCapacity超过最大数组大小，进行hugeCapacity方法判断，最后根据新容量将原数组拷贝给新数组

	private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

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

	// 若minCapacity小于0则表示溢出（溢出时二进制补码符号位进位变为1）
    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

add方法，先进行扩容判断，然后有数组size末尾添加新数据

    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

get方法，首先进行索引有效性检验是否越界，然后强转Object类型取值，unchecked为取消一些运行时的检查，这里为取消强转的检查

    public E get(int index) {
        rangeCheck(index);

        return elementData(index);
    }

    private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

    @SuppressWarnings("unchecked")
    E elementData(int index) {
        return (E) elementData[index];
    }

按索引add方法，即插入方法，首先依旧是索引范围检查，扩容判断，把index之后包括index位置的数组元素向数组后整体移动一位，然后index位置赋值为element

    public void add(int index, E element) {
        rangeCheckForAdd(index);

        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }

    private void rangeCheckForAdd(int index) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

remove方法，这里主要介绍fastRemove方法，按Object或按索引的删除方法只是多了一些简单的步骤而已

fastRemove方法与按索引添加也类似，将删除位置的元素后面的所有元素向前移动一位，并将最后一个无用的空位置置于null让GC垃圾回收器处理

    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
    }

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

本文地址：https://blog.csdn.net/GHSTART/article/details/112846713