基于jdk1.8源碼
UML類關(guān)系圖
? 我們先來看一下ArrayList的類關(guān)系圖诫咱。
ArrayList.png
? 從圖中可以看出件已，ArrayList繼承了AbstractList抽象類恋博，實現(xiàn)了4個接口雹仿。
1.實現(xiàn)了List接口：
2.實現(xiàn)了RandomAccess接口：
3.實現(xiàn)了Cloneable接口：
4.實現(xiàn)了Serializable接口：
構(gòu)造函數(shù)
<u>ArrayList的構(gòu)造方法就做一件事情重付，就是初始化一下儲存數(shù)據(jù)的容器勺像，其實本質(zhì)上就是一個數(shù)組障贸，在其中就叫elementData。</u>
1.ArrayList()
構(gòu)造一個初始容量為 10 的空列表吟宦。如果我們創(chuàng)建ArrayList對象的時候不傳入?yún)?shù)篮洁，則使用此無參構(gòu)造方法創(chuàng)建ArrayList對象。
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
初始化一個空的list殃姓，在add第一個元素的時候袁波，設(shè)置初始容量為10
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
//data一開始是空，則返回10的初始容量
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
2.ArrayLIst(int)
構(gòu)造一個指定容量為capacity的空ArrayList蜗侈。這是一個帶初始容量大小的有參構(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);
}
}
- 初始容量大于0,實例化數(shù)組，將自定義的容量大小當(dāng)成初始化elementData的大小
- 初始容量等于0踏幻，將空數(shù)組賦給elementData
- 初始容量小于0枷颊，拋異常
3.ArrayList(Collection<? extends E>)
構(gòu)造一個包含指定 collection 的元素的列表，這些元素是按照該 collection 的迭代器返回它們的順序排列的。第二個有參構(gòu)造方法構(gòu)造時賦的值是它的父類Collection對象夭苗。
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)
//每個集合的toarray()的實現(xiàn)方法不一樣信卡，所以需要判斷一下，如果不是Object[].class類型题造，那么就需要使用ArrayList中的方法去改造一下傍菇。
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
- 將集合對象轉(zhuǎn)成數(shù)據(jù)，地址賦值給elementData
- 如果數(shù)組的實際大小等于0（c中沒有元素）界赔，將空數(shù)組EMPTY_ELEMENTDATA賦值給elementData
- 如果size的值大于0桥嗤，則執(zhí)行Arrays.copy方法，把collection對象的內(nèi)容（可以理解為深拷貝）copy到elementData中()
重要方法
1.get方法
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
@SuppressWarnings("unchecked")
E elementData(int index) {
return (E) elementData[index];
}
可以看到由于Arraylist底層就是個obj的數(shù)組仔蝌，所以獲取元素是比較簡單的。直接先對index進(jìn)行范圍判斷荒吏，然后返回數(shù)組下標(biāo)對應(yīng)的值敛惊。
2.set方法
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
set方法是替換數(shù)組某個位置的值。先檢查下標(biāo)是否越界绰更，然后取出舊值瞧挤，把新值替換進(jìn)去，最后返回舊值給用戶儡湾。
3.add方法
(1)一個參的方法
在list末尾加上一個元素
public boolean add(E e) {
//確保內(nèi)部容量特恬，傳的是size+1的最小容量值，避免浪費(fèi)
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) {
//實際數(shù)組大小如果為空的話徐钠，初始化max(10癌刽，minCapacity)
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
//確保明確的容量
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
//如果最終所需的最小容量>目前數(shù)組的長度，則進(jìn)行擴(kuò)容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
//新容量=老容量+老容量/2
int newCapacity = oldCapacity + (oldCapacity >> 1);
//擴(kuò)容后還比最小需求容量小的話尝丐，直接使用最小需求容量作為新的容量大小
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
//如果新的容量超過了最大的數(shù)組容量显拜，則進(jìn)行巨大化處理
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
//講數(shù)組拷貝進(jìn)新擴(kuò)容的大數(shù)組里面
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
(2)兩個參的方法
在list指定的位置插入一個元素
public void add(int index, E element) {
//越界檢查
rangeCheckForAdd(index);
//確保內(nèi)部容量，不夠會調(diào)用grow進(jìn)行擴(kuò)容
ensureCapacityInternal(size + 1); // Increments modCount!!
//復(fù)制數(shù)組爹袁，arraycopy(原數(shù)組远荠，源數(shù)組中的起始位置，目標(biāo)數(shù)組失息，目標(biāo)數(shù)據(jù)中的起始位置譬淳，要復(fù)制的數(shù)組元素的數(shù)量)
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
4.remove方法
(1)刪除指定位置的方法
刪除指定位置元素，返回該元素
public E remove(int index) {
//檢查是否越界
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
//剩下元素的位置往前移動
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
//將索引指向null,讓GC回收多余末尾的舊值
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
(2)刪除第一個匹配到的元素
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;
}
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;
//說是刪除盹兢，其實就是移動后面的元素覆蓋掉前面的元素邻梆，再將最后的元素索引設(shè)置為空，以此達(dá)到刪除的目的绎秒。
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
}
(3)刪除一段區(qū)間的元素
fromIndex<=刪除區(qū)間<toIndex
protected void removeRange(int fromIndex, int toIndex) {
modCount++;
int numMoved = size - toIndex;
System.arraycopy(elementData, toIndex, elementData, fromIndex,
numMoved);
// clear to let GC do its work
int newSize = size - (toIndex-fromIndex);
for (int i = newSize; i < size; i++) {
elementData[i] = null;
}
size = newSize;
}
對比jdk11的寫法
protected void removeRange(int fromIndex, int toIndex) {
if (fromIndex > toIndex) {
throw new IndexOutOfBoundsException(
outOfBoundsMsg(fromIndex, toIndex));
}
modCount++;
shiftTailOverGap(elementData, fromIndex, toIndex);
}
private void shiftTailOverGap(Object[] es, int lo, int hi) {
System.arraycopy(es, hi, es, lo, size - hi);
for (int to = size, i = (size -= hi - lo); i < to; i++)
es[i] = null;
}
(4)removeAll和retainAll
//刪除源數(shù)組中包含目標(biāo)數(shù)組的元素
public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, false);//false表示不保留相同的元素确虱，即刪除
}
//交集，保留源數(shù)組中包含目標(biāo)數(shù)組的元素
public boolean retainAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, true);//true表示保留相同的元素
}
private boolean batchRemove(Collection<?> c, boolean complement) {
final Object[] elementData = this.elementData; //拿原集合出來
int r = 0, w = 0;
boolean modified = false; //有沒有改變標(biāo)志
try {
for (; r < size; r++)//循環(huán)每一個原集合的元素
if (c.contains(elementData[r]) == complement)//判斷每一個源元素是否存在于對比的list中。complement為true則把元素保存下來(retainAll);為false則不保留(removeAll)
elementData[w++] = elementData[r];
} finally {
// Preserve behavioral compatibility with AbstractCollection,
// even if c.contains() throws.
if (r != size) {//如果contains過程出錯校辩，則把剩下的源數(shù)據(jù)的元素復(fù)制到目標(biāo)數(shù)組里面去
System.arraycopy(elementData, r,//源數(shù)組窘问，源起始位置
elementData, w,//目標(biāo)數(shù)組，目標(biāo)起始位置
size - r);//復(fù)制的長度
w += size - r;//更新目標(biāo)數(shù)組的最新長度
}
if (w != size) {//目標(biāo)數(shù)組剩下的元素為源數(shù)組的元素宜咒，可以==null惠赫，讓gc回收掉
// clear to let GC do its work
for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size - w;
size = w;
modified = true;//數(shù)組的大小有變化則返回true;
}
}
return modified;
}
(5)indexOf和lastIndexOf
//返回源數(shù)組中第一個命中的下標(biāo)，如沒有則返回-1故黑。
public int indexOf(Object o) {
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]))
return i;
}
return -1;
}
//倒序?qū)ふ叶郏祷氐谝粋€命中的下標(biāo)
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;
}
(6)clear()
public void clear() {
modCount++;
// clear to let GC do its work
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
問題
1.默認(rèn)初始化大小
/**
* Default initial capacity.
*/
private static final int DEFAULT_CAPACITY = 10;
2.怎么擴(kuò)容
當(dāng)判斷需要的最小容量大于list中數(shù)組的長度時，則通過grow擴(kuò)容场晶，首先擴(kuò)大為原數(shù)組的1.5倍混埠，還不夠就擴(kuò)充為需求的容量大小。
3.最大容量
最大容量為MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
4.怎么找到下一個的
因為lsit的底層存儲還是數(shù)組诗轻，所以直接通過下標(biāo)定位就行了钳宪。
5.線程安全嗎
不安全的，主要問題出現(xiàn)在獲取size大小操作完后扳炬，size++這里不是原子性的吏颖。導(dǎo)致會出出現(xiàn)臟讀的情況。舉例：A和B兩個線程同時調(diào)用add方法
- 初始列表size大小為0恨樟。此時兩個線程同時拿到size為0半醉。
- 線程A執(zhí)行插入操作，將elementData[0]=A
- 此時線程B也執(zhí)行插入操作劝术，將elementData[0]=B
- 線程A將size++
- 線程B將size++
此時我們會發(fā)現(xiàn)ArrayList的size變成了2缩多，[0]=B;[1]=null。這就出現(xiàn)線程不安全的問題了
6.和hashmap的區(qū)別
額外知識點(diǎn)
1.transient關(guān)鍵字
/**
* 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 acces Object[] elementData; // non-private to simplify nested class access
transient的字面意思是短暫的养晋，在java中被此關(guān)鍵字修飾的屬性值將不會被序列化瞧壮。
具體可查看：https://baijiahao.baidu.com/s?id=1636557218432721275&wfr=spider&for=pc
2.MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
The maximum size of array to allocate.
Some VMs reserve some header words in an array.
Attempts to allocate larger arrays may result in
OutOfMemoryError: Requested array size exceeds VM limit
有一些虛擬機(jī)在數(shù)組中保留了一些頭信息，為了避免內(nèi)存溢出而已匙握。
3.modCount的作用
在 AbstractList 中咆槽，有一個全局變量 madCount，記錄了結(jié)構(gòu)性改變的次數(shù)圈纺。結(jié)構(gòu)性改變指的是那些修改了列表大小的操作秦忿，在迭代過程中可能會造成錯誤的結(jié)果。
madCount 交由迭代器（Iterator）和列表迭代器（ListIterator）使用蛾娶，當(dāng)進(jìn)行 next()灯谣、remove()、previous()蛔琅、set()胎许、add() 等操作時，如果 modCount 的值意外改變，那么迭代器或者列表迭代器就會拋出 ConcurrentModificationException 異常辜窑。
如果希望提供快速失敼呈觥（fail-fast）機(jī)制，那么其子類就應(yīng)該在 add(int, E)穆碎、remove(int) 等結(jié)構(gòu)性改變的方法中將 madCount 變量自增牙勘，否則可以忽略該變量。
