ArrayList 繼承結(jié)構(gòu)
ArrayLisy.png
ArrayList的本質(zhì)是一個(gè)數(shù)組
這是ArrayList的屬性减俏，包括默認(rèn)長度幼苛，空數(shù)組倔喂，elementData（存儲(chǔ)數(shù)據(jù)的數(shù)組）和size（集合中元素個(gè)數(shù)）
private static final int DEFAULT_CAPACITY = 10;
/**
* Shared empty array instance used for empty instances.
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* Shared empty array instance used for default sized empty instances. We
* distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
* first element is added.
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* 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
/**
* The size of the ArrayList (the number of elements it contains).
*
* @serial
*/
private int size;
ArrayList的構(gòu)造函數(shù)
- 無參夠著函數(shù)雏蛮，就是初始化為一個(gè)默認(rèn)空數(shù)組恢氯，不分配內(nèi)存空間带斑，實(shí)現(xiàn)懶加載，需要的時(shí)候再分配內(nèi)存
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
- 有參構(gòu)造函數(shù)勋拟，出入初始化大小勋磕，檢查初始參數(shù)
- 大于0：分配對(duì)應(yīng)內(nèi)存空間
- 等于0：賦值給默認(rèn)空數(shù)組
- 小于0： 拋出初始化參數(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);
}
}
重要方法分析：add(E e) , get(int index), set(int index , T data), remove(int index)
- add(E e): 添加一個(gè)數(shù)據(jù)
ensureCapacityInternal(size + 1): 確認(rèn)容量
minCapacity -> size+1
calculateCapacity(elementData, minCapacity)：計(jì)算容量，如果插入后size大于當(dāng)前數(shù)組的容量則擴(kuò)容敢靡，如果size小于挂滓，直接返回，執(zhí)行賦值操作啸胧，同時(shí)size+1
grow(minCapacity)： 擴(kuò)容方法
private void grow(int minCapacity) {
// 獲取原來數(shù)組的容量
int oldCapacity = elementData.length;
// 擴(kuò)容1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 主要用于第一次插入時(shí)擴(kuò)容赶站，默認(rèn)為10，所以第一次不是擴(kuò)1.5倍纺念，而是創(chuàng)建長度為10的數(shù)組
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 判斷數(shù)組長度是否超過最大值
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
// 將老數(shù)據(jù)拷貝到一個(gè)新數(shù)組
elementData = Arrays.copyOf(elementData, newCapacity);
}
- get(int index)
public E get(int index) {
// 數(shù)組下標(biāo)越界檢查
rangeCheck(index);
return elementData(index);
}
- set(int index, T data)
public E set(int index, E element) {
// 數(shù)組下標(biāo)越界檢查
rangeCheck(index);
E oldValue = elementData(index);
// 賦值
elementData[index] = element;
// 返回舊值
return oldValue;
}
- remove(int index)
public E remove(int index) {
// 數(shù)組下標(biāo)越界檢查
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
// 計(jì)算需要移動(dòng)的數(shù)量贝椿，如果是最末尾賊不要移動(dòng)
int numMoved = size - index - 1;
// 如果在非末尾
if (numMoved > 0)
// 將當(dāng)前索引所在的后面的所有值，向前移動(dòng)一位（拷貝index+1到最后的所有數(shù)據(jù)到index開始的位置）
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
// 將最后一位設(shè)置為空陷谱，同時(shí)size-1
elementData[--size] = null; // clear to let GC do its work
// 返回舊值
return oldValue;
}
源碼中modCount++的作用
用于在多線程環(huán)境下烙博，保證數(shù)據(jù)安全的FailFast機(jī)制。主要是在集合迭代過程中，防止集合變化導(dǎo)致錯(cuò)誤渣窜。原理是集合開始迭代是會(huì)把modCount賦值給迭代器一個(gè)屬性铺根，迭代過程中不斷檢查值當(dāng)前modCount與原始值是否相等，不等則拋出ConcurrentModificationException異常
總結(jié)
- ArrayList的實(shí)現(xiàn)是數(shù)組乔宿，底層結(jié)構(gòu)是連續(xù)內(nèi)存空間的線性表夷都，在隨機(jī)讀寫上性能好，通過計(jì)算獲取下標(biāo)位置
- 在隨機(jī)插入和刪除時(shí)予颤， 需要移動(dòng)插入位置后面的所有元素囤官，性能較差
- 在插入時(shí)可能需要?jiǎng)討B(tài)擴(kuò)容，第一次擴(kuò)容到10蛤虐，后面每次擴(kuò)容1.5倍
