Java集合-ArrayList

分析了一些map的结构，本想继续分析一下迭代器Iterator，但是想想还是用arrayLisy来分析迭代器比较省力，就先分析一下ArrayList

1. 源码分析

还是先通过源码来对ArrayList有要一个深入的了解先，首先看他的定义：

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

ArrayList继承于AbstractList，实现了List、RandomAccess、Cloneable、Serializable接口，可以看出来，他是一个可以复制、可序列化的数据类型。

看他的主要成员变量：

private transient Object[] elementData;
private int size;

非常简单，定义了一些数组用于存放数据，同时有一个size进行记录数组的指针（也可以理解为数组中存有的数据量大小），众所周知，ArrayList是一个可变的数组，那么初始化情况ArrayList的大小是多少：

public ArrayList(int initialCapacity) {
    super();
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    this.elementData = new Object[initialCapacity];
}
public ArrayList() { this(10); }

如果未指定数组大小时，默认为10，那么当他容量大于10时，他会怎么扩容呢：

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，他会将原来的elementData.length直接缩小一半，再加入原来的size大小（即新容量是原容量的1.5倍），同时新容量不能超过系统最大可用的大小（hugeCapacity(minCapacity)）.

那么我们来看一下他的添加数据add():

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}
private void ensureCapacityInternal(int minCapacity) {
    modCount++;
    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

add的方法，先检查是否需要扩容和修改计数modCount，这里看到上面的grow()的minCapacity是当前数据量+1,同时在elementData把对象填入指针位置，同时指针位置向后移动一位.

看一下get方法：

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

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

也是很简单易懂的源码，先检查需要取的数据位置是否超过了目前数据指针位置，如果是，就抛出熟悉的越界异常IndexOutOfBoundsException，如果没有，直接返回数据位置的数据对象。

其他的方法就不一一研究，同时把迭代器Iterator单开一篇进行分析。

2. 为什么ArrayList线程不安全

再回过来看一下add方法：

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

这里的核心是elementData[size++] = e，这里是三个操作：

get size value；
elementData[size] = e；
size++；

那么这就是一个非原子操作，很容易理解，当两个线程同时add数组数据，线程A现将数组中size位置填入A，线程B现将数组中size位置填入B，然后两个线程再分别将size+1，那么可以知道A数据将会丢失。