数据结构 - ArrayList - 《Java》

属性
构造函数
增加
删除
- remove(int index)
修改
- set(int index,E element)
查找
- indexOf(Object o)
get(int index)

属性

DEFAULT_CAPACITY，默认初始化容量１0
size 表示当前数组大小　非线程安全
modCount 统计当前数组被修改的版本次数，数据结构有变动就会＋１

/**
 * 默认初始化容量
 */
private static final int DEFAULT_CAPACITY = 10;
/**
 * 如果自定义容量为0，则会默认用它来初始化ArrayList。或者用于空数组替换。
 */
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
 * 如果没有自定义容量，则会使用它来初始化ArrayList。或者用于空数组比对。
 */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
 * 这就是ArrayList底层用到的数组
 * 非私有，以简化嵌套类访问
 * transient 在已经实现序列化的类中，不允许某变量序列化
 */
transient Object[] elementData;
/**
 * 实际ArrayList集合大小
 */
private int size;
/**
 * 可分配的最大容量
 */
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

构造函数

默认构造函数

初始化赋值的是一个空数组，当执行增加元素操作，才会分配空间大小，即向数组中添加第一个元素时，数组容量扩为10。

public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

自定义大小

根据initialCapacity 数值初始化一个空数组，如果值为0，则初始化一个空数组:

/**
 * 根据initialCapacity 初始化一个空数组
 */
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);
    }
}

集合构造

通过集合做参数的形式初始化：如果集合为空，则初始化为空数组，如果

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

增加

add(E e)

指定的元素追加到此列表的末尾。

当我们要 add 进第1个元素到 ArrayList 时，elementData.length 为0 （因为还是一个空的 list），因为执行了 ensureCapacityInternal() 方法，所以 minCapacity 此时为10。此时，minCapacity - elementData.length > 0成立，所以会进入 grow(minCapacity) 方法。
当add第2个元素时，minCapacity 为2，此时e lementData.length(容量)在添加第一个元素后扩容成 10 了。此时，minCapacity - elementData.length > 0不成立，所以不会进入（执行）grow(minCapacity) 方法。
添加第3、4···到第10个元素时，依然不会执行grow方法，数组容量都为10。
直到添加第11个元素，minCapacity(为11)比elementData.length（为10）要大。进入grow方法进行扩容。
```
/**
* 在数组末尾添加元素
*/
public boolean add(E e) {
  ensureCapacityInternal(size + 1);  // Increments modCount!!
  elementData[size++] = e;
  return true;
}
```
ensureCapacityInternal()
注意参数是size+1,size+1代表的含义是：

如果集合添加元素成功后，集合中的实际元素个数。
为了确保扩容不会出现错误。

假如不加一处理，如果默认size是0，则0+0>>1还是0。如果size是1，则1+1>>1还是1。在1.8版本后，默认ArrayList arrayList = new ArrayList();后，size应该是0.所以,size+1对扩容来讲很必要.

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

calculateCapacity

计算容量：如果elementData是空，则返回默认容量10和size+1的最大值，否则返回size+1

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

ensureExplicitCapacity

判断是否需要扩容，如果size+1 > elementData.length证明数组已经放满，则增加容量，调用grow()。

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

增加容量：默认1.5倍扩容。

获取当前数组长度=>oldCapacity
oldCapacity>>1 表示将oldCapacity右移一位(位运算)，相当于除2。再加上1，相当于新容量扩容1.5倍。
如果newCapacity<mincapacity，则newcapacity mincapacity="size+1=2" elementdata="1" newcapacity="1+1""" style="font-size: inherit;color: inherit;line-height: inherit;">>1=1</mincapacity，则newcapacity>,1<2所以如果不处理该情况，扩容将不能正确完成。
如果新容量比最大值还要大，则将新容量赋值为VM要求最大值。
将elementData拷贝到一个新的容量中。
grow
oldCapacity为旧容量，newCapacity为新容量
将oldCapacity 右移一位，其效果相当于oldCapacity /2，整句运算式的结果就是将新容量更新为旧容量的1.5倍，如果新容量大于 MAX_ARRAY_SIZE,进入(执行) hugeCapacity() 方法来比较 minCapacity 和 MAX_ARRAY_SIZE，
如果minCapacity大于最大容量，则新容量则为Integer.MAX_VALUE，否则，新容量大小则为 MAX_ARRAY_SIZE 即为 Integer.MAX_VALUE - 8。
扩容探究

当add第1个元素时，oldCapacity 为0，经比较后第一个if判断成立，newCapacity = minCapacity(为10)。但是第二个if判断不会成立，即newCapacity 不比 MAX_ARRAY_SIZE大，则不会进入 hugeCapacity 方法。数组容量为10，add方法中 return true,size增为1。
当add第11个元素进入grow方法时，newCapacity为15，比minCapacity（为11）大，第一个if判断不成立。新容量没有大于数组最大size，不会进入hugeCapacity方法。数组容量扩为15，add方法中return true,size增为11。
以此类推······ ```java /**
- 要分配的最大数组大小 */ 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); }

private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) // overflow throw new OutOfMemoryError(); //对minCapacity和MAX_ARRAY_SIZE进行比较 //若minCapacity大，将Integer.MAX_VALUE作为新数组的大小 //若MAX_ARRAY_SIZE大，将MAX_ARRAY_SIZE作为新数组的大小 //MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; }


---
<a name="PW4PN"></a>
#### add(int index, E 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++; }

rangeCheckForAdd()是越界异常检测方法。`ensureCapacityInternal()`之前有讲，着重说一下`System.arrayCopy`方法：

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

代码解释:
- Object src : 原数组
- int srcPos : 从元数据的起始位置开始
- Object dest : 目标数组
- int destPos : 目标数组的开始起始位置
- int length : 要copy的数组的长度
```java
        int[] srcArray = new int[]{2, 4, 1, 2, 3, 4, 9, 10, 15, 50};
        int[] destArray = new int[5];
        System.arraycopy(srcArray, 0, destArray, 1, 4);
        for (int i = 0; i < destArray.length; i++) {
            System.out.println(destArray[i]);
        }

`ensureCapacity`

在 add 大量元素之前用 ensureCapacity 方法，以减少增量重新分配的次数

    /**
    如有必要，增加此 ArrayList 实例的容量，以确保它至少可以容纳由minimum capacity参数指定的元素数。
     *
     * @param   minCapacity   所需的最小容量
     */
    public void ensureCapacity(int minCapacity) {
        int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
            // any size if not default element table
            ? 0
            // larger than default for default empty table. It's already
            // supposed to be at default size.
            : DEFAULT_CAPACITY;
        if (minCapacity > minExpand) {
            ensureExplicitCapacity(minCapacity);
        }
    }

ArrayList 添加大量元素之前最好先使用ensureCapacity 方法，以减少增量重新分配的次数

public class EnsureCapacityTest {
    public static void main(String[] args) {
        ArrayList<Object> list = new ArrayList<Object>();
        final int N = 10000000;
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < N; i++) {
            list.add(i);
        }
        long endTime = System.currentTimeMillis();
        System.out.println("使用ensureCapacity方法前："+(endTime - startTime));
        list = new ArrayList<Object>();
        long startTime1 = System.currentTimeMillis();
        list.ensureCapacity(N);
        for (int i = 0; i < N; i++) {
            list.add(i);
        }
        long endTime1 = System.currentTimeMillis();
        System.out.println("使用ensureCapacity方法后："+(endTime1 - startTime1));
    }
}

删除

remove(int index)

删除指定下标的元素。

public E remove(int index) {
    // 检测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 var1) {
        int var2;
        if (var1 == null) {
            for(var2 = 0; var2 < this.size; ++var2) {
                if (this.elementData[var2] == null) {
                    this.fastRemove(var2);
                    return true;
                }
            }
        } else {
            for(var2 = 0; var2 < this.size; ++var2) {
                if (var1.equals(this.elementData[var2])) {
                    this.fastRemove(var2);
                    return true;
                }
            }
        }
        return false;
    }
    private void fastRemove(int var1) {
        ++this.modCount;
        int var2 = this.size - var1 - 1;
        if (var2 > 0) {
            System.arraycopy(this.elementData, var1 + 1, this.elementData, var1, var2);
        }
        this.elementData[--this.size] = null;
    }

修改

set(int index,E element)

public E set(int index, E element) {
    rangeCheck(index);
    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}

查找

indexOf(Object o)

根据Object对象获取数组中的索引值。如果o为空，则返回数组中第一个为空的索引；不为空也类似。
注意：通过源码可以看到，该方法是允许传空值进来的。

public int indexOf(Object o) {
    if (o == null) {
        for (int i = 0; i < size; i++)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = 0; i < size; i++)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}

get(int index)

返回指定下标处的元素的值。rangeCheck(index)会检测index值是否合法，如果合法则返回索引对应的值。

public E get(int index) {
   rangeCheck(index);
   return elementData(index);
}