Java集合(一) —— Collection源碼分析
Java集合(二) —— ArrayList源碼分析
Java集合(三) —— LinkedList源碼分析
Java集合(四) —— PriorityQueue源碼分析
Java集合(五) —— HashSet源碼分析
Java集合(六) —— LinkedHashSet源碼分析
Java集合(七) —— TreeSet源碼分析
Java集合(八) —— HashMap源碼分析
Java集合(九) —— LinkedHashMap源碼分析
Java集合(十) —— TreeMap源碼分析
1.ArrayList繼承圖
2.ArrayList的數(shù)據(jù)結(jié)構(gòu)
// 源碼
/**
* The array buffer into which the elements of the ArrayList are stored.
* The capacity of the ArrayList is the length of this array buffer. Any
* empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
* will be expanded to DEFAULT_CAPACITY when the first element is added.
*/
transient Object[] elementData; // non-private to simplify nested class access
可以看到ArrayList的底層是通過數(shù)組實(shí)現(xiàn)的旬渠。
數(shù)組（Array）是一種線性表數(shù)據(jù)結(jié)構(gòu)馏颂，用一組連續(xù)的內(nèi)存空間，來存儲(chǔ)一組具有相同類型的數(shù)據(jù)猛拴。
3.ArrayList性能分析
1.因?yàn)锳rrayList是基于數(shù)組實(shí)現(xiàn)的遇绞，所以可以通過下標(biāo)快速訪問元素(包括get&set)，其時(shí)間復(fù)雜度為O(1)。
2.增加/刪除元素：最理想的狀況是從數(shù)組末尾增加或刪除元素巧号，不需要移動(dòng)數(shù)據(jù)，時(shí)間復(fù)雜度為O(1);最糟糕的狀況是從頭部新增或刪除一個(gè)元素姥闭，導(dǎo)致所有的元素都要移動(dòng)一位丹鸿，時(shí)間復(fù)雜度為O(n)；
3.因?yàn)槊總€(gè)位置插入/刪除元素的概率是一樣的棚品，所以平均時(shí)間復(fù)雜度為（1+2+…n）/n=O(n)
總結(jié)(對比LinkedList)：
- ArrayList具有較好的查詢性能靠欢，而新增/刪除都可能引起大量元素的移動(dòng)，性能較差铜跑，所以ArrayList適用于查詢較多门怪，新增/刪除較少的場景。
- LinkedList(下一章會(huì)介紹)是基于鏈表的锅纺，在查詢(隨機(jī)訪問)時(shí)性能較差掷空，因?yàn)樾枰陔p向鏈表中尋找index的位置再返回，所以LinkedList適用于查詢較少，新增/刪除較多的場景坦弟。
- LinkedList需要額外的內(nèi)存空間保存索引信息护锤。
4.源碼分析
- 成員變量分析
/**
* 默認(rèn)初始容量大小為 10
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* 指定該ArrayList容量為0時(shí)，返回該空數(shù)組酿傍。
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* 當(dāng)調(diào)用無參構(gòu)造方法烙懦，返回的是該數(shù)組。剛創(chuàng)建一個(gè)ArrayList 時(shí)拧粪，其內(nèi)數(shù)據(jù)量為0修陡。
* 它與EMPTY_ELEMENTDATA的區(qū)別就是：該數(shù)組是默認(rèn)返回的，而后者是在用戶指定容量為0時(shí)返回可霎。
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* 存儲(chǔ)集合元素的底層實(shí)現(xiàn)：真正存放元素的數(shù)組魄鸦。
* 被標(biāo)記為transient，在對象被序列化的時(shí)候不會(huì)被序列化癣朗。
*/
transient Object[] elementData;
/**
* 實(shí)際元素?cái)?shù)量
*/
private int size;
- 構(gòu)造函數(shù)分析
/**
* 默認(rèn)將elementData 指向一個(gè)空數(shù)組拾因，即其大小為0，要在第一次添加元素時(shí)容量才擴(kuò)大至10旷余。(可以認(rèn)為是一種懶加載機(jī)制绢记，避免浪費(fèi)內(nèi)存空間)
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/**
* 指定容量的構(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òu)造ArrayList
*/
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;
}
}
3.核心方法分析
- add(E e)
public boolean add(E e) {
// 檢查是否需要擴(kuò)容
ensureCapacityInternal(size + 1); // Increments modCount!!
// 新增元素
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
// 第一次添加元素時(shí)，minCapacity = 1正卧，所以返回默認(rèn)容量DEFAULT_CAPACITY = 10
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
// list被修改次數(shù)
modCount++;
// overflow-conscious code
// minCapacity = 10
if (minCapacity - elementData.length > 0)
// 進(jìn)行擴(kuò)容
grow(minCapacity);
}
/**
* 擴(kuò)容
*/
private void grow(int minCapacity) {
// 當(dāng)前數(shù)組容量
int oldCapacity = elementData.length;
// 擴(kuò)容新容量
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 如果擴(kuò)容后容量仍小于期望的最小容量
if (newCapacity - minCapacity < 0)
// 將期望的最小容量賦值給新容量
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
// 如果擴(kuò)容后的容量大于臨界值蠢熄，則進(jìn)行大容量分配
newCapacity = hugeCapacity(minCapacity);
// 進(jìn)行數(shù)組復(fù)制
elementData = Arrays.copyOf(elementData, newCapacity);
}
關(guān)于擴(kuò)容
int newCapacity = oldCapacity + (oldCapacity >> 1);
首先說明，擴(kuò)容并非網(wǎng)上所說在原來基礎(chǔ)上增加一半炉旷。oldCapacity >> 1是位運(yùn)算签孔，假設(shè)oldCapacity = 10，則newCapacity = 15窘行；下一次擴(kuò)容時(shí)饥追，oldCapacity = 15，newCapacity = 22罐盔。(不懂位運(yùn)算的請自行百度)
- add(int index, E element)
public void add(int index, E element) {
// 數(shù)組越界檢查
rangeCheckForAdd(index);
// 檢查是否需要擴(kuò)容
ensureCapacityInternal(size + 1);
// 拷貝數(shù)組
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
// 指定位置新增元素
elementData[index] = element;
// 數(shù)組大小+1
size++;
}
- remove(int index)
public E remove(int index) {
// 下標(biāo)越界檢查
rangeCheck(index);
// 修改次數(shù)+1
modCount++;
E oldValue = elementData(index);
// 需要移動(dòng)的元素?cái)?shù)量
int numMoved = size - index - 1;
if (numMoved > 0)
// 移動(dòng)元素操作
System.arraycopy(elementData, index+1, elementData, index, numMoved);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
- get(int index)
public E get(int index) {
// 數(shù)組越界檢查
rangeCheck(index);
// fail-fast：快速失敗機(jī)制
checkForComodification();
return ArrayList.this.elementData(offset + index);
}
E elementData(int index) {
return (E) elementData[index];
}
關(guān)于快速失敗機(jī)制
fail-fast 機(jī)制但绕，即快速失敗機(jī)制，是java集合(Collection)中的一種錯(cuò)誤檢測機(jī)制惶看。當(dāng)在迭代集合的過程中該集合在結(jié)構(gòu)上發(fā)生改變的時(shí)候捏顺，就有可能會(huì)發(fā)生fail-fast，即拋出 ConcurrentModificationException異常纬黎。fail-fast機(jī)制并不保證在不同步的修改下一定會(huì)拋出異常草丧，它只是盡最大努力去拋出，所以這種機(jī)制一般僅用于檢測bug莹桅。
- clear()
public void clear() {
modCount++;
// clear to let GC do its work
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
- set(int index, E element)
/**
* 替換指定索引元素
*/
public E set(int index, E element) {
// 數(shù)組越界檢查
rangeCheck(index);
// 記錄舊的元素
E oldValue = elementData(index);
// 替換元素
elementData[index] = element;
return oldValue;
}
