1. 構(gòu)造方法
ArrayList 有三個構(gòu)造方法
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;
/**
* Constructs an empty list with the specified initial capacity.
*
* @param initialCapacity the initial capacity of the list
* @throws IllegalArgumentException if the specified initial capacity
* is negative
*/
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);
}
}
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/**
* Constructs a list containing the elements of the specified
* collection, in the order they are returned by the collection's
* iterator.
*
* @param c the collection whose elements are to be placed into this list
* @throws NullPointerException if the specified collection is null
*/
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// defend against c.toArray (incorrectly) not returning Object[]
// (see e.g. https://bugs.openjdk.java.net/browse/JDK-6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
ArrayList 把數(shù)據(jù)都存儲到 transient Object[] elementData 數(shù)組中，transient 是保證對象不被序列化（一般用于不可暴露的敏感信息或者無序序列化的對象）。
1.1 無參構(gòu)造 ArrayList()
this.elementData 被賦值為空數(shù)組 DEFAULTCAPACITY_EMPTY_ELEMENTDATA
1.2 ArrayList(int initialCapacity)
初始化一個 initialCapacity 長度的數(shù)組賦值給 elementData
1.3 ArrayList(Collection<? extends E> c)
將入?yún)?shù)集合轉(zhuǎn)成數(shù)組賦值給 elementData
2. 添加元素
/**
* This helper method split out from add(E) to keep method
* bytecode size under 35 (the -XX:MaxInlineSize default value),
* which helps when add(E) is called in a C1-compiled loop.
*/
private void add(E e, Object[] elementData, int s) {
if (s == elementData.length)
elementData = grow();
elementData[s] = e;
size = s + 1;
}
/**
* Appends the specified element to the end of this list.
*
* @param e element to be appended to this list
* @return {@code true} (as specified by {@link Collection#add})
*/
public boolean add(E e) {
modCount++;
add(e, elementData, size);
return true;
}
modCount 是用來記錄數(shù)組 elementData 變化的次數(shù)。
當(dāng)調(diào)用 add(E e) 方法添加元素時，內(nèi)部又調(diào)用了重載的私有方法 add(E e, Object[] elementData, int s)。
這里要明確兩個東西：
一個是 size，每添加一個元素就 +1，每刪除一個元素就 -1，它代表的是集合實際的元素個數(shù)；
另一個是 elementData.length，它是數(shù)組的真是長度，也就是數(shù)組當(dāng)前的最大容量 capacity。
add(E e, Object[] elementData, int s) 通過 size 和 capacity的比較，判斷是否需要擴容，也就是當(dāng)實際元素個數(shù)和集合容量相等的時候，就需要擴容了（比如，集合的容量是10，添加第 10 個元素時，就需要先擴容，擴容后在添加元素），擴容用到的方法是 grow()。
/**
* Increases the capacity to ensure that it can hold at least the
* number of elements specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity
* @throws OutOfMemoryError if minCapacity is less than zero
*/
private Object[] grow(int minCapacity) {
return elementData = Arrays.copyOf(elementData,
newCapacity(minCapacity));
}
private Object[] grow() {
return grow(size + 1);
}
可以看到擴容最終用到的是 Arrays.copyOf(arr, newLength) 方法，它的作用是 新建一個 newLength 長度的數(shù)組，然后把原來的數(shù)組 arr 中的元素復(fù)制到新數(shù)組。如果 arr.length > newLength，arr 中多余的數(shù)據(jù)就放棄；如果 arr.length < newLength，新數(shù)組中的其他位置就空著。
擴容的關(guān)鍵在于 newCapacity(minCapacity) 方法
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private int newCapacity(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity <= 0) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
return Math.max(DEFAULT_CAPACITY, minCapacity);
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return minCapacity;
}
return (newCapacity - MAX_ARRAY_SIZE <= 0)
? newCapacity
: hugeCapacity(minCapacity);
}
oldCapacity >> 1，將 oldCapacity 右移一位，達到整除 2 的效果（10 二進制位 1010，右移一位變成 0101，對應(yīng)十進制 5；9(1001) >>1,結(jié)果是 4(0100)）。這個地方妙啊，要我來肯定是用 2 整除，肯定沒這個高效。
這里做了判斷，if (newCapacity - minCapacity <= 0) 對應(yīng)一下幾種情況：
- minCapacity 為負(fù)數(shù)，拋出異常
- elementData 為空數(shù)組，那么 newCapacity 就是 DEFAULT_CAPACITY(默認(rèn)值是10) 和 minCapacity 中最大的，空數(shù)組的size +1 = 1，所以空數(shù)組第一次擴容是直接擴到 10。
- 初始化的集合 capacity 較小，例如 1 和 2，此時 return minCapacity;
沒能在上個判斷中 return 的又分為兩種情況
- 比較正常的數(shù)組，newCapacity <= MAX_ARRAY_SIZE，直接返回 newCapacity
- 超大集合，需要另一個方法 hugeCapacity(minCapacity)，這么大的數(shù)據(jù)，一般應(yīng)該不會用集合了吧。。。。
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_VALUE 個元素數(shù)量，就是 ArrayList 的極限了
3 移除元素
/**
* Removes the first occurrence of the specified element from this list,
* if it is present. If the list does not contain the element, it is
* unchanged. More formally, removes the element with the lowest index
* {@code i} such that
* {@code Objects.equals(o, get(i))}
* (if such an element exists). Returns {@code true} if this list
* contained the specified element (or equivalently, if this list
* changed as a result of the call).
*
* @param o element to be removed from this list, if present
* @return {@code true} if this list contained the specified element
*/
public boolean remove(Object o) {
final Object[] es = elementData;
final int size = this.size;
int i = 0;
found: {
if (o == null) {
for (; i < size; i++)
if (es[i] == null)
break found;
} else {
for (; i < size; i++)
if (o.equals(es[i]))
break found;
}
return false;
}
fastRemove(es, i);
return true;
}
/**
* Private remove method that skips bounds checking and does not
* return the value removed.
*/
private void fastRemove(Object[] es, int i) {
modCount++;
final int newSize;
if ((newSize = size - 1) > i)
System.arraycopy(es, i + 1, es, i, newSize - i);
es[size = newSize] = null;
}
其中 found: 是個標(biāo)志用于配合 break 跳出到指定位置，格式為 "字符"+":" 使用時字符可以自己定義，如：out：，in:
found 中的代碼就是遍歷數(shù)組，尋找要移除的對象，找不到則直接返回 false，找到了就跳出循環(huán)，執(zhí)行 fastRemove。
最終刪除過程，是利用本地方法 System.arraycopy(src, srcPos, dest, destPos, length) 實現(xiàn)
/**
* @param src the source array.
* @param srcPos starting position in the source array.
* @param dest the destination array.
* @param destPos starting position in the destination data.
* @param length the number of array elements to be copied.
*/
@HotSpotIntrinsicCandidate
public static native void arraycopy(Object src, int srcPos,
Object dest, int destPos,
int length);
這個方法，用途就是將 src 數(shù)組的第 srcPos 個元素開始，length 個元素，覆蓋 dest 數(shù)組中的第 destPos 之后的元素。
此處實際上就是將需要刪除的元素之后的所有元素向前移動一位（要保證數(shù)組元素的連續(xù)），要刪除的元素就被后面的覆蓋了，然后再把最后一個元素賦值為 null。
用 add(int index, E element) 添加元素時也類似，先把 index 位置及之后的元素向后移動一位，然后再把 index 位置的元素賦值為 element。
4 結(jié)論
4.1 擴容機制
- ArrayList 內(nèi)部用數(shù)組 Object[] elementData 來存放數(shù)據(jù)。
- ArrayList三個構(gòu)造方法：
2.1. 無參構(gòu)造產(chǎn)生的 ArrayList 對象內(nèi)部是個 length 為 0 的空數(shù)組。
2.2. ArrayList(int initialCapacity) 構(gòu)造方法會生成一個，長度為 initialCapacity 的數(shù)組，initialCapacity 為負(fù)數(shù)則會報錯
2.3. ArrayList(Collection<? extends E> c) 構(gòu)造方法會利用 c.toArray()，將集合 c 轉(zhuǎn)變成 ArrayList 對象內(nèi)部的數(shù)組，長度自然為 c.size() - ArrayList 內(nèi)部有一個重要參數(shù) size，它代表的是 ArrayList 中的實際元素個數(shù)，添加元素的時候 size 自增 1，刪除數(shù)據(jù)是自減 1；另外 elementData.length,代表的是Capacity，也就是 ArrayList 當(dāng)前的最大容量，size <= elementData.length。
- 觸發(fā)擴容：
4.1. elementData.length 為 0 時，添加第一個元素就會觸發(fā)擴容，此時會將 elementData 擴容成一個長度為 DEFAULT_CAPACITY = 10 的數(shù)組，并將第一個元素賦值給 elementData[1]
4.2. elementData.length 不為 0 時，當(dāng)添加第 elementData.length 個元素時，會觸發(fā)擴容 - 使用 grow 方法擴容
5.1 常規(guī)情況下，通過 newCapacity = oldCapacity + (oldCapacity >> 1) 的方式擴容，即每次增加原來容量的 1/2，即擴容到原來的 1.5 倍。（如：10>15>22....）
5.2 elementData.length 為 0，直接擴容到 10
5.3 如果 Integer.MAX_VALUE > newCapacity > MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8, 擴容結(jié)果是擴容為長度為 Integer.MAX_VALUE 的數(shù)組，并且不會再擴容，如果真的添加到這個數(shù)組的最后一位，仍會觸發(fā)擴容機制，導(dǎo)致 newCapacity = oldCapacity + (oldCapacity >> 1) 為負(fù)數(shù)，最終報錯 OutOfMemoryError。
5.4 oldCapacity + (oldCapacity >> 1) 的理論值大于 Integer.MAX_VALUE 時，實際的結(jié)果是負(fù)數(shù)（因為超出了Integer的范圍），此時會直接報 OutOfMemoryError。
4.2 適用場景
查：ArrayList 底層結(jié)構(gòu)是數(shù)組，所以遍歷方便。
增、刪：add(e) 添加元素時，最末尾添加；add(index，e) 添加元素時，index 之后的元素全部后移一位，remove 刪除元素時，該元素的之后的元素全部前移一位。運算量較大，并不適合。
4.3 線程安全
添加、刪除元素都 涉及 size 加減的問題，并沒有原子性的保障，多線程操作時 size 會混亂。
擴容涉及 size 和 elementData.length 的比較和判斷，多個線程操作也會導(dǎo)致誤判。
CopyOnWriteArryList 可以并發(fā)讀，寫時復(fù)制，可以解決線程安全問題。
