上一篇中的提到集合具體實(shí)現(xiàn)類在后續(xù)章節(jié)中逐一分析亏吝，本篇來(lái)分析項(xiàng)目中經(jīng)常用到的數(shù)組列表（ArrayList）
1 數(shù)組列表類關(guān)系
數(shù)組列表UML.png
ArrayList主要實(shí)現(xiàn)了List熊响、RandomAccess秒梅、Cloneable刀森、Serializable接口撮奏，繼承了AbstractList抽象類杠览。
List接口定義了數(shù)組列表必須實(shí)現(xiàn)的方法
AbstractList實(shí)現(xiàn)了List中的通用的方法弯菊；
RandomAccess接口上一篇提到過(guò)，是為了監(jiān)測(cè)列表查詢效率踱阿，做個(gè)標(biāo)記管钳；
Cloneable接口可以實(shí)現(xiàn)對(duì)象的克露趾贰；
Serializable接口標(biāo)識(shí)序列號(hào)蹋嵌；
2 數(shù)組列表（ArrayList）源碼分析
2.1 屬性字段和構(gòu)造函數(shù)
/**
* Integer.MAX_VALUE是int整形的最大取值2的31次方-1育瓜，這個(gè)常量用來(lái)控制集合的最大容量
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
/**
* 存放ArrayList對(duì)象的數(shù)組
*/
private transient Object[] elementData;
/**
* 數(shù)組列表大小
*/
private int size;
/**
* 根據(jù)傳入的數(shù)字初始化elementData 數(shù)組
*/
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
}
/**
* 默認(rèn)elementData 的大小為10
*/
public ArrayList() {
this(10);
}
/**
* 根據(jù)傳入的集合構(gòu)造數(shù)組列表
*/
public ArrayList(Collection<? extends E> c) {
//將傳入的集合轉(zhuǎn)換為數(shù)組，賦值給elementData
elementData = c.toArray();
size = elementData.length;
// 如果elementData 的元素類型不是Object栽烂，通過(guò)Arrays.copyOf轉(zhuǎn)換為Object
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
}
2.2 添加元素
覆蓋了AbstractList中的add（）方法躏仇，這里有個(gè)問(wèn)題，當(dāng)超出列表的長(zhǎng)度時(shí)腺办，如何自動(dòng)增加列表長(zhǎng)度焰手，添加元素，詳細(xì)看下面你的源碼分析：
/**
* 添加元素到列表
*/
public boolean add(E e) {
//確認(rèn)列表容量方法
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
/**
* 當(dāng)添加元素超過(guò)容器的容量時(shí)怀喉，自動(dòng)擴(kuò)增容器容量
*/
private void ensureCapacityInternal(int minCapacity) {
modCount++;
// 注意這里實(shí)現(xiàn)了自動(dòng)擴(kuò)增容器容量
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
/**
* 自動(dòng)擴(kuò)增容器容量方法
*/
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
/**
* 假設(shè)以空參數(shù)方法構(gòu)造列表书妻，則容器默認(rèn)大小是10，當(dāng)往列表中加載第11個(gè)元
* 素時(shí)躬拢，也就是說(shuō)oldCapacity =11躲履，11的二進(jìn)制單位右移1位，是0000 0101聊闯，
* 十進(jìn)制是5工猜，即newCapacity =15，這里把容器的長(zhǎng)度擴(kuò)增了5位.
*/
int newCapacity = oldCapacity + (oldCapacity >> 1);
//如果newCapacity <minCapacity菱蔬，newCapacity 取最小值minCapacity
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//如果newCapacity >MAX_ARRAY_SIZE 篷帅，newCapacity 取最大值
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
//調(diào)整elementData 的大小為新的容量
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
//Integer.MAX_VALUE是int整形的最大取值2的31次方-1
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
/**
* 添加元素的集合指定位置
*/
public void add(int index, E element) {
//檢查索引位置是否超出列表邊界
rangeCheckForAdd(index);
//確定是否要擴(kuò)增
ensureCapacityInternal(size + 1); // Increments modCount!!
//將elementData數(shù)組中index的位置空留出來(lái)
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
//將新插入的element賦給elementData數(shù)組index位置的值
elementData[index] = element;
size++;
}
/**
* 檢查索引位置是否超出列表邊界
*/
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
/**
* 添加集合到列表
*/
public boolean addAll(Collection<? extends E> c) {
//轉(zhuǎn)換引入的集合(c)為數(shù)組
Object[] a = c.toArray();
//獲取引入集合的數(shù)組大小
int numNew = a.length;
//確定是否要擴(kuò)增
ensureCapacityInternal(size + numNew); // Increments modCount
//拷貝引入的數(shù)組到elementData的尾部
System.arraycopy(a, 0, elementData, size, numNew);
//是列表的長(zhǎng)度增加為size+numNew
size += numNew;
//引入的集合(c)大小不為空，則返回true
return numNew != 0;
}
/**
* 添加集合到列表指定位置
*/
public boolean addAll(int index, Collection<? extends E> c) {
//同上
rangeCheckForAdd(index);
Object[] a = c.toArray();
int numNew = a.length;
//根據(jù)傳入的集合拴泌，確定是否需要擴(kuò)增容量
ensureCapacityInternal(size + numNew); // Increments modCount
int numMoved = size - index;
if (numMoved > 0)
//先將elementData數(shù)組中index到index + numNew 值后移魏身，為引入c集合空出位置
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
//將c集合中元素復(fù)制到elementData數(shù)組中index到index + numNew的位置
System.arraycopy(a, 0, elementData, index, numNew);
//同上
size += numNew;
return numNew != 0;
}
2.3 移除元素
下面分析如何動(dòng)態(tài)的移除數(shù)列表中的元素
/**
* 根據(jù)指定的索引移除元素
*/
public E remove(int index) {
rangeCheck(index);
//注意modCount繼承自AbstractList抽象類，是一個(gè)不包括在序列化中的值
modCount++;
// 訪問(wèn)elementData[index]值
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
//將elementData數(shù)組的元素從index+1位置后移到index
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
//將elementData數(shù)組最后一個(gè)位置元素設(shè)置為null
elementData[--size] = null; // Let gc do its work
//返回被移除的元素
return oldValue;
}
/**
* 判斷移除元素的位置是否超出邊界
*/
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
// 返回elementData[index]值
@SuppressWarnings("unchecked")
E elementData(int index) {
return (E) elementData[index];
/**
* 根據(jù)傳入的對(duì)象蚪腐，去列表中循環(huán)查詢箭昵，如果存在相同對(duì)象，調(diào)用fastRemove方法移除
*/
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;
}
/*
* 根據(jù)位置index移除元素削茁，和remove(int index) 方法的區(qū)別宙枷，是不用返回移除元素值
*/
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; // Let gc do its work
}
2.3 訪問(wèn)元素
/**
* 隨機(jī)訪問(wèn)數(shù)組列表中的元素
*/
public E get(int index) {
//判斷index是否超出數(shù)組列表訪問(wèn)
rangeCheck(index);
//放回elementData[index]值，這里可以說(shuō)明茧跋，ArrayList隨機(jī)訪問(wèn)的效率高
return elementData(index);
}
2.4其他方法
2.4.1 包含運(yùn)算
/**
* 暴露給外部的集合包含運(yùn)算方法
*/
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
/**
*實(shí)現(xiàn)集合包含運(yùn)算
*/
public int indexOf(Object o) {
if (o == null) {
//如果o是null慰丛，循環(huán)elementData，查找是否有null值
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
//如果o不是是null瘾杭，循環(huán)elementData诅病，查找是否有相等的值，
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
//有相等的值返回索引i，否則返回-1贤笆；
return -1;
}
/**
* 顧名思義和上面的相反蝇棉，反向查詢是否相等的值
*/
public int lastIndexOf(Object o) {
if (o == null) {
for (int i = size-1; i >= 0; i--)
if (elementData[i]==null)
return i;
} else {
for (int i = size-1; i >= 0; i--)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
2.4.2 求交運(yùn)算
/**
* 暴露給外部的集合求交集方法
*/
public boolean retainAll(Collection<?> c) {
return batchRemove(c, true);
}
//實(shí)現(xiàn)交集運(yùn)算，
private boolean batchRemove(Collection<?> c, boolean complement) {
//將elementData數(shù)組轉(zhuǎn)換為常量數(shù)組
final Object[] elementData = this.elementData;
int r = 0, w = 0;
boolean modified = false;
try {
for (; r < size; r++)
//循環(huán)訪問(wèn)列表芥永，調(diào)用contains方法篡殷，判斷引入的集合是否包含列表中的元素，如果有賦值給新的常量數(shù)組
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) {
for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size - w;
size = w;
modified = true;
}
}
return modified;
}
參考文章
1 《Java核心技術(shù)（卷一第9版）》
2 http://blog.csdn.net/jzhf2012/article/details/8540410
