【源码解析】Java8-ArrayList

### ArrayList源码分析

从一个简单的list创建说起：

List list = new ArrayList();

点进来看一下ArrayList

/**
     * Constructs an empty list with an initial capacity of ten.
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

这个注释比较有趣，构造一个容量为10的空list，容量为10还是空list。。比较有意思吧

再来看下DEFAULTCAPACITY_EMPTY_ELEMENTDATA和this.elementData是什么东西：

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    private static final long serialVersionUID = 8683452581122892189L;

    /**
     * Default initial capacity.
     */
    private static final int DEFAULT_CAPACITY = 10;

    /**
     * Shared empty array instance used for empty instances.
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};

    /**
     * Shared empty array instance used for default sized empty instances. We
     * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
     * first element is added.
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**
     * The array buffer into which the elements of the ArrayList are stored.
     * The capacity of the ArrayList is the length of this array buffer. Any
     * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
     * will be expanded to DEFAULT_CAPACITY when the first element is added.
     */
    transient Object[] elementData; // non-private to simplify nested class access
    
    /**
     * The size of the ArrayList (the number of elements it contains).
     *
     * @serial
     */
    private int size;
 }

其中DEFAULTCAPACITY_EMPTY_ELEMENTDATA为一个静态常量，一个空的Object数组，而elementData和String中的value类似也是一个空的Object数组。

10在哪？？不是说容量为10的空list么，为什么都是空的数组？

private static final int DEFAULT_CAPACITY = 10 ，我只看到了这行代码，构造的时候没用到呀，疑惑。。。

list新增元素：

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

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

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

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

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

list新增一个元素

首先做的是ensureCapacityInternal 确定数组容量
计算list容量：如果elementData是DEFAULTCAPACITY_EMPTY_ELEMENTDATA则，此时取DEFAULT_CAPACITY = 10这个变量和size+1的最大值（size是list的实际长度），因为刚初始化是空的所以肯定是默认容量大
确定最终长度并进行初始化此长度的数组

详解扩充：

什么时候才会扩充：

当前list的size+1大于此list的elementData的length的时候会扩充
怎么扩充：
1. 调用grow方法：
2. 计算新的容量 int newCapacity = oldCapacity + (oldCapacity >> 1); 左移1位 /2的一次方
  
  即原容量的1.5倍

删除元素

根据下标删除元素：

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

查找需要删除元素下标
计算偏移量然后删除

Vector和ArrayList
- Vector比ArrayList相对简陋，刚开始就会初始化elementData的长度
- 扩容的时候
  
  int newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity);
  
  扩大到原来的一倍
- 关键方法都加了synchronized 线程安全，和StringBuilder和StringBuffer有些像

Java源码解析

#Java #源码 #Java集合 #ArrayList #Java8

【源码解析】Java8-LinkList 上一篇

【源码解析】Java8-HashMap 下一篇