ArrayList -> AbstractList -> AbstractCollection -> List
同時實現(xiàn)了RandomAccess，Cloneable，Serializable

學(xué)習(xí)下它的設(shè)計理念和思想，看下它的構(gòu)造方法和增刪改查，

構(gòu)造 - Constructor

三個構(gòu)造函數(shù)，ArrayList()，ArrayList(int)和ArrayList(Collection)

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

這個DEFAULTCAPACITY_EMPTY_ELEMENTDATA就是一個空的數(shù)組

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

elementData就是ArrayList里實際做存儲的數(shù)組。

ArrayList(int)是創(chuàng)建一個指定大小的數(shù)組

ArrayList(Collection)是根據(jù)這個Collection里的順序創(chuàng)建一個對應(yīng)的數(shù)組，大小和這個collection的大小一致。根據(jù)這些構(gòu)造函數(shù)可以看出，如果指定collection，那么構(gòu)造出來的ArrayList在下次插入的時候必然會再次grow，x2是在所難免，這里在處理大集合的時候得注意性能問題。

增 - add

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

先判斷當(dāng)前的size+1滿不滿足當(dāng)前容器的大小，如果size+1小于等于現(xiàn)有的容器大小，那么就可以直接放入，只需要size++即可，如果size+1大于現(xiàn)有的容量，那么就需要擴容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);
}

可以看到擴容就是x 2，如果乘以2后還是不滿足這個期望的大小，那么按乘2的結(jié)果來，如過乘2后超過了最大的數(shù)組大小，其實就是最大的Integer(Integer.MAX_VALUE，即2的31次方，不過這里還減了8，注釋說有些JVM給Array加了一些頭部信息所以減8），那就得算下到底是拋出異常還是取最大值，會用到這個方法。

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

如果超過最大值，就取Integer最大值，如果沒超過就取MAX_ARRAY_SIZE。

如果是空數(shù)組，那么加第一個元素的時候，會直接使用DEFAULT_CAPACITY申請一個空間為10的數(shù)組。

還有兩種add，一種是按下標(biāo)進(jìn)行添加，add(int index, E element)，也不難，利用上面講的方法在確保有空間的時候，調(diào)用native方法System.arraycopy給要插入的元素留出空間就好。

最后一種是addAll(Collection<? extends E> c)，把c這個collection轉(zhuǎn)成array，再按順序添到原有的數(shù)組后面。

刪 Remove

remove主要分為兩個方法，一個是remove(int index)，按照數(shù)組的下標(biāo)進(jìn)行刪除，一個是remove(object o)，按照傳入的object匹配，同樣的元素進(jìn)行刪除。

remove(index)

先說按下標(biāo)刪除，很簡單，先用index對號入座找出這個元素，然后再用native方法System.arraycopy做數(shù)組拷貝，把這個元素略過再復(fù)制到同樣的數(shù)組里，最后一個元素置空為null，好讓GC可以回收內(nèi)存。

remove(obj)

再看刪除object的remove方法，這個方法的返回值是boolean，和之前那個不同，按index刪除是可以返回被刪除的元素的。如果傳入的obj是null，那么會把數(shù)組里所有為null的元素刪除，如果傳入的不是null，會把所有數(shù)據(jù)組里所有equals(obj)為true的對象都刪掉，但因為這里調(diào)用的是Object對象的equals，本質(zhì)上就是引用比較。

public boolean equals(Object obj) {
    return (this == obj);
}

說到equals簡單擴展下，對于任何非null的equals比較要滿足4點要求：

• reflextive，反射性，x.equals(x)
• symmetric，對稱性，x.equals(y) 且 y.equals(x)
• transitive，傳遞性，x.equals(y)，y.equals(z)，則x.equals(z)
• consistent，一致性，只要x.equals(y)，那么無論調(diào)用多少次，如果這兩個對象沒有變動則恒等

改 Update/Replace

在ArrayList里其實沒有update這種操作，看了下jdk8的源碼，只有在List集合里有個default默認(rèn)實現(xiàn)replaceAll，功能是傳入一個UnaryOperator就是一個函數(shù)，效果和map類似。要實現(xiàn)這個update可遍歷數(shù)組找到對應(yīng)數(shù)據(jù)，然后再add(index, obj)進(jìn)去，或者用stream再filter最后map。

查 Read/Query

數(shù)組的查就是get，按下標(biāo)來取，利用的就是數(shù)組的特性，很簡單，只需要做好邊界處理即可，不細(xì)談了這里。