- ArrayList的成員變量分析。
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; //空構(gòu)造器時(shí)，默認(rèn)為容量為0的空數(shù)組
transient Object[] elementData;//集合實(shí)際 存放數(shù)據(jù)的數(shù)組，不需要序列化，故用transient來修飾
private int size;// list實(shí)際大小
private static final int DEFAULT_CAPACITY = 10;// 默認(rèn)list容量
protected transient int modCount = 0;// 這個(gè)在迭代遍歷并發(fā)刪除的的時(shí)候就可以顯露問題
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
- ArrayList的常見創(chuàng)建方式。
2.1 空構(gòu)造函數(shù)
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;// 空構(gòu)造器時(shí)，默認(rèn)為容量為0的空數(shù)組
}
2.2 初始化集合大小的構(gòu)造函數(shù)（如果已知集合需要容納元素大小，建議此方法創(chuàng)建）
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);
}
}
3 集合操作：增加元素
3.1 添加元素（依次在數(shù)組最后一個(gè)元素添加）
public boolean add(E e) {
// 第一步：確認(rèn)list是否已滿，如果未滿，直接添加，如果已滿則看是否需要擴(kuò)容
ensureCapacityInternal(size + 1);
// 第二步：添加元素
elementData[size++] = e;// 添加元素
return true;
}
我們知道集合優(yōu)于數(shù)組的其中一個(gè)原因就是數(shù)組在聲明的時(shí)候大小就確定了，不可變。而集合在添加元素可以自動(dòng)擴(kuò)容的。那么究竟集合是如何實(shí)現(xiàn)自動(dòng)擴(kuò)容的呢？
第一步：先來確定一下當(dāng)前集合容量是否滿足添加一個(gè)元素需求。
/**
* 開始擴(kuò)容，擴(kuò)容的時(shí)候就需要考慮到什么時(shí)候開始擴(kuò)容，擴(kuò)容多大比較合適。實(shí)際上問題歸根于解決擴(kuò)容多大的問題。
*
* @param minCapacity
*/
public void ensureCapacityInternal(int minCapacity) {
// 解決第一個(gè)問題：什么時(shí)候需要擴(kuò)容?
if (elementData == EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
第二步：什么時(shí)候需要擴(kuò)容？
/**
* 開始擴(kuò)容
*
* @param minCapacity
*/
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
if (minCapacity > elementData.length) {
// 如果擴(kuò)容大于新建數(shù)組的長度（數(shù)組的長度，非集合中元素的大?。?，這個(gè)時(shí)候需要擴(kuò)容。
grow(minCapacity);
}
}
第三步：如何擴(kuò)容？
/**
* 實(shí)際擴(kuò)容操作
*
* @param minCapacity
*/
private void grow(int minCapacity) {
int oldCapacity = elementData.length; // 原來數(shù)組長度
int newCapacity = oldCapacity + (oldCapacity >> 1);// 擴(kuò)容新數(shù)組大小，為什么選擇擴(kuò)容原來的1.5倍？難道是這是為了節(jié)省空間最佳方案。
if (newCapacity - minCapacity < 0) {
newCapacity = minCapacity; // 從這里可以看出來，實(shí)際擴(kuò)容大小，有可能不止1.5倍大小。
}
if (newCapacity - MAX_ARRAY_SIZE > 0) {
// 如果MAX_ARRAY_SIZE大小都不能滿足擴(kuò)容之后的新容量大小，則需要進(jìn)一步擴(kuò)容
newCapacity = hugeCapacity(minCapacity);
}
elementData = Arrays.copyOf(elementData, newCapacity);// 最后一步最重要的是，把原來數(shù)組復(fù)制到擴(kuò)容之后的數(shù)組中。這里需要使用到j(luò)dk本地庫，
// 不可避免需要IO操作，如果頻繁的擴(kuò)容，會(huì)影響ArrayList的性能，因此如果我們知道list大小，可以直接構(gòu)造出指定容量的數(shù)組
}
/**
* 當(dāng)擴(kuò)容MAX_ARRAY_SIZE都不能滿足新的容量時(shí)
*
* @param minCapacity
* @return
*/
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // 溢出
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE
: MAX_ARRAY_SIZE;// 從這里可以看出list能夠存儲(chǔ)的最大容量是整型范圍內(nèi)的最大容量。
}
3.1 指定位置添加元素
@Override
public void add(int index, E element) {
//第一步：查看index是否越界
rangeAddCheck(index);
//第二步：擴(kuò)容
ensureCapacityInternal(size + 1);
//第三步：移動(dòng)index位置（包含index）之后的元素，本質(zhì)是將index往index+1的元素開始往后移動(dòng)，然后將新值賦予到index位置處。
System.arraycopy(elementData, index, elementData, index+1, size-index);
//第四步：添加index新值
elementData[index] = element;
size ++;
}
總結(jié)一下添加的思路：檢查ArrayList是否有足夠的容量來存儲(chǔ)待添加元素，如果容量不夠需要擴(kuò)容操作。然后創(chuàng)建一個(gè)擴(kuò)容之后新容量的數(shù)組，并將原來數(shù)組復(fù)制到新數(shù)組中，原來數(shù)組引用指向新的數(shù)組。
3.2 刪除指定位置元素
@Override
public E remove(int index) {
rangeCheck(index);
modCount ++;
int movedNum = size - index -1;//需要移動(dòng)多少個(gè)元素
E oldValue = elementData(index);
if (movedNum > 0) {
System.arraycopy(elementData, index+1, elementData, index, movedNum);//從index+1開始復(fù)制elementData，然后放入elementData的index位置，總共復(fù)制movedNum個(gè)元素
}
elementData[size--] = null;//把最后一個(gè)元素置空，便于垃圾回收
return oldValue;
}
主要思路就是，將index之后的位置統(tǒng)一向前移動(dòng)一位，并將數(shù)組最后一個(gè)元素置null,以便于垃圾回收器回收。
3.3 修改指定位置元素
@Override
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;//返回的是原來index位置上的值
}
3.4 獲取元素
@Override
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
@SuppressWarnings("unchecked")
E elementData(int index) {
return (E) elementData[index];
}
/**
* 檢查是否越界
*/
private void rangeCheck(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("越界啦！");
}
}
private void rangeAddCheck(int index){
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("越界啦！");
}
}
3.5 查找元素
@Override
public int indexOf(Object o) {
//由于ArrayList可以放置null元素，因此在查找的時(shí)候需要分情況討論
if (o == null) {
for (int i = 0; i < size; i++) {
if (elementData[i]==null) {
return i;
}
}
} else {
for (int i = 0; i < size; i++) {
if (o.equals(elementData[i])) {//這里使用的object的equals()方法，如果又必須要需重寫
return i;
}
}
}
return -1;
}
@Override
public int lastIndexOf(Object o) {
// ArrayList允許null，因此通過循環(huán)遍歷查找元素時(shí)，需要分為null，非null值,主要區(qū)別就是根據(jù)相等判斷方法不一致。
//如何才能這個(gè)元素最后出現(xiàn)的位置呢？那么我們遍歷該數(shù)組的時(shí)候，需要從后面往前面遍歷，這樣第一次遇見的這個(gè)元素位置就是該元素最后出現(xiàn)的位置
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;
}
其實(shí)，分析到這里我們就可以看出ArrayList的特點(diǎn)了：
- 自動(dòng)擴(kuò)容機(jī)制保證操作ArrayList時(shí)容量大小可變。
- 可通過數(shù)組下標(biāo)訪問元素，查詢快，增刪操作慢，涉及擴(kuò)容，數(shù)組復(fù)制等操作。
- 線程不安全，效率高。
-
元素有序，且可為null。
圖片.png
