前言
在之前的幾篇文章里面椅挣，我主要都是推薦了一些工具類头岔，為的就是讓大家可以提高開發(fā)效率，但是我們在提高開發(fā)效率鼠证，也應該提高代碼的執(zhí)行效率峡竣，注重代碼的質(zhì)量。如何提高名惩，其中的一個好辦法就是閱讀源碼澎胡，知其然知其所以然。
下面我就以面試問答的形式學習我們的最常用的裝載容器——ArrayList（源碼分析基于JDK8）
問答內(nèi)容
1.
問：ArrayList有用過嗎娩鹉？它是一個什么東西攻谁？可以用來干嘛？
答：有用過弯予，ArrayList就是數(shù)組列表戚宦，主要用來裝載數(shù)據(jù)，當我們裝載的是基本類型的數(shù)據(jù)int,long,boolean,short,byte...的時候我們只能存儲他們對應的包裝類锈嫩，它的主要底層實現(xiàn)是數(shù)組Object[] elementData受楼。與它類似的是LinkedList，和LinkedList相比呼寸，它的查找和訪問元素的速度較快艳汽，但新增，刪除的速度較慢对雪。
示例代碼：
// 創(chuàng)建一個ArrayList河狐，如果沒有指定初始大小，默認容器大小為10
ArrayList<String> arrayList = new ArrayList<String>();
// 往容器里面添加元素
arrayList.add("張三");
arrayList.add("李四");
arrayList.add("王五");
// 獲取index下標為0的元素 張三
String element = arrayList.get(0);
// 刪除index下標為1的元素 李四
String removeElement = arrayList.remove(1);
2.
問：您說它的底層實現(xiàn)是數(shù)組，但是數(shù)組的大小是定長的馋艺，如果我們不斷的往里面添加數(shù)據(jù)的話栅干，不會有問題嗎？
答：ArrayList可以通過構造方法在初始化的時候指定底層數(shù)組的大小捐祠。
- 通過無參構造方法的方式
ArrayList()初始化碱鳞，則賦值底層數(shù)組Object[] elementData為一個默認空數(shù)組Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}所以數(shù)組容量為0，只有真正對數(shù)據(jù)進行添加add時踱蛀，才分配默認DEFAULT_CAPACITY = 10的初始容量窿给。
示例代碼：
// 定義ArrayList默認容量為10
private static final int DEFAULT_CAPACITY = 10;
// 空數(shù)組，當調(diào)用無參構造方法時默認復制這個空數(shù)組
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 真正保存數(shù)據(jù)的底層數(shù)組
transient Object[] elementData;
// ArrayList的實際元素數(shù)量
private int size;
public ArrayList() {
// 無參構造方法默認為空數(shù)組
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
- 通過指定容量初始大小的構造方法方式
ArrayList(int initialCapacity)初始化星岗，則賦值底層數(shù)組Object[] elementData為指定大小的數(shù)組this.elementData = new Object[initialCapacity];
示例代碼：
private static final Object[] EMPTY_ELEMENTDATA = {};
// 通過構造方法出入指定的容量來設置默認底層數(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ù)量已經(jīng)達到底層數(shù)組
Object[] elementData的上限時填大，我們再往ArrayList元素，則會觸發(fā)ArrayList的自動擴容機制俏橘，ArrayList會通過位運算int newCapacity = oldCapacity + (oldCapacity >> 1);以1.5倍的方式初始化一個新的數(shù)組（如初始化數(shù)組大小為10，則擴容后的數(shù)組大小為15）圈浇，然后使用Arrays.copyOf(elementData, newCapacity);方法將原數(shù)據(jù)的數(shù)據(jù)逐一復制到新數(shù)組上面去寥掐，以此達到ArrayList擴容的效果。雖然磷蜀，Arrays.copyOf(elementData, newCapacity);方法最終調(diào)用的是native void arraycopy(Object src, int srcPos, Object dest, int destPos, int length)是一個底層方法召耘，效率還算可以，但如果我們在知道ArrayList想裝多少個元素的情況下褐隆，卻沒有指定容器大小污它，則就會導致ArrayList頻繁觸發(fā)擴容機制，頻繁進行底層數(shù)組之間的數(shù)據(jù)復制庶弃，大大降低使用效率衫贬。
示例代碼：
public boolean add(E e) {
//確保底層數(shù)組容量，如果容量不足歇攻，則擴容
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// 容量不足固惯，則調(diào)用grow方法進行擴容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
/**
* 擴容方法(重點)
*/
private void grow(int minCapacity) {
// 獲得原容量大小
int oldCapacity = elementData.length;
// 新容量為原容量的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 再判斷新容量是否已足夠，如果擴容后仍然不足夠缴守，則復制為最小容量長度
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 判斷是否超過最大長度限制
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 將原數(shù)組的數(shù)據(jù)復制至新數(shù)組葬毫， ArrayList的底層數(shù)組引用指向新數(shù)組
// 如果數(shù)據(jù)量很大，重復擴容屡穗，則會影響效率
elementData = Arrays.copyOf(elementData, newCapacity);
}
- 因此贴捡，在我們使用ArrayList的時候，如果知道最終的存儲容量capacity村砂，則應該在初始化的時候就指定ArrayList的容量
ArrayList(int initialCapacity)烂斋，如果初始化時無法預知裝載容量，但在使用過程中，得知最終容量源祈，我們可以通過調(diào)用ensureCapacity(int minCapacity)方法來指定ArrayList的容量煎源，并且，如果我們在使用途中香缺，如果確定容量大小手销，但是由于之前每次擴容都擴充50%，所以會造成一定的存儲空間浪費图张，我們可以調(diào)用trimToSize()方法將容器最小化到存儲元素容量锋拖，進而消除這些存儲空間浪費。例如：我們當前存儲了11個元素祸轮，我們不會再添加但是當前的ArrayList的大小為15兽埃，有4個存儲空間沒有被使用，則調(diào)用trimToSize()方法后适袜，則會重新創(chuàng)建一個容量為11的數(shù)組Object[] elementData柄错，將原有的11個元素復制至新數(shù)組，達到節(jié)省內(nèi)存空間的效果苦酱。
示例代碼：
/**
* 將底層數(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);
}
}
/**
* 將容器最小化到存儲元素容量
*/
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}
3.
問：那它是怎么樣刪除元素的售貌？您上面說到ArrayList訪問元素速度較快，但是新增和刪除的速度較慢疫萤，為什么呢颂跨？
答：
通過源碼我們可以得知，ArrayList刪除元素時扯饶，先獲取對應的刪除元素恒削，然后把要刪除元素對應索引index后的元素逐一往前移動1位，最后將最后一個存儲元素清空并返回刪除元素尾序，以此達到刪除元素的效果钓丰。
當我們通過下標的方式去訪問元素時，我們假設訪問一個元素所花費的時間為K蹲诀，則通過下標一步到位的方式訪問元素斑粱，時間則為1K，用“大O”表示法表示脯爪，則時間復雜度為O(1)则北。所以ArrayList的訪問數(shù)據(jù)的數(shù)據(jù)是比較快的。
當我們?nèi)ヌ砑釉?code>add(E e)時痕慢，我們是把元素添加至末尾尚揣，不需要移動元素，此時的時間復雜度為O(1)掖举，但我們把元素添加到指定位置快骗，最壞情況下，我們將元素添加至第一個位置
add(int index, E element)，則整個ArrayList的n-1個元素都要往前移動位置方篮，導致底層數(shù)組發(fā)生n-1次復制名秀。通常情況下，我們說的時間復雜度都是按最壞情況度量的藕溅，此時的時間復雜度為O(n)匕得。刪除元素同理，刪除最后一個元素不需要移動元素巾表，時間復雜度為O(1)汁掠，但刪除第一個元素，則需要移動n-1個元素集币，最壞情況下的時間復雜度也是O(n)考阱。所以ArrayList訪問元素速度較快，但是新增和刪除的速度較慢鞠苟。
示例代碼：
/**
* 將元素添加至末尾
*/
public boolean add(E e) {
// 確保底層數(shù)組容量乞榨，如果容量不足，則擴容
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
/**
* 將元素添加至指定下標位置
*/
public void add(int index, E element) {
// 檢查下標是否在合法范圍內(nèi)
rangeCheckForAdd(index);
// 確保底層數(shù)組容量当娱，如果容量不足姜凄，則擴容
ensureCapacityInternal(size + 1); // Increments modCount!!
// 將要添加的元素下標后的元素通過復制的方式逐一往后移動，騰出對應index下標的存儲位置
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
// 將新增元素存儲至指定下標索引index
elementData[index] = element;
// ArrayList的大小 + 1
size++;
}
/**
* 通過下標索引的方式刪除元素
*/
public E remove(int index) {
// 檢查下標是否在合法范圍內(nèi)
rangeCheck(index);
modCount++;
// 直接通過下標去訪問底層數(shù)組的元素
E oldValue = elementData(index);
// 計算數(shù)組需要移動的元素個數(shù)
int numMoved = size - index - 1;
if (numMoved > 0)
// 將要刪除的元素下標后的元素通過復制的方式逐一往前移動
System.arraycopy(elementData, index+1, elementData, index, numMoved);
//將底層數(shù)組長度減1趾访，并清空最后一個存儲元素。
elementData[--size] = null; // clear to let GC do its work
// 返回移除元素
return oldValue;
}
4.
問：ArrayList是線程安全的嗎董虱？
答：ArrayList不是線程安全的扼鞋，如果多個線程同時對同一個ArrayList更改數(shù)據(jù)的話，會導致數(shù)據(jù)不一致或者數(shù)據(jù)污染愤诱。如果出現(xiàn)線程不安全的操作時云头，ArrayList會盡可能的拋出ConcurrentModificationException防止數(shù)據(jù)異常，當我們在對一個ArrayList進行遍歷時淫半，在遍歷期間溃槐，我們是不能對ArrayList進行添加，修改科吭，刪除等更改數(shù)據(jù)的操作的昏滴，否則也會拋出ConcurrentModificationException異常，此為fail-fast（快速失敹匀恕）機制谣殊。從源碼上分析，我們在add,remove,clear等更改ArrayList數(shù)據(jù)時牺弄，都會導致modCount的改變姻几，當expectedModCount != modCount時，則拋出ConcurrentModificationException。如果想要線程安全蛇捌，可以考慮使用Vector抚恒、CopyOnWriteArrayList。
示例代碼：
/**
* AbstractList.Itr 的迭代器實現(xiàn)
*/
private class Itr implements Iterator<E> {
int cursor; // index of next element to return
int lastRet = -1; // index of last element returned; -1 if no such
//期望的modCount
int expectedModCount = modCount;
public boolean hasNext() {
return cursor != size;
}
@SuppressWarnings("unchecked")
public E next() {
checkForComodification();
int i = cursor;
if (i >= size)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i + 1;
return (E) elementData[lastRet = i];
}
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
@Override
@SuppressWarnings("unchecked")
public void forEachRemaining(Consumer<? super E> consumer) {
Objects.requireNonNull(consumer);
final int size = ArrayList.this.size;
int i = cursor;
if (i >= size) {
return;
}
final Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length) {
throw new ConcurrentModificationException();
}
while (i != size && modCount == expectedModCount) {
consumer.accept((E) elementData[i++]);
}
// update once at end of iteration to reduce heap write traffic
cursor = i;
lastRet = i - 1;
checkForComodification();
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
總結
如果在初始化的時候知道ArrayList的初始容量络拌，請一開始就指定容量
ArrayList<String> list = new ArrayList<String>(20);,如果一開始不知道容量俭驮，中途才得知，請調(diào)用list.ensureCapacity(20);來擴充容量盒音，如果數(shù)據(jù)已經(jīng)添加完畢表鳍，但仍需要保存在內(nèi)存中一段時間，請調(diào)用list.trimToSize()將容器最小化到存儲元素容量祥诽，進而消除這些存儲空間浪費譬圣。ArrayList是以1.5倍的容量去擴容的，如初始容量是10雄坪，則容量依次遞增擴充為：15厘熟，22，33维哈，49绳姨。擴容后把原始數(shù)據(jù)從舊數(shù)組復制至新數(shù)組中。
ArrayList訪問元素速度較快阔挠，下標方式訪問元素飘庄，時間復雜度為O(1)，添加與刪除速度較慢购撼，時間復雜度均為O(n)跪削。
ArrayList不是線程安全的，但是在發(fā)生并發(fā)行為時迂求，它會盡可能的拋出
ConcurrentModificationException碾盐，此為fail-fast機制。
