看了一周的SpringMVC請求的過程，突然對老伙計，ArrayList這些我們使用比較多的集合類產(chǎn)生了興趣，下面開始解析ArrayList源碼
ArrayList 繼承了AbstractList類
實現(xiàn)的接口有：List, RandomAccess, Cloneable, java.io.Serializable
首先ArrayList有四個靜態(tài)域
1、serialVersionUID：序列化和反序列需要用到的id
2、DEFAULT_CAPACITY：默認的容量大小
3、EMPTY_ELEMENTDATA：是一個靜態(tài)的空數(shù)組
4、DEFAULTCAPACITY_EMPTY_ELEMENTDATA：作用同EMPTY_ELEMENTDATA 一樣。區(qū)別是這里表明創(chuàng)建這個類的時候沒有指定capacity而是使用默認的DEFAULT_CAPACITY 。
transient Object[] elementData;//臨時存放元素的地方，不加入序列化
ArrayList有三種構(gòu)造函數(shù)：
第一種無參構(gòu)造函數(shù)：
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
第二種是設(shè)置容量大小的構(gòu)造函數(shù)
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);
}
}
第三種是直接傳入一個集合作為參數(shù)：
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;
}
}
前面兩種構(gòu)造方法都比較簡單，第三個構(gòu)造方法有點不一樣的地方，首先第一個if語句，將elementData.length賦值給了size,然后進行里層的if語句判斷，為什么還要進行類型判斷呢，注釋中解釋道
c.toArray might (incorrectly) not return Object[] (see 6260652)，查過這個代碼后，發(fā)覺問題源自參數(shù)，
如果是ArrayList.toArray()方法，返回的數(shù)組就是Object[]類型，但是Arrays.asList(...).toArray,返回的數(shù)組呢
Arrays.asList(...)返回的是class java.util.Arrays$ArrayList類型，這種類型的toArray()方法返回的是實際數(shù)據(jù)的類型，String類型的，那么toArray()方法就會返回String類型，就是因為有這種情況，所以在里層加多了一個判斷，將elementData類型轉(zhuǎn)換成Object[]類型。
在看過數(shù)據(jù)的增加的時候，印象最深的當(dāng)屬對于容量的處理工作，當(dāng)數(shù)組大小超過默認的容器大小后，那么需要執(zhí)行擴容語句，擴容涉及的部分：
public void ensureCapacity(int minCapacity)
private static int calculateCapacity(Object[] elementData, int minCapacity)
private void ensureCapacityInternal(int minCapacity)
private void ensureExplicitCapacity(int minCapacity)
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8
private void grow(int minCapacity)
private static int hugeCapacity
看到這些方法，最直觀的是不是ensureCapacity是public，而其他的方法都是private,實際上，ensureCapacity方法在內(nèi)部源碼中是沒有調(diào)用到的，這個方法是提供給用戶進行設(shè)置容量大小的。他的代碼如下：
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);
}
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
如果調(diào)用該方法的集合是空集，那么就會默認給這個集合內(nèi)的elementData初始化大小10的容量，否則容量為0，在下邊的增加數(shù)據(jù)的代碼塊中，都出現(xiàn)了ensureCpacityInternal()方法的調(diào)用，最終完成擴容工作的是ensureExplicitCapacity()方法。
擴容數(shù)組：
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);
}
這個方法的思路就是，先將原來的容量增加原來容量的一般，然后跟傳入的容量進行比較，如果小于傳入的容量，那么就將傳入的容量賦值給擴容的容量，然后進行第二次判斷，判斷擴容的容量是否會大于數(shù)組的最大容量，如果大于數(shù)組最大的容量，那么將會有兩個選擇，如果傳入的容量大小大于數(shù)組最大容量，則將擴容的容量賦值為整型的最大值，如果傳入的容量大小小于數(shù)組最大容量，則將擴容的容量賦值為數(shù)組最大的容量。
增刪
1、增加
public boolean add(E e)
public void add(int index, E element)
public boolean addAll(Collection<? extends E> c)
public boolean addAll(int index, Collection<? extends E> c)
增加的方法四種，剛剛說過，四種都調(diào)用了擴容判定的方法
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
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++;
}
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
int numMoved = size - index;
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}
這里我要講的是System.arraycopy()的調(diào)用，該方法的參數(shù)順序為：拷貝數(shù)組，開始位置，拷入數(shù)組，開始位置，長度。這也是我遇到的第一個native方法，在底層源碼中看不到native的實現(xiàn)，拷貝的時候要注意拷貝的長度計算，跟刪除略有不同。
2、刪除
public E remove(int index)
public boolean remove(Object o)
private void fastRemove(int index)
刪除涉及這三個方法的使用
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
}
刪除中，可以看到在長度上，增加是length = size -index ,而刪除是length = size -index -1
這個方面自己算個例子就很容易明白了，這邊要注意的是，刪除一個object的時候，要判斷變量是否為空，為空直接使用==null的方式，不為空要使用equals()方法進行判斷，還有一個點是，刪除完數(shù)據(jù)后，要記得將位置置為null，讓java的gc機制回收不用的內(nèi)存空間
講完ArrayList對于增刪的處理后，下邊講下這兩個方法
1、public boolean removeAll(Collection<?> c)
2、public boolean retainAll(Collection<?> c)
第一個方法的代碼為：
public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, false);
}
第二個方法的代碼為：
public boolean retainAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, true);
}
可以看到，首先這兩個方法先判斷傳入的集合進行了非空檢測，檢測完后返回的是batchRemove()方法的返回值，不同的是第二個參數(shù)設(shè)置一個為true，一個為false。
為了更容易理解，我先在這邊介紹一下這兩個方法的功能
第一個方法是移除list集合中有關(guān)集合c的元素
第二個方法是移除list集合中除集合c元素外的其他所有元素
也就是兩個方法互為補集
下邊來看下代碼塊的實現(xiàn)
private boolean batchRemove(Collection<?> c, boolean complement) {
final Object[] elementData = this.elementData;
int r = 0, w = 0;
boolean modified = false;
try {
for (; r < size; r++)
if (c.contains(elementData[r]) == complement)
elementData[w++] = elementData[r];
} finally {
// Preserve behavioral compatibility with AbstractCollection,
// even if c.contains() throws.
if (r != size) {
System.arraycopy(elementData, r,
elementData, w,
size - r);
w += size - r;
}
if (w != size) {
// clear to let GC do its work
for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size - w;
size = w;
modified = true;
}
}
return modified;
}
首先創(chuàng)建了一個數(shù)組用來接收臨時數(shù)組，然后分別創(chuàng)建了兩個整型，一個是r，一個是w，整型r的作用類似于for循環(huán)第一個參數(shù)new出來的變量，用于遍歷整個數(shù)組，整型w的作用是計算經(jīng)過操作后，篩選出來的元素的個數(shù)，還有個布爾類型modified，默認為false，判斷方法執(zhí)行是否成功的元素。
所以r一般是大于w的，我們看到在finally代碼塊里有兩個if語句，第一個判斷語句r!=size，遍歷整個數(shù)組的情況下，r是等于size的，只有出現(xiàn)異常，無法再繼續(xù)執(zhí)行下去的時候r!=size,將r后邊為處理的數(shù)據(jù)加到w的后邊。第二個判斷語句w!=size,如果w等于size，說明篩選出來的元素是整個數(shù)組，那么就沒有需要剔除的元素，也就是沒有修改集合，返回默認的false,如果w!=size,則將List數(shù)組的w之后包括w全部置為null，讓GC回收。
代碼接著往下走，我們發(fā)現(xiàn)到了序列化和反序列化的方法，ArrayList都已經(jīng)實現(xiàn)了Serializable接口，為何還要自己寫序列化和反序列化方法呢，看代碼：
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException{
// Write out element count, and any hidden stuff
int expectedModCount = modCount;
s.defaultWriteObject();
// Write out size as capacity for behavioural compatibility with clone()
s.writeInt(size);
// Write out all elements in the proper order.
for (int i=0; i<size; i++) {
s.writeObject(elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
elementData = EMPTY_ELEMENTDATA;
// Read in size, and any hidden stuff
s.defaultReadObject();
// Read in capacity
s.readInt(); // ignored
if (size > 0) {
// be like clone(), allocate array based upon size not capacity
int capacity = calculateCapacity(elementData, size);
SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity);
ensureCapacityInternal(size);
Object[] a = elementData;
// Read in all elements in the proper order.
for (int i=0; i<size; i++) {
a[i] = s.readObject();
}
}
}
發(fā)現(xiàn)了什么，序列化和反序列化中的循環(huán)變量是以size為準的，在ArrayList中，有兩個變量容易弄混，一個是size,一個是elementData.length，第一個是數(shù)組中實際擁有元素的個數(shù)，第二個是數(shù)組的長度，數(shù)組長度是大于等于數(shù)組擁有元素個數(shù)的，所以如果自己寫序列化和反序列化語句，那么可以節(jié)省這部分的內(nèi)存開銷。
再之后的代碼就是關(guān)于迭代器方面的，這部分我還沒研究，暫時不講?？v觀ArrayList源碼，通篇有兩個要特別注意的點，就是Arrays.copyOf()和System.arraycopy()
copyOf()的作用是拿來擴容用的
arraycopy()的作用是進行數(shù)組內(nèi)元素移位用的
這是二者最大區(qū)別，并且這兩個方法也不是一個類的方法
copyOf()是Arrays的方法，arraycopy()是System的方法
說到這里，就有必要說一下ArrayList的toArray()方法，看代碼：
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
這個是不帶參數(shù)的toArray(),內(nèi)部是通過Arrays.copyOf來實現(xiàn)的，比較簡單
public <T> T[] toArray(T[] a) {
if (a.length < size)
// Make a new array of a's runtime type, but my contents:
return (T[]) Arrays.copyOf(elementData, size, a.getClass());
System.arraycopy(elementData, 0, a, 0, size);
if (a.length > size)
a[size] = null;
return a;
}
而這個帶有數(shù)組類型參數(shù)的toArray()，就相對復(fù)雜點，但是對比兩個方法，可以看出來無參的toArray()方法是使用Arrays.copyOf(),有參的toArray()方法是通過System.arraycopy()和Arrays.copyOf()進行實現(xiàn)的，我解釋一下有參的方法實現(xiàn)。首先List.toArray(T)，，這個方法是將list的數(shù)據(jù)拷貝到T中，并且返回的也是T的類型，先判斷T和List的長度，如果拷入數(shù)組T的長度小于拷貝數(shù)組List的長度，則調(diào)用Arrays.copyOf()方法，直接將拷貝數(shù)組進行類型轉(zhuǎn)換，如果拷入數(shù)組T的長度大于拷貝數(shù)組List的長度，則調(diào)用System.arraycopy()將拷入數(shù)組T的0~List.length范圍數(shù)據(jù)置為List,然后list.length的位置置為null,這樣其實可以達到區(qū)分拷貝前后數(shù)據(jù)的作用，測試代碼如下：
public void testGoods() {
ArrayList<String> list = new ArrayList<>(Arrays.asList("s","t","r"));
String[] str = {"q","w","r","c","z"};
str = list.toArray(str);
for (String s :str)
System.out.println(s);
}
效果圖：
如果我將str的數(shù)據(jù)刪除到只剩下一個數(shù)據(jù)，效果圖如下：
這兩種情況通過代碼就很直觀的顯示出來了。
總結(jié)
1、如果在聲明ArrayList的時候不設(shè)初始值，那么ArrayList會默認設(shè)置一個容量為10的數(shù)組，但是ArrayList的大小還是為0的
2、ArrayList可以看成是一個動態(tài)的數(shù)組，相比較與數(shù)組來說，ArrayList可以用ensureCapacityInternal方法自動擴容，在向ArrayList添加元素的時候，ArrayList會先檢測現(xiàn)在數(shù)組的容量是否足夠，若不夠，ArrayList會將數(shù)組的容量擴大為原來的1.5倍，如果還不夠，就用傳進來的參數(shù)作為數(shù)組的容量。如果我們在知道存儲元素多少的時候，盡量給ArrayList設(shè)定一個初始容量，這樣就可以減少ArrayList的自動擴容，減少數(shù)組元素的移動來提高程序的性能。
3、ArrayList在增加或刪除元素的時候，都需要將數(shù)組里面的元素移動到另一個數(shù)組中，這是非常耗時間的，所以遇到需要對元素進行頻繁的刪除和添加的集合時，這時候選用LinkedList要比ArrayList好很多，如果遇到在集合中查找元素比較多的操作時，ArrayList又是一個不錯的選擇，因為ArrayList直接可以用下標(biāo)就可以獲取到元素。
4、在讀ArrayList源碼的時候要注意ensureCapacityInternal擴容方法和System.arraycopy(original, 0, copy, 0,length)方法。
問題解析：
來講一下ArrayList中遇到的一個問題，就是關(guān)于addAll(int index,Collection<? extends E> e)方法
該方法第一行代碼就是對index進行的判斷
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
int numMoved = size - index;
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
可以看到第一個方法對于index的判斷，index大于size或者小于0則拋出異常，也就是說size>=index>=0
我當(dāng)時的疑問出于size怎么可以等于index,因為index是數(shù)組的下標(biāo)，肯定比個數(shù)少一，然后在大佬的指點下，發(fā)覺，如果我的index==size,那么就是在數(shù)組尾插入集合C，這樣是符合標(biāo)準的，但是index==size，那么原數(shù)組就不需要移動了，如果沒有加上長度的判定，那么會出現(xiàn)BUG，怪自己粗心。
參考鏈接：
https://blog.csdn.net/wangbiao007/article/details/52474756
http://www.cnblogs.com/ITtangtang/p/3948555.html#toArray
https://blog.csdn.net/weixin_39148512/article/details/79234817
https://blog.csdn.net/u011518120/article/details/52026076
https://www.cnblogs.com/gxl1995/p/7534171344218b3784f1beb90d621337.html
