閱讀源碼的主線是：構(gòu)造方法->常用的API（增、刪、改钳枕、查）->ArrayList擴(kuò)容算法。
ArrayList是一個(gè)動(dòng)態(tài)數(shù)組赏壹，其核心數(shù)據(jù)結(jié)構(gòu)就是一個(gè)數(shù)組Object[] elementData,它繼承自AbstractList<E>鱼炒，實(shí)現(xiàn)了List<E>，RandomAccess蝌借，Cloneable昔瞧，java.io.Serializable接口，其中RandomAccess接口代表了它具有隨機(jī)快速訪問的能力菩佑。
因?yàn)?code>ArrayList核心數(shù)據(jù)結(jié)構(gòu)是數(shù)組自晰，所以它是有一定的容量的（數(shù)組的length）這就涉及到一個(gè)問題，當(dāng)集合中的元素超過這個(gè)容量的時(shí)候稍坯，ArrayList便會(huì)進(jìn)行擴(kuò)容操作（關(guān)于擴(kuò)容操作酬荞，后面會(huì)介紹到，這里先給一個(gè)大致的認(rèn)知）瞧哟。擴(kuò)容操作是ArrayList的一個(gè)性能消耗比較大的地方混巧，所以如果我們可以提前預(yù)知到數(shù)據(jù)的大小，此時(shí)我們應(yīng)該通過帶有指定集合大小參數(shù)的構(gòu)造方法來創(chuàng)建ArrayList勤揩，而不是無腦使用無參構(gòu)造牲剃，指定集合大小可以減少擴(kuò)容次數(shù)，提高效率雄可。
1、ArrayList構(gòu)造方法
//數(shù)組默認(rèn)容量為10
private static final int DEFAULT_CAPACITY = 10;
//空數(shù)組
private static final Object[] EMPTY_ELEMENTDATA = {};
//真正用來儲(chǔ)存元素的數(shù)組
transient Object[] elementData;
//集合大小
private int size;
//無參構(gòu)造缠犀，也是我們平時(shí)無腦使用的構(gòu)造方法
public ArrayList() {
super();
//無參構(gòu)造方法將空數(shù)組賦值給了elementData
this.elementData = EMPTY_ELEMENTDATA;
}
//帶初始容量大小的構(gòu)造方法
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0)
//初始容量小于0直接拋出異常
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
//初始容量大于等于0時(shí)数苫，直接創(chuàng)建一個(gè)容量大小為 initialCapacity 的數(shù)組
this.elementData = new Object[initialCapacity];
}
//利用其他集合類來創(chuàng)建一個(gè) ArrayList集合
public ArrayList(Collection<? extends E> c) {
//這屆利用 Collection.toArray()方法得到一個(gè)數(shù)組，并且把它賦值給 elementData
elementData = c.toArray();
//集合元素?cái)?shù)量
size = elementData.length;
// c.toArray might (incorrectly) not return Object[] (see 6260652)
//這里 c.toArray 返回的可能不是 Object[]辨液，之所以會(huì)有這個(gè)問題是因?yàn)槔^承的原因：
//父類實(shí)例的具體類型虐急，實(shí)際上取決于在 new 的時(shí)候，我們使用的子類類型滔迈。
//具體的分析見：http://www.itread01.com/articles/1478295315.html
if (elementData.getClass() != Object[].class)
//如果 c.toArray 返回的不是 Object[] 時(shí)止吁，利用 Arrays.copyOf() 方法被辑，將 c 中元素復(fù)制到 elementData中。
elementData = Arrays.copyOf(elementData, size, Object[].class);
}
至此敬惦，構(gòu)造函數(shù)就走完了盼理，此時(shí)會(huì)構(gòu)建出數(shù)組 elementData。注意：若使用前面兩個(gè)構(gòu)造函數(shù)俄删，此時(shí) size還是0宏怔，也就是ArryList中還沒有元素；若使用第三種構(gòu)造函數(shù)畴椰，此時(shí) ArryList 已經(jīng)有了元素了臊诊，size 不為0。
2斜脂、增
2.1 add(E element) 方法
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;//在數(shù)組末尾追加一個(gè)元素抓艳，并修改 size 的值
return true;
}
//注意到ensureCapacityInternal()方法，每次 add 之前都會(huì)調(diào)用改方法
private void ensureCapacityInternal(int minCapacity) {
//如果時(shí)調(diào)用的第一個(gè)構(gòu)造方法初始化的 ArrayList帚戳，則取 10 和
//minCapacity中的最大值作為 minCapacity玷或，當(dāng)且僅當(dāng)無參構(gòu)
//造函數(shù)第一次調(diào)用 add 才會(huì)進(jìn)入這個(gè) if 語句
if (elementData == EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;//如果需要擴(kuò)容，會(huì)修改 modCount 的值
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
//這個(gè)方法真正的去擴(kuò)容
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
//創(chuàng)建一個(gè) newCapacity 變量销斟，它的大小等于原有大小加上原有大小的一半
int newCapacity = oldCapacity + (oldCapacity >> 1);
//如果 newCapacity 比我們期望擴(kuò)容的值還小庐椒，那么就將我們期望擴(kuò)容的值賦給 newCapacity
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:
//這里利用 Arrays.copyOf() 對(duì) elementData數(shù)組進(jìn)行擴(kuò)容
elementData = Arrays.copyOf(elementData, newCapacity);
}
延伸：阿里巴巴Java開發(fā)手冊(cè)中第一章第五小節(jié)第九條建議建議我們：9. 【推薦】集合初始化時(shí)， 指定集合初始值大小蚂踊。它這樣建議的依據(jù)是什么呢约谈？假設(shè)我們需要一個(gè)容量為50的ArrayList，調(diào)用它的無參構(gòu)造：
- 當(dāng)?shù)谝淮握{(diào)用
add方法時(shí)犁钟，需要進(jìn)行一次擴(kuò)容棱诱，此時(shí)elementData數(shù)組容量為10； - 當(dāng)元素?cái)?shù)量小于等于10時(shí)都不會(huì)在擴(kuò)容涝动；
- 當(dāng)元素?cái)?shù)量大于10時(shí)迈勋，進(jìn)行第二次擴(kuò)容1.5倍，此時(shí)
elementData數(shù)組容量為15（10+5）醋粟； - 當(dāng)元素?cái)?shù)量大于15時(shí)靡菇，進(jìn)行第三次擴(kuò)容1.5倍，此時(shí)
elementData數(shù)組容量為22（15+7）米愿； - 當(dāng)元素?cái)?shù)量大于22時(shí)厦凤，進(jìn)行第四次擴(kuò)容1.5倍，此時(shí)
elementData數(shù)組容量為33（22+11）育苟； - 當(dāng)元素?cái)?shù)量大于33時(shí)较鼓，進(jìn)行第五次擴(kuò)容1.5倍，此時(shí)
elementData數(shù)組容量為49（33+16）； - 當(dāng)元素?cái)?shù)量大于49時(shí)博烂，進(jìn)行第六次擴(kuò)容1.5倍香椎，此時(shí)
elementData數(shù)組容量為73（49 + 24）；
也就是說我們需要一個(gè)容量為50 的ArrayList禽篱，最后卻得到了一個(gè)容量為73 的ArrayList畜伐，這不僅浪費(fèi)了空間，同時(shí)由grow()方法我們得知谆级，每次都會(huì)進(jìn)行數(shù)組copy烤礁，這是極其消耗性能的。這也驗(yàn)證了我們文章開頭提出的觀點(diǎn)肥照，假如我們可以提前預(yù)知元素的數(shù)量的時(shí)候脚仔，建議集合初始化的時(shí)候就指定其大小，以減少多次擴(kuò)容帶來的效率問題舆绎。
2.2 add(int index,E element)方法
public void add(int index, E element) {
//這里可能會(huì)存在一些疑問鲤脏，ArrayList進(jìn)行第一次擴(kuò)容之后，內(nèi)部 elementData
//數(shù)組的長(zhǎng)度為10吕朵，此時(shí)假設(shè)只有一個(gè)元素（0號(hào)位置）猎醇，即 size = 1,
//調(diào)用add(int index, E element)，我們往2號(hào)位置插入一個(gè)元素
//（index = 2努溃，size = 1）硫嘶，按理說數(shù)組的長(zhǎng)度時(shí)足夠的，但是在ArrayList
//卻會(huì)拋出數(shù)組越界問題,這樣的做法是為了保證ArrayList數(shù)據(jù)內(nèi)存地址的連續(xù)性梧税。
//同時(shí)也是為了避免后面取數(shù)據(jù)的時(shí)候出現(xiàn)數(shù)組越界問題沦疾，假如這里沒有做邊界檢查，
//2號(hào)位置我們插入一個(gè)元素第队，即elementData[2]有數(shù)據(jù)哮塞，我們使用 list 去獲取
//數(shù)據(jù)時(shí)，應(yīng)該是list.get(1)發(fā)現(xiàn)并沒有這個(gè)元素凳谦。
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
//進(jìn)入擴(kuò)容算法
ensureCapacityInternal(size + 1); // Increments modCount!!
//將index開始的數(shù)據(jù)忆畅，向后移動(dòng)一位
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;//將element元素插入index位置
size++;
}
2.3 addAll(Collection<? extends E> c)方法
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
//確定是否需要擴(kuò)容
ensureCapacityInternal(size + numNew); // Increments modCount
//在這個(gè)list的末尾追加一個(gè)集合
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}
2.4 addAll(int index,Collection<? extends E> c)方法
public boolean addAll(int index, Collection<? extends E> c) {
//判斷是否越界
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
//這里不需要判斷c.toArray()類型是否為Object[].class 類型 ，
//后面 System.arraycopy()方法會(huì)將az中元素全部copy到elementData數(shù)組中尸执，
//保證了類型一致問題
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
int numMoved = size - index;
// 0<= index < size時(shí)走這個(gè) if 分支
if (numMoved > 0)
//將elementData數(shù)組中從index開始的（size-index）個(gè)元素
//向右移動(dòng)（index+numNew）位家凯。
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
//如果走了上一個(gè)if分支，就是填充上一個(gè)操作之后空出來的位置如失，
//否則绊诲，即index=size,就在末尾追加a數(shù)組
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}
3、刪
3.1 remove(int index)方法
public E remove(int index) {
//首先進(jìn)行邊界檢查
rangeCheck(index);
//修改modCount岖常，因?yàn)榻Y(jié)構(gòu)發(fā)生了變化
modCount++;
//需要?jiǎng)h除的元素
E oldValue = elementData(index);
//需要向左移動(dòng)的元素的個(gè)數(shù)
int numMoved = size - index - 1;
//除了刪除最后一個(gè)元素均會(huì)走這個(gè)分支
if (numMoved > 0)
//將elementData數(shù)組中numMoved個(gè)元素分別向左移動(dòng)一位
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
//將數(shù)組末尾置空，不再強(qiáng)引用葫督，可以被GC回收
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
3.2 remove(Object o)方法
//刪除該元素在書中中第一次出現(xiàn)的位置上的元素竭鞍。
public boolean remove(Object o) {
if (o == null) {
//刪除值為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;
}
//該方法不進(jìn)行邊界檢查了板惑，因?yàn)檫@里的index一定是0<=index<size的
private void fastRemove(int index) {
//修改modCount，因?yàn)榻Y(jié)構(gòu)已經(jīng)發(fā)生了變化
modCount++;
int numMoved = size - index - 1;
if (numMoved > 0)
//和remove(int index)方法原理一樣了
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
}
3.3 removeAll(Collection<?> c)
//批量刪除
public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, false);
}
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;
}
關(guān)于批量刪除分析詳見我的另外一篇文章偎快，這里就不再詳細(xì)介紹了冯乘。
4、改
4.1 set(int index,E element)方法
//修改操作不會(huì)修改modCount的值晒夹，即不會(huì)修改結(jié)構(gòu)裆馒，相對(duì)增刪來說時(shí)高效操作。
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
5丐怯、查
5.1 get(int index) 方法
//查操作不會(huì)修改modCount的值喷好，沒有結(jié)構(gòu)的變化，相對(duì)增刪來說時(shí)高效操作
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
6读跷、小結(jié)
1梗搅、通過源碼分析我們知道增刪改查四個(gè)操作中，如果增導(dǎo)致了擴(kuò)容一定會(huì)修改modCount的值效览，而刪除一定會(huì)修改modCount的值无切。改、查操作一定不會(huì)修改modCount的值丐枉。
2哆键、擴(kuò)容操作會(huì)導(dǎo)致數(shù)組的復(fù)制，刪除操作除了刪除最后一個(gè)元素均會(huì)導(dǎo)致數(shù)組復(fù)制瘦锹，因此籍嘹，相對(duì)來說增刪操作時(shí)比較消耗性能的，而改查操作時(shí)相對(duì)高效的操作沼本。如果需要頻繁增刪元素噩峦，那么就不是很推薦使用ArrayList這種數(shù)據(jù)結(jié)構(gòu)了。
3抽兆、經(jīng)過源碼分析也驗(yàn)證了阿里巴巴Java開發(fā)手冊(cè)中中提出的集合初始化時(shí)识补， 指定集合初始值大小建議的合理性。
以上是我閱讀源碼的一些思考和心得辫红，如有寫的不正確的地方凭涂，還請(qǐng)大神指出，以免誤人子弟贴妻。
