今天就跟大家聊聊有關(guān)如何用源碼分析ArrayList，可能很多人都不太了解，為了讓大家更加了解，小編給大家總結(jié)了以下內(nèi)容，希望大家根據(jù)這篇文章可以有所收獲。
目前創(chuàng)新互聯(lián)建站已為上千多家的企業(yè)提供了網(wǎng)站建設(shè)、域名、網(wǎng)頁空間、網(wǎng)站托管、服務(wù)器托管、企業(yè)網(wǎng)站設(shè)計(jì)、迪慶州網(wǎng)站維護(hù)等服務(wù)，公司將堅(jiān)持客戶導(dǎo)向、應(yīng)用為本的策略，正道將秉承"和諧、參與、激情"的文化，與客戶和合作伙伴齊心協(xié)力一起成長(zhǎng)，共同發(fā)展。
重慶分公司
重慶分公司
/** ArrayList的初始化容量 **/
public static final int DEFAULT_CAPACITY = 10;
/** 數(shù)組能存儲(chǔ)的最大元素容量 **/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
/** 空數(shù)組，當(dāng)調(diào)用無參數(shù)構(gòu)造函數(shù)的時(shí)候默認(rèn)給個(gè)空數(shù)組 **/
public static final Object[] EMPTY_ELEMENTDATA = {};
/** 真正保存數(shù)據(jù)的數(shù)組 **/
transient Object[] elementData;
/** 實(shí)際ArrayList的元素個(gè)數(shù) **/
private int size;ArrayList的初始化容量為10，真正的數(shù)據(jù)是存在elementData中，實(shí)際存儲(chǔ)的元素個(gè)數(shù)用size表示。
/** 無參構(gòu)造函數(shù) **/
public ArrayList() {
super();
this.elementData = EMPTY_ELEMENTDATA;
}
/** 初始化容量構(gòu)造函數(shù) **/
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0) {
throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
}
this.elementData = new Object[initialCapacity];
}
/** 已有集合構(gòu)造函數(shù) **/
public ArrayList(Collection c) {
elementData = c.toArray();
size = elementData.length;
if (elementData.getClass() != Object[].class) {
elementData = Arrays.copyOf(elementData, size, Object[].class);
}
}如果構(gòu)造函數(shù)不傳入List容量 則初始化elementData為空數(shù)組。
如果構(gòu)造函數(shù)傳入List容量 則初始化elementData為傳入容量的Object數(shù)組
如果構(gòu)造函數(shù)傳入了集合 則將集合轉(zhuǎn)換為數(shù)組賦值給elementData，同時(shí)設(shè)置size值為數(shù)組的長(zhǎng)度。
元素插入主要有以下四個(gè)方法：
boolean add(E e)
void add(int index, E e)
boolean addAll(Collection c)
boolean addAll(int index, Collection c)
/** 添加元素 **/
@Override
public boolean add(E e) {
//確保數(shù)組容量
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}在添加元素時(shí)，先通過ensureCapacityInternal方法保證elementData數(shù)組擁有足夠的容量。
然后直接插入尾部位置的元素并改變?cè)氐膶?shí)際總數(shù)量。
private void ensureCapacityInternal(int minCapacity) {
if (elementData == EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
//如果元素?cái)?shù)量將超過數(shù)組長(zhǎng)度 則需動(dòng)態(tài)擴(kuò)容
if (minCapacity - elementData.length > 0) {
grow(minCapacity);
}
}
/** 數(shù)組擴(kuò)容機(jī)制 **/
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity < minCapacity) {
newCapacity = minCapacity;
}
if (newCapacity > MAX_ARRAY_SIZE) {
newCapacity = minCapacity > MAX_ARRAY_SIZE ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}
elementData = Arrays.copyOf(elementData, newCapacity);
}先判斷需要保證的元素?cái)?shù)量是否大于elementData數(shù)組的長(zhǎng)度，如果大于，則需要將elementData數(shù)組進(jìn)行擴(kuò)容。
在擴(kuò)容時(shí)，先設(shè)置數(shù)組長(zhǎng)度newCapacity為原數(shù)組長(zhǎng)度的1.5倍，然后判斷需要保證的元素?cái)?shù)量是否大于newCapacity新數(shù)組的長(zhǎng)度，若仍然不夠，則直接設(shè)置newCapacity為需要保證的元素?cái)?shù)量。
然后將新數(shù)組長(zhǎng)度newCapacity與常量最大數(shù)組長(zhǎng)度對(duì)比，最后通過Arrays.copyOf方法進(jìn)行擴(kuò)容。
/** 在指定位置添加元素 **/
@Override
public void add(int index, E e) {
rangeCheckForAdd(index);
//確保數(shù)組容量
ensureCapacityInternal(size + 1);
//將插入位置后的所有元素往后移
System.arraycopy(elementData, index, elementData, index + 1, size - index);
elementData[index] = e;
size ++;
}先判斷index是否越界，然后通過ensureCapacityInternal方法保證elementData數(shù)組擁有足夠的容量。
然后將index之后的所有元素往后移動(dòng)。
最后插入index位置的值，并改變?cè)氐膶?shí)際總數(shù)量。
/** 往當(dāng)前集合中添加集合c **/
public boolean addAll(Collection c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew);
//將數(shù)組a中所有元素copy到elementData中
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}先將集合c轉(zhuǎn)換為Object數(shù)組a，并取出a的長(zhǎng)度。
然后通過ensureCapacityInternal方法保證elementData數(shù)組擁有足夠的容量。
將數(shù)組a復(fù)制到elementData數(shù)組的后面并改變?cè)氐膶?shí)際總數(shù)量。
/** 在當(dāng)前集合中的index位置添加集合c **/
public boolean addAll(int index, Collection c) {
rangeCheckForAdd(index);
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew);
//將index后面所有元素往后移動(dòng)
System.arraycopy(elementData, index, elementData, index + numNew, size - index);
//將數(shù)組a中元素插入到elementData的index位置
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}相比addAll(Collection c)方法僅多一步，將index后面所有元素往后移動(dòng)
元素移除主要有以下五個(gè)方法
void clear()
E remove(int index)
boolean remove(Object o)
boolean removeAll(Collection c)
boolean retainAll(Collection c)
/** 清空當(dāng)前集合中所有元素 **/
public void clear() {
modCount ++;
//將所有元素設(shè)置為null讓GC回收掉
for (int i = 0; i < size; i++) {
elementData[i] = null;
}
size = 0;
}將所有元素設(shè)置為null并設(shè)置size為0。
/** 移除指定位置index元素 **/
@Override
public E remove(int index) {
rangeCheck(index);
//獲取到舊的元素
E oldValue = (E) elementData[index];
//計(jì)算需要移動(dòng)的元素
int needMoveNum = size - index - 1;
if (needMoveNum > 0) {
//將移除位置后的所有元素往前移
System.arraycopy(elementData, index + 1, elementData, index, needMoveNum);
}
//將數(shù)組最后一個(gè)元素置為null
elementData[--size] = null;
return oldValue;
}
/** 檢測(cè)數(shù)組是否越界 **/
private void rangeCheck(int index) {
if (index >= size || index < 0) {
throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
}
}先檢測(cè)元素是否越界，然后根據(jù)索引獲取到原有元素oldValue。
數(shù)組移除時(shí)，需要將index后面的元素往前移動(dòng)一位，所以先根據(jù)移除元素的位置計(jì)算出需要移動(dòng)元素的個(gè)數(shù)needMoveNum，如果大于0就通過System.arraycopy方法移動(dòng)。
然后將最后一個(gè)元素設(shè)置為null，返回原有元素oldValue。
/** 移除指定元素o **/
@Override
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;
}
/** 相比remove(int index)方法，不需要檢測(cè)數(shù)組越界和返回舊元素 **/
private void fastRemove(int index) {
modCount++;
//計(jì)算需要移動(dòng)的元素
int needMoveNum = size - index - 1;
if (needMoveNum > 0) {
//將移除位置后的所有元素往前移
System.arraycopy(elementData, index + 1, elementData, index, needMoveNum);
}
//將數(shù)組最后一個(gè)元素置為null
elementData[--size] = null;
}如果指定的元素o是null,則循環(huán)找到一個(gè)為null的元素并移除。
否則循環(huán)數(shù)組元素，通過equals方法找到元素并移除。
/** 從當(dāng)前集合中移除集合c中所有的元素 **/
public boolean removeAll(Collection c) {
Objects.requireNonNull(c);
return batchRemove(c, false);
}/** 只保留當(dāng)前集合與指定集合c中都存在的元素 **/
public boolean retainAll(Collection c) {
Objects.requireNonNull(c);
return batchRemove(c, true);
}private boolean batchRemove(Collection c, boolean complement) {
final Object[] elementData = this.elementData;
int r = 0, w = 0;
boolean modified = false;
try {
for (; r < size; r++) {
//判斷是保留相同的還是保留不同的
if (c.contains(elementData[r]) == complement) {
elementData[w++] = elementData[r];
}
}
} finally {
//正常情況下 r和size是相等的 如果拋出異常 則將剩余未比較的復(fù)制到elementData中
if (r != size) {
System.arraycopy(elementData, r, elementData, w, size - r);
w += size - r;
}
//如果有移除的數(shù)據(jù)，w和size是不相等的 此時(shí)將W之后的數(shù)據(jù)置空 讓GC回收掉
if (w != size) {
for (int i = w; i < size; i++) {
elementData[i] = null;
}
modCount += size - w;
size = w;
modified = true;
}
}
return modified;
}/** 查詢?cè)?nbsp;**/
@Override
public E get(int index) {
//檢查索引是否越界
rangeCheck(index);
//返回?cái)?shù)組指定位置的元素
return elementData(index);
}判斷數(shù)組是否越界
返回指定位置的數(shù)組元素即可。
E elementData(int index) {
return (E) elementData[index];
}/** 更改元素 **/
@Override
public E set(int index, E e) {
rangeCheck(index);
//查詢?cè)性?
E oldValue = (E) elementData[index];
//設(shè)置為最新元素
elementData[index] = e;
return oldValue;
}先判斷數(shù)組是否越界
獲取到舊的元素
將當(dāng)前位置設(shè)置為新的元素
返回舊元素。
總結(jié)
ArrayList底層主要通過Object數(shù)組elementData實(shí)現(xiàn)
ArrayList初始化容量為10，擴(kuò)容時(shí)每次增加至原來的1.5倍
查詢更新操作時(shí)最簡(jiǎn)單，通過數(shù)組下標(biāo)可快速定位元素位置進(jìn)行操作
添加刪除時(shí)由于需要移動(dòng)后面的元素位置，所以會(huì)更加耗時(shí)；移動(dòng)元素位置時(shí)主要通過System.arraycopy方法實(shí)現(xiàn)
看完上述內(nèi)容，你們對(duì)如何用源碼分析ArrayList有進(jìn)一步的了解嗎？如果還想了解更多知識(shí)或者相關(guān)內(nèi)容，請(qǐng)關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道，感謝大家的支持。
