ArrayList底层源码分析

ArrayList底层，主要是由数组实现

看代码

List<String> list = new ArrayList<>();

我们new出一个ArrayList()后，看看底层构造函数做了哪些事情

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
transient Object[] elementData;
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

显然，底层构造函数对一个java的数组进行了初始化。

如果调用add后，ArrayList又做了什么呢?

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

elementData[size++] = e;这里i是后加的，所以此时elementData[0] = e

看断点

再来看看

ensureCapacityInternal(size + 1);

看看这里ArrayList做了什么

private void ensureCapacityInternal(int minCapacity) {
	ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

继续跟

private static final int DEFAULT_CAPACITY = 10;
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
	return Math.max(DEFAULT_CAPACITY, minCapacity);
}
	return minCapacity;
}

这里if肯定进的来，因为第一次初始化的时候elementData肯定是默认的容量确实是0，DEFAULT_CAPACITY这个值是10，所以比较下，最后返回10

返回10后，跟到

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

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

modCount++这个可以先不管，下面的判断，如果传入的大于当前数组的长度，就做扩容

那么第一次elementData是0，肯定需要做扩容，因此代码继续跟到grow()这个方法

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

int newCapacity = oldCapacity + (oldCapacity >> 1);

这里用了个右移位运算符，那么实际上效果是旧的大小加上旧的大小除以2后作为新的大小，故最后扩容效果是原来的1.5倍。

相比一下Vector，扩容Vector是原来的2倍。

int newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity);

这里初始化ArrayList大小就走了

newCapacity = minCapacity;

所以最后得出了10

elementData = Arrays.copyOf(elementData, newCapacity);

这里就是把旧的elementData复制到新的扩容后的数组去。

我们可以看下copyOf底层

public static <T> T[] copyOf(T[] original, int newLength) {
   return (T[]) copyOf(original, newLength, original.getClass());
}

第一个就是原始数组，第二个入参就是新的入参

最后扩容后就是赋值了

elementData[size++] = e;

至此add()方法原理就说的差不多了

    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);
        elementData[--size] = null; // clear to let GC do its work

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

remove这里有两种方式实现

最普通的第一种使用index去remove

其实核心思想是

int numMoved = size - index - 1;
System.arraycopy(elementData, index+1, elementData, index,numMoved);

arraycopy底层实现如下

public static native void arraycopy(Object src,  int  srcPos,
                                        Object dest, int destPos,
                                        int length);

• src原始数据
• srcPos原始数据位置
• dest目标数据
• destPos目标数据位置
• length移动长度

numMoved假设现在数据长度是16，所需要移除第10位数据，那么index就是10，numMoved=16-10-1 = 5，其实就等于10开始index+1，第11位开始的后5位，统统往前移一格

最后

elementData[--size] = null; // clear to let GC do its work

让最末尾的数据设置为null，从源码的注解上也可以看到，给出的提示是，清空它，为了让GC(垃圾回收器)去回收掉。