前言

存放数据的容器其重要性不再多说了， 项目中到处在使用， 所以从分析下相应的容器重要源码， 以便加深记忆。

源码分析

仅仅分析其最重要用的最多的方法。 重要成员变量、 初始化、 add、 remove

重要成员变量

1
2
3
4
5
6
7
8
9
private static final int DEFAULT_CAPACITY = 10;

private static final Object[] EMPTY_ELEMENTDATA = {};

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

transient Object[] elementData; 

private int size;

没有删除, 对以上就是 ArrayList 的所有成员变量。

  • DEFAULT_CAPACITY：默认大小
  • EMPTY_ELEMENTDATA：空的数据结构
  • DEFAULTCAPACITY_EMPTY_ELEMENTDATA： 空的数据结构， 在初始化不给初始化大小时赋予的容器
  • elementData： 存放数据的真正容易， 由此可见其内部是以 Object 数组结构进行存储
  • size： 数据的大小

初始化

1
2
3
4
5
6
7
8
9
10
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);
    }
}

很简单， 就是构造出给定的容器大小的容器而已。

添加

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

因为存储结构是数组， 数组是有大小边界的， 所以必须要保证调添加的数据有空间存储， 所以上就来确保空间大小。 

1
2
3
4
5
6
7
8
private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

看到没， 如果我们需要存储的数据的空间需求比申请的数组的总长度大， 就要扩容了， 也就是 grow。

1
2
3
4
5
6
7
8
9
10
11
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);
}

通过 grow 可以看出来， 先不说下面的那个 MAX_ARRAY_SIZE， 上面就是取老大小的二分之三也就是扩容原来的一半和需要的容器大小的较大的值。 最后直接把老的数据拷贝到新的大容器里。
我们紧接着看看指定坐标的添加数据怎么玩的。

1
2
3
4
5
6
7
public void add(int index, E element) {
    ensureCapacityInternal(size + 1); 
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;
}

首先上来开始先确保有足够的容器去存储， 不再分析。 紧接着就是把数组中的坐标位置到最后的数据都拷贝到坐标位置 + 1， 也就是都往后移动一位， 然后把当前坐标的数据赋予数据， size + 1。

删除

1
2
3
4
5
6
7
8
9
10
11
public E remove(int index) {
    E oldValue = (E) 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;
}

这个也好简单， 不再过多的分析， 靠 System.arrraycopy 使数据都往指定位置进一位， 然后把最后那个数据赋予空， size - 1。