Java集合框架ArrayList源碼分析（一）
ArrayList底層維護(hù)的是一個(gè)動(dòng)態(tài)數(shù)組，每個(gè)ArrayList實(shí)例都有一個(gè)容量。該容量是指用來(lái)存儲(chǔ)列表元素的數(shù)組的大小。它總是至少等于列表的大小。隨著向 ArrayList 中不斷添加元素，其容量也自動(dòng)增長(zhǎng)。
ArrayList不是同步的（也就是說(shuō)不是線程安全的），如果多個(gè)線程同時(shí)訪問(wèn)一個(gè)ArrayList實(shí)例，而其中至少一個(gè)線程從結(jié)構(gòu)上修改了列表，那么它必須保持外部同步，在多線程環(huán)境下，可以使用Collections.synchronizedList方法聲明一個(gè)線程安全的ArrayList，例如：
List arraylist = Collections.synchronizedList(new ArrayList());
下面通過(guò)ArrayList的源碼來(lái)分析其原理。
1、ArrayList的構(gòu)造方法：ArrayList提供了三種不同的構(gòu)造方法
1) ArrayList()，構(gòu)造一個(gè)初始容量為 10 的空列表。
2) ArrayList(int initialCapacity)，構(gòu)造一個(gè)具有指定初始容量的空列表。
3) ArrayList(Collection<? extends E> c)，構(gòu)造一個(gè)包含指定 collection 的元素的列表，這些元素是按照該 collection 的迭代器返回它們的順序排列的。
源碼如下：
private transient Object[] elementData;
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
this.elementData = new Object[initialCapacity]; //生成一個(gè)長(zhǎng)度為10的Object類型的數(shù)組
}
public ArrayList() {
this(10); //調(diào)用ArrayList(int i)
}<br><br>
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray(); //返回包含此 collection 中所有元素的數(shù)組
size = elementData.length;
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class); //復(fù)制指定的數(shù)組，返回包含相同元素和長(zhǎng)度的Object類型的數(shù)組
}
當(dāng)采用不帶參數(shù)的構(gòu)造方法ArrayList()生成一個(gè)集合對(duì)象時(shí)，其實(shí)是在底層調(diào)用ArrayList(int initialCapacity)這一構(gòu)造方法生產(chǎn)一個(gè)長(zhǎng)度為10的Object類型的數(shù)組。當(dāng)采用帶有集合類型參數(shù)的構(gòu)造方法時(shí)，在底層生成一個(gè)包含相同的元素和長(zhǎng)度的Object類型的數(shù)組。
2、add方法：ArrayList提供了兩種添加元素的add方法
1) add(E e)，將指定的元素添加到此列表的尾部。
2) add(int index, E e)，將指定的元素插入此列表中的指定位置。向右移動(dòng)當(dāng)前位于該位置的元素（如果有）以及所有后續(xù)元素（將其索引加 1）private int size;
public boolean add(E e) {
ensureCapacity(size + 1); // 擴(kuò)大數(shù)組容量
elementData[size++] = e; //將元素e添加到下標(biāo)為size的Object數(shù)組中，并且執(zhí)行size++
return true;
}
public void add(int index, E element) {
if (index > size || index < 0) //如果指定要插入的數(shù)組下標(biāo)超過(guò)數(shù)組容量或者指定的下標(biāo)小于0，拋異常
throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
ensureCapacity(size+1); // 擴(kuò)大數(shù)組容量
System.arraycopy(elementData, index, elementData, index + 1,size - index); //從指定源數(shù)組中復(fù)制一個(gè)數(shù)組，復(fù)制從指定的位置開(kāi)始，到目標(biāo)數(shù)組的指定位置結(jié)束。<br> // elementData --- 源數(shù)組 index --- 源數(shù)組中的起始位置 <br> // elementData --- 目標(biāo)數(shù)組 index+1 --- 目標(biāo)數(shù)組中的起始位置<br> // size - index --- 要復(fù)制的數(shù)組元素的數(shù)量
elementData[index] = element; //將要添加的元素放到指定的數(shù)組下標(biāo)處
size++;
}
public void ensureCapacity(int minCapacity) {
modCount++;
int oldCapacity = elementData.length; //原數(shù)組的容量
if (minCapacity > oldCapacity) {
Object oldData[] = elementData;
int newCapacity = (oldCapacity * 3)/2 + 1; //定義新數(shù)組的容量，為原數(shù)組容量的1.5倍+1
if (newCapacity < minCapacity)
newCapacity = minCapacity;
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity); //復(fù)制指定的數(shù)組，返回新數(shù)組的容量為newCapacity
}
}
如果集合中添加的元素超過(guò)了10個(gè)，那么ArrayList底層會(huì)新生成一個(gè)數(shù)組，長(zhǎng)度為原數(shù)組的1.5倍+1，并將原數(shù)組中的元素copy到新數(shù)組中，并且后續(xù)添加的元素都會(huì)放在新數(shù)組中，當(dāng)新數(shù)組的長(zhǎng)度無(wú)法容納新添加的元素時(shí)，重復(fù)該過(guò)程。這就是集合添加元素的實(shí)現(xiàn)原理。
3、get方法：
1) get(int index)，返回此列表中指定位置上的元素。
public E get(int index) {
RangeCheck(index); //檢查傳入的指定下標(biāo)是否合法
return (E) elementData[index]; //返回?cái)?shù)組下標(biāo)為index的數(shù)組元素
}
private void RangeCheck(int index) {
if (index >= size) //如果傳入的下標(biāo)大于或等于集合的容量，拋異常
throw new IndexOutOfBoundsException(
"Index: "+index+", Size: "+size);
}
4、remove方法：
1) E remove(int index)，移除此列表中指定位置上的元素。向左移動(dòng)所有后續(xù)元素（將其索引減 1）。
2) boolean remove(Object o)，移除此列表中首次出現(xiàn)的指定元素（如果存在）。如果列表不包含此元素，則列表不做改動(dòng)，返回boolean值。
public E remove(int index) {
RangeCheck(index); //檢查指定的下標(biāo)是否合法
modCount++;
E oldValue = (E) elementData[index]; //獲取指定下標(biāo)的數(shù)組元素
int numMoved = size - index - 1; //要移動(dòng)的元素個(gè)數(shù)
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index, numMoved); //移動(dòng)數(shù)組元素
elementData[--size] = null; // Let gc do its work
return oldValue;
}
public boolean remove(Object o) {
if (o == null) { //如果傳入的參數(shù)為null
for (int index = 0; index < size; index++)
if (elementData[index] == null) { //移除首次出現(xiàn)的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) { //移除指定位置的元素,實(shí)現(xiàn)方法類似remove(int i)
modCount++;
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // Let gc do its work
}
5、clone方法：
1) Object clone()，返回此ArrayList實(shí)例的淺表副本（不復(fù)制這些元素本身） 。
public Object clone() {
try {
ArrayList<E> v = (ArrayList<E>) super.clone(); //調(diào)用Object類的clone方法返回一個(gè)ArrayList對(duì)象
v.elementData = Arrays.copyOf(elementData, size); //復(fù)制目標(biāo)數(shù)組
v.modCount = 0;
return v;
} catch (CloneNotSupportedException e) {
// this shouldn't happen, since we are Cloneable
throw new InternalError();
}
}
以上通過(guò)對(duì)ArrayList部分關(guān)鍵源碼的分析，知道了ArrayList底層的實(shí)現(xiàn)原理，關(guān)于ArrayList源碼有以下幾點(diǎn)幾點(diǎn)總結(jié)：
1) ArrayList 底層是基于數(shù)組來(lái)實(shí)現(xiàn)的，可以通過(guò)下標(biāo)準(zhǔn)確的找到目標(biāo)元素，因此查找的效率高；但是添加或刪除元素會(huì)涉及到大量元素的位置移動(dòng)，效率低。
2) ArrayList提供了三種不同的構(gòu)造方法，無(wú)參數(shù)的構(gòu)造方法默認(rèn)在底層生成一個(gè)長(zhǎng)度為10的Object類型的數(shù)組，當(dāng)集合中添加的元素個(gè)數(shù)大于10，數(shù)組會(huì)自動(dòng)進(jìn)行擴(kuò)容，即生成一個(gè)新的數(shù)組，并將原數(shù)組的元素放到新數(shù)組中。
3) ensureCapacity方法對(duì)數(shù)組進(jìn)行擴(kuò)容，它會(huì)生成一個(gè)新數(shù)組，長(zhǎng)度是原數(shù)組的1.5倍+1，隨著向ArrayList中不斷添加元素，當(dāng)數(shù)組長(zhǎng)度無(wú)法滿足需要時(shí)，重復(fù)該過(guò)程。
以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
相關(guān)文章
Java使用正則表達(dá)式驗(yàn)證用戶名和密碼的方法
這篇文章主要介紹了Java使用正則表達(dá)式驗(yàn)證用戶名和密碼的方法，本文給大家介紹的非常詳細(xì)，具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2019-09-09
這篇文章主要為大家介紹了java?緩沖流的概念使用方法以及實(shí)例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2023-06-06
Netty分布式Server啟動(dòng)流程服務(wù)端初始化源碼分析
本章主要講解server啟動(dòng)的關(guān)鍵步驟,?讀者只需要了解server啟動(dòng)的大概邏輯,?知道關(guān)鍵的步驟在哪個(gè)類執(zhí)行即可,?并不需要了解每一步的運(yùn)作機(jī)制,?之后會(huì)對(duì)每個(gè)模塊進(jìn)行深度分析2022-03-03
這篇文章主要介紹了Java中的字符串常量池詳細(xì)介紹,JVM為了減少字符串對(duì)象的重復(fù)創(chuàng)建,其維護(hù)了一個(gè)特殊的內(nèi)存,這段內(nèi)存被成為字符串常量池或者字符串字面量池,需要的朋友可以參考下2015-01-01
下面小編就為大家?guī)?lái)一篇淺談Java枚舉的作用與好處。小編覺(jué)得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2016-07-07
SpringMVC + jquery.uploadify實(shí)現(xiàn)上傳文件功能
文件上傳是很多項(xiàng)目都會(huì)使用到的功能，SpringMVC當(dāng)然也提供了這個(gè)功能。不過(guò)小編不建議在項(xiàng)目中通過(guò)form表單來(lái)提交文件上傳，這樣做的局限性很大。下面這篇文章主要介紹了利用SpringMVC + jquery.uploadify實(shí)現(xiàn)上傳文件功能的相關(guān)資料，需要的朋友可以參考下。2017-06-06
Spring Boot 2結(jié)合Spring security + JWT實(shí)現(xiàn)微信小程序登錄
這篇文章主要介紹了Spring Boot 2結(jié)合Spring security + JWT實(shí)現(xiàn)微信小程序登錄,本文給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2021-01-01
SpringBoot之groups應(yīng)對(duì)不同的Validation規(guī)則自定義方式
這篇文章主要介紹了SpringBoot之groups應(yīng)對(duì)不同的Validation規(guī)則自定義方式，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2021-10-10
這篇文章主要介紹了Java并發(fā)之BlockingQueue的使用，小編覺(jué)得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2018-06-06
Spring實(shí)現(xiàn)在非controller中獲取request對(duì)象
這篇文章主要介紹了Spring實(shí)現(xiàn)在非controller中獲取request對(duì)象方式，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2021-08-08