看了一周的SpringMVC請(qǐng)求的過(guò)程绪杏，突然對(duì)老伙計(jì)，ArrayList這些我們使用比較多的集合類產(chǎn)生了興趣淑翼，下面開(kāi)始解析ArrayList源碼
ArrayList 繼承了AbstractList類
實(shí)現(xiàn)的接口有：List, RandomAccess, Cloneable, java.io.Serializable
首先ArrayList有四個(gè)靜態(tài)域
1塔粒、serialVersionUID：序列化和反序列需要用到的id
2、DEFAULT_CAPACITY：默認(rèn)的容量大小
3身冬、EMPTY_ELEMENTDATA：是一個(gè)靜態(tài)的空數(shù)組
4衅胀、DEFAULTCAPACITY_EMPTY_ELEMENTDATA：作用同EMPTY_ELEMENTDATA 一樣。區(qū)別是這里表明創(chuàng)建這個(gè)類的時(shí)候沒(méi)有指定capacity而是使用默認(rèn)的DEFAULT_CAPACITY 酥筝。
transient Object[] elementData;//臨時(shí)存放元素的地方滚躯，不加入序列化
ArrayList有三種構(gòu)造函數(shù)：
第一種無(wú)參構(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);
}
}
第三種是直接傳入一個(gè)集合作為參數(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)造方法都比較簡(jiǎn)單，第三個(gè)構(gòu)造方法有點(diǎn)不一樣的地方嘿歌，首先第一個(gè)if語(yǔ)句掸掏，將elementData.length賦值給了size,然后進(jìn)行里層的if語(yǔ)句判斷，為什么還要進(jìn)行類型判斷呢宙帝，注釋中解釋道
c.toArray might (incorrectly) not return Object[] (see 6260652)丧凤，查過(guò)這個(gè)代碼后，發(fā)覺(jué)問(wèn)題源自參數(shù)步脓，
如果是ArrayList.toArray()方法愿待，返回的數(shù)組就是Object[]類型浩螺，但是Arrays.asList(...).toArray,返回的數(shù)組呢
Arrays.asList(...)返回的是class java.util.Arrays$ArrayList類型，這種類型的toArray()方法返回的是實(shí)際數(shù)據(jù)的類型呼盆，String類型的年扩，那么toArray()方法就會(huì)返回String類型，就是因?yàn)橛羞@種情況访圃，所以在里層加多了一個(gè)判斷厨幻，將elementData類型轉(zhuǎn)換成Object[]類型。
在看過(guò)數(shù)據(jù)的增加的時(shí)候腿时，印象最深的當(dāng)屬對(duì)于容量的處理工作况脆，當(dāng)數(shù)組大小超過(guò)默認(rèn)的容器大小后，那么需要執(zhí)行擴(kuò)容語(yǔ)句批糟，擴(kuò)容涉及的部分：
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,實(shí)際上徽鼎，ensureCapacity方法在內(nèi)部源碼中是沒(méi)有調(diào)用到的盛末，這個(gè)方法是提供給用戶進(jìn)行設(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)用該方法的集合是空集否淤，那么就會(huì)默認(rèn)給這個(gè)集合內(nèi)的elementData初始化大小10的容量悄但，否則容量為0，在下邊的增加數(shù)據(jù)的代碼塊中石抡，都出現(xiàn)了ensureCpacityInternal()方法的調(diào)用檐嚣，最終完成擴(kuò)容工作的是ensureExplicitCapacity()方法。
擴(kuò)容數(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);
}
這個(gè)方法的思路就是啰扛，先將原來(lái)的容量增加原來(lái)容量的一般嚎京，然后跟傳入的容量進(jìn)行比較，如果小于傳入的容量隐解，那么就將傳入的容量賦值給擴(kuò)容的容量鞍帝，然后進(jìn)行第二次判斷，判斷擴(kuò)容的容量是否會(huì)大于數(shù)組的最大容量煞茫，如果大于數(shù)組最大的容量膜眠，那么將會(huì)有兩個(gè)選擇，如果傳入的容量大小大于數(shù)組最大容量溜嗜，則將擴(kuò)容的容量賦值為整型的最大值宵膨，如果傳入的容量大小小于數(shù)組最大容量，則將擴(kuò)容的容量賦值為數(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)
增加的方法四種，剛剛說(shuō)過(guò)土全，四種都調(diào)用了擴(kuò)容判定的方法
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ù)順序?yàn)椋嚎截悢?shù)組会涎，開(kāi)始位置，拷入數(shù)組瑞凑，開(kāi)始位置末秃，長(zhǎng)度。這也是我遇到的第一個(gè)native方法籽御，在底層源碼中看不到native的實(shí)現(xiàn)练慕，拷貝的時(shí)候要注意拷貝的長(zhǎng)度計(jì)算，跟刪除略有不同技掏。
2铃将、刪除
public E remove(int index)
public boolean remove(Object o)
private void fastRemove(int index)
刪除涉及這三個(gè)方法的使用
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
}
刪除中，可以看到在長(zhǎng)度上哑梳，增加是length = size -index ,而刪除是length = size -index -1
這個(gè)方面自己算個(gè)例子就很容易明白了劲阎，這邊要注意的是，刪除一個(gè)object的時(shí)候鸠真，要判斷變量是否為空悯仙，為空直接使用==null的方式，不為空要使用equals()方法進(jìn)行判斷吠卷，還有一個(gè)點(diǎn)是锡垄，刪除完數(shù)據(jù)后，要記得將位置置為null撤嫩，讓java的gc機(jī)制回收不用的內(nèi)存空間
講完ArrayList對(duì)于增刪的處理后，下邊講下這兩個(gè)方法
1蠢终、public boolean removeAll(Collection<?> c)
2序攘、public boolean retainAll(Collection<?> c)
第一個(gè)方法的代碼為：
public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, false);
}
第二個(gè)方法的代碼為：
public boolean retainAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, true);
}
可以看到，首先這兩個(gè)方法先判斷傳入的集合進(jìn)行了非空檢測(cè)寻拂，檢測(cè)完后返回的是batchRemove()方法的返回值程奠，不同的是第二個(gè)參數(shù)設(shè)置一個(gè)為true，一個(gè)為false祭钉。
為了更容易理解瞄沙，我先在這邊介紹一下這兩個(gè)方法的功能
第一個(gè)方法是移除list集合中有關(guān)集合c的元素
第二個(gè)方法是移除list集合中除集合c元素外的其他所有元素
也就是兩個(gè)方法互為補(bǔ)集
下邊來(lái)看下代碼塊的實(shí)現(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)建了一個(gè)數(shù)組用來(lái)接收臨時(shí)數(shù)組，然后分別創(chuàng)建了兩個(gè)整型慌核，一個(gè)是r距境，一個(gè)是w，整型r的作用類似于for循環(huán)第一個(gè)參數(shù)new出來(lái)的變量垮卓，用于遍歷整個(gè)數(shù)組垫桂，整型w的作用是計(jì)算經(jīng)過(guò)操作后，篩選出來(lái)的元素的個(gè)數(shù)粟按，還有個(gè)布爾類型modified诬滩，默認(rèn)為false霹粥，判斷方法執(zhí)行是否成功的元素。
所以r一般是大于w的疼鸟，我們看到在finally代碼塊里有兩個(gè)if語(yǔ)句后控，第一個(gè)判斷語(yǔ)句r!=size，遍歷整個(gè)數(shù)組的情況下空镜，r是等于size的浩淘，只有出現(xiàn)異常，無(wú)法再繼續(xù)執(zhí)行下去的時(shí)候r!=size,將r后邊為處理的數(shù)據(jù)加到w的后邊姑裂。第二個(gè)判斷語(yǔ)句w!=size,如果w等于size馋袜，說(shuō)明篩選出來(lái)的元素是整個(gè)數(shù)組，那么就沒(méi)有需要剔除的元素舶斧，也就是沒(méi)有修改集合欣鳖，返回默認(rèn)的false,如果w!=size,則將List數(shù)組的w之后包括w全部置為null，讓GC回收茴厉。
代碼接著往下走泽台，我們發(fā)現(xiàn)到了序列化和反序列化的方法，ArrayList都已經(jīng)實(shí)現(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為準(zhǔn)的嗜闻，在ArrayList中蜕依，有兩個(gè)變量容易弄混，一個(gè)是size,一個(gè)是elementData.length琉雳，第一個(gè)是數(shù)組中實(shí)際擁有元素的個(gè)數(shù)样眠，第二個(gè)是數(shù)組的長(zhǎng)度，數(shù)組長(zhǎng)度是大于等于數(shù)組擁有元素個(gè)數(shù)的翠肘，所以如果自己寫序列化和反序列化語(yǔ)句檐束，那么可以節(jié)省這部分的內(nèi)存開(kāi)銷。
再之后的代碼就是關(guān)于迭代器方面的束倍，這部分我還沒(méi)研究被丧，暫時(shí)不講⌒髅茫縱觀ArrayList源碼捺僻，通篇有兩個(gè)要特別注意的點(diǎn)器钟，就是Arrays.copyOf()和System.arraycopy()
copyOf()的作用是拿來(lái)擴(kuò)容用的
arraycopy()的作用是進(jìn)行數(shù)組內(nèi)元素移位用的
這是二者最大區(qū)別多糠，并且這兩個(gè)方法也不是一個(gè)類的方法
copyOf()是Arrays的方法温技，arraycopy()是System的方法
說(shuō)到這里，就有必要說(shuō)一下ArrayList的toArray()方法廊移，看代碼：
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
這個(gè)是不帶參數(shù)的toArray(),內(nèi)部是通過(guò)Arrays.copyOf來(lái)實(shí)現(xiàn)的糕簿，比較簡(jiǎ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;
}
而這個(gè)帶有數(shù)組類型參數(shù)的toArray()探入，就相對(duì)復(fù)雜點(diǎn)，但是對(duì)比兩個(gè)方法懂诗，可以看出來(lái)無(wú)參的toArray()方法是使用Arrays.copyOf(),有參的toArray()方法是通過(guò)System.arraycopy()和Arrays.copyOf()進(jìn)行實(shí)現(xiàn)的蜂嗽，我解釋一下有參的方法實(shí)現(xiàn)。首先List.toArray(T)殃恒，植旧，這個(gè)方法是將list的數(shù)據(jù)拷貝到T中，并且返回的也是T的類型离唐，先判斷T和List的長(zhǎng)度病附，如果拷入數(shù)組T的長(zhǎng)度小于拷貝數(shù)組List的長(zhǎng)度，則調(diào)用Arrays.copyOf()方法亥鬓，直接將拷貝數(shù)組進(jìn)行類型轉(zhuǎn)換完沪，如果拷入數(shù)組T的長(zhǎng)度大于拷貝數(shù)組List的長(zhǎng)度，則調(diào)用System.arraycopy()將拷入數(shù)組T的0~List.length范圍數(shù)據(jù)置為L(zhǎng)ist,然后list.length的位置置為null,這樣其實(shí)可以達(dá)到區(qū)分拷貝前后數(shù)據(jù)的作用嵌戈，測(cè)試代碼如下：
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ù)刪除到只剩下一個(gè)數(shù)據(jù)覆积，效果圖如下：
這兩種情況通過(guò)代碼就很直觀的顯示出來(lái)了。
總結(jié)
1熟呛、如果在聲明ArrayList的時(shí)候不設(shè)初始值宽档，那么ArrayList會(huì)默認(rèn)設(shè)置一個(gè)容量為10的數(shù)組，但是ArrayList的大小還是為0的
2庵朝、ArrayList可以看成是一個(gè)動(dòng)態(tài)的數(shù)組吗冤，相比較與數(shù)組來(lái)說(shuō)，ArrayList可以用ensureCapacityInternal方法自動(dòng)擴(kuò)容九府，在向ArrayList添加元素的時(shí)候椎瘟，ArrayList會(huì)先檢測(cè)現(xiàn)在數(shù)組的容量是否足夠，若不夠昔逗，ArrayList會(huì)將數(shù)組的容量擴(kuò)大為原來(lái)的1.5倍降传，如果還不夠篷朵，就用傳進(jìn)來(lái)的參數(shù)作為數(shù)組的容量勾怒。如果我們?cè)谥来鎯?chǔ)元素多少的時(shí)候，盡量給ArrayList設(shè)定一個(gè)初始容量声旺，這樣就可以減少ArrayList的自動(dòng)擴(kuò)容笔链，減少數(shù)組元素的移動(dòng)來(lái)提高程序的性能。
3腮猖、ArrayList在增加或刪除元素的時(shí)候鉴扫，都需要將數(shù)組里面的元素移動(dòng)到另一個(gè)數(shù)組中，這是非常耗時(shí)間的澈缺，所以遇到需要對(duì)元素進(jìn)行頻繁的刪除和添加的集合時(shí)坪创，這時(shí)候選用LinkedList要比ArrayList好很多炕婶，如果遇到在集合中查找元素比較多的操作時(shí)，ArrayList又是一個(gè)不錯(cuò)的選擇莱预，因?yàn)锳rrayList直接可以用下標(biāo)就可以獲取到元素柠掂。
4、在讀ArrayList源碼的時(shí)候要注意ensureCapacityInternal擴(kuò)容方法和System.arraycopy(original, 0, copy, 0,length)方法依沮。
問(wèn)題解析：
來(lái)講一下ArrayList中遇到的一個(gè)問(wèn)題涯贞，就是關(guān)于addAll(int index,Collection<? extends E> e)方法
該方法第一行代碼就是對(duì)index進(jìn)行的判斷
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));
}
可以看到第一個(gè)方法對(duì)于index的判斷，index大于size或者小于0則拋出異常危喉，也就是說(shuō)size>=index>=0
我當(dāng)時(shí)的疑問(wèn)出于size怎么可以等于index,因?yàn)閕ndex是數(shù)組的下標(biāo)宋渔，肯定比個(gè)數(shù)少一，然后在大佬的指點(diǎn)下辜限，發(fā)覺(jué)皇拣，如果我的index==size,那么就是在數(shù)組尾插入集合C，這樣是符合標(biāo)準(zhǔn)的列粪，但是index==size审磁，那么原數(shù)組就不需要移動(dòng)了，如果沒(méi)有加上長(zhǎng)度的判定岂座，那么會(huì)出現(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
