當(dāng)前位置:首頁 > 公眾號(hào)精選 > 架構(gòu)師社區(qū)
[導(dǎo)讀]前言ArrayList是Java集合框架中比較常用的數(shù)據(jù)結(jié)構(gòu)了。繼承自AbstractList,實(shí)現(xiàn)了List接口。底層基于數(shù)組實(shí)現(xiàn)容量大小動(dòng)態(tài)變化。一看就是一個(gè)比較重要的模塊,所以我們今天就來學(xué)習(xí)一下ArrayList相關(guān)知識(shí)。ArrayList的數(shù)據(jù)結(jié)構(gòu)和作用ArrayLis...

前言

ArrayList是Java集合框架中比較常用的數(shù)據(jù)結(jié)構(gòu)了。繼承自AbstractList,實(shí)現(xiàn)了List接口。底層基于數(shù)組實(shí)現(xiàn)容量大小動(dòng)態(tài)變化。一看就是一個(gè)比較重要的模塊,所以我們今天就來學(xué)習(xí)一下ArrayList相關(guān)知識(shí)。

ArrayList的數(shù)據(jù)結(jié)構(gòu)和作用

ArrayList數(shù)據(jù)結(jié)構(gòu)是數(shù)組,用來裝載數(shù)據(jù)。
相對(duì)于LinkedList,查詢效率高,因?yàn)榈讓邮菙?shù)組,分配的是連續(xù)的內(nèi)存空間,CPU在讀取時(shí)可以緩存連續(xù)的內(nèi)存空間,大幅度降低讀取的性能開銷;增刪效率低,相對(duì)于Vector來說是線程不安全。
雖然ArrayList是線程不安全的,但在我們實(shí)際的應(yīng)用過程中,一般都是用來查詢,涉及到增刪的操作比較少,如果涉及到的增刪操作比較頻繁的場(chǎng)景,我們可以選擇LinkedList,如果想保證線程安全,可以使用Vector、CopyOrWriteArray。

如何實(shí)現(xiàn)存放任意數(shù)量的對(duì)象

ArrayList構(gòu)造器有無參構(gòu)造和有參構(gòu)造。在有參構(gòu)造器中,ArrayList可以通過構(gòu)造方法在初始化的時(shí)候進(jìn)行指定底層數(shù)組的大小。但是我們?cè)谑褂糜袇?gòu)造時(shí),會(huì)不會(huì)初始化數(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);
}
}
由代碼可知,我們可以很明確地得出結(jié)論:不會(huì)初始化數(shù)組大小。不信的話我們可以測(cè)試一下:
public static void main(String[] args){
//此處使用有參構(gòu)造,大小為10
ArrayListarrayList = new ArrayList<>(10);
System.out.println("size:" arrayList);
arrayList.set(1, "A");
}
關(guān)于ArrayList的幾大問題,看完還不懂來打我!看到這里是不是已經(jīng)懵圈了?不要慌,我們慢慢來分析。我們的參數(shù)是 initialCapacity,這里是將參數(shù)基于 elementData 設(shè)置的,并不是直接設(shè)置的數(shù)組大?。ㄖ档米⒁獾氖?,ensureCapacity();方法也是這種原理)。我們也可以理解為這個(gè)數(shù)組現(xiàn)在理論上最大可以裝10個(gè)數(shù)據(jù),但是他現(xiàn)在還是空的。
在無參構(gòu)造器中,初始化出一個(gè)默認(rèn)空的數(shù)組,數(shù)組容量為 0,當(dāng)我們調(diào)用add();方法是,默認(rèn)分配【DEFAULT_CAPACITY = 10】的初始容量。下面會(huì)具體介紹新增過程,此處不再贅述。
/**
* 數(shù)組默認(rèn)初始容量
*/

private static final int DEFAULT_CAPACITY = 10;
/**
* 用于默認(rèn)大小的空實(shí)例的共享空數(shù)組實(shí)例。
* 與 EMPTY_ELEMENTDATA 區(qū)分開來,以了解何時(shí)膨脹多少添加第一個(gè)元素。
*/

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* 構(gòu)造一個(gè)初始空列表。
*/

public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
但是,對(duì)于無參構(gòu)造和有參構(gòu)造,數(shù)組都是有長(zhǎng)度限制的,ArrayList是通過什么方式去實(shí)現(xiàn)可以存放任意數(shù)量的對(duì)象,長(zhǎng)度沒有限制的呢?不要慌,原來這個(gè)地方也是用到了數(shù)組的擴(kuò)容。

數(shù)組的擴(kuò)容

當(dāng)前我們有一個(gè)初始容器為10的數(shù)組,且每個(gè)位置已經(jīng)插滿數(shù)據(jù),但是現(xiàn)在又要新增一條數(shù)據(jù),這個(gè)時(shí)候當(dāng)前數(shù)組已經(jīng)不能滿足我們的要求了,那我們就需要進(jìn)行擴(kuò)容;
關(guān)于ArrayList的幾大問題,看完還不懂來打我!然后我們就需要進(jìn)行擴(kuò)容,擴(kuò)大到原來的1.5倍,即【10 10 / 2】;
關(guān)于ArrayList的幾大問題,看完還不懂來打我!最后將原數(shù)組的數(shù)據(jù)原封不動(dòng)地移動(dòng)到新數(shù)組,再返回新數(shù)組的地址,這樣ArrayList中數(shù)據(jù)就是新的數(shù)組了。
關(guān)于ArrayList的幾大問題,看完還不懂來打我!接下來,我們就看一下源碼中的具體實(shí)現(xiàn)吧
//擴(kuò)容前置判斷
private void ensureExplicitCapacity(int minCapacity) {
modCount ;
//minCapacity: 插入數(shù)據(jù)后容器大小或者默認(rèn)容器大小
//當(dāng)minCapacity比當(dāng)前數(shù)組大時(shí),說明需要擴(kuò)容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
//擴(kuò)容具體過程
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
//此處java 8采用了位運(yùn)算,提升效率
int newCapacity = oldCapacity   (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 直接使用數(shù)組的復(fù)制方法
elementData = Arrays.copyOf(elementData, newCapacity);
}

ArrayList的的新增

在ArrayList中,新增有三個(gè)方法分別是以下三種:
//1\. 將指定的元素附加到此列表的末尾
public boolean add(E e) {
ensureCapacityInternal(size 1); // Increments modCount!!
elementData[size ] = e;
return true;
}
//2\. 在此指定位置插入指定元素列表。
public void add(int index, E element) {
//判斷指定參數(shù)是否超過范圍
rangeCheckForAdd(index);
ensureCapacityInternal(size 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index 1,
size - index);
elementData[index] = element;
size ;
}
//3\. 將指定集合中的所有元素追加到末尾這個(gè)列表,
//   按照它們返回的順序指定集合的迭代器。
public boolean addAll(Collection c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size   numNew); // Increments modCount
System.arraycopy(a, 0, elementData, size, numNew);
size  = numNew;
return numNew != 0;
}
由代碼可知,不管是哪種插入,我們都需要通過調(diào)用 ensureCapacityInternal(); 方法來校驗(yàn)數(shù)組長(zhǎng)度,如果長(zhǎng)度不夠,就進(jìn)行擴(kuò)容,前面我們已經(jīng)了解過。對(duì)于指定位置新增時(shí),我們?cè)谛r?yàn)完成之后通過調(diào)用 arraycopy(); 方法來實(shí)現(xiàn)數(shù)組的復(fù)制。下面我們就來了解一下指定位置插入的過程。
當(dāng)前我們有一個(gè)長(zhǎng)度為10,還有一個(gè)空位的數(shù)組;
關(guān)于ArrayList的幾大問題,看完還不懂來打我!現(xiàn)在我們需要插入一個(gè)【a】,目標(biāo)位置是【5】,則先復(fù)制一個(gè)數(shù)組,指定位置之前的數(shù)據(jù)不變,從【5】開始把后面的數(shù)據(jù)從【5 1】的位置開始復(fù)制,新數(shù)組空出位置【5】;
關(guān)于ArrayList的幾大問題,看完還不懂來打我!上一步我們已經(jīng)把【5】這個(gè)位置空出來了,然后將數(shù)據(jù)【a】插入空位,這樣就完成了指定位置插入的操作了。
關(guān)于ArrayList的幾大問題,看完還不懂來打我!由上可知,ArrayList在新增的需要把數(shù)據(jù)復(fù)制一份,這個(gè)操作如果是針對(duì)大數(shù)據(jù)量List,再加上擴(kuò)容的操作,那效率就慢了。

ArrayList的刪除

話不多說,我們先來看一下代碼:
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);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
由代碼可知,如果是刪除末位,則直接刪除就完成了操作;如果是將中間數(shù)據(jù)刪除,則此過程中也是類似于插入操作,將數(shù)組進(jìn)行了復(fù)制,調(diào)用arraycopy();方法。下面我們就來了解一下指定位置刪除的過程。
當(dāng)前我們有一個(gè)長(zhǎng)度為10;
關(guān)于ArrayList的幾大問題,看完還不懂來打我!現(xiàn)在我們需要?jiǎng)h除目標(biāo)位置為【5】的數(shù)據(jù),則先復(fù)制一個(gè)數(shù)組,指定位置之前的數(shù)據(jù)不變,從【5 1】之后的數(shù)據(jù)進(jìn)行復(fù)制到新數(shù)組;
關(guān)于ArrayList的幾大問題,看完還不懂來打我!得到新的數(shù)組,就是刪除了指定位置【5】數(shù)據(jù)的數(shù)組了。
關(guān)于ArrayList的幾大問題,看完還不懂來打我!同理,ArrayList的刪除和新增一樣效率比較低。對(duì)于數(shù)據(jù)量大的數(shù)組需要復(fù)制和移動(dòng)的位置就比較大了。

ArrayList適合做隊(duì)列嗎

一般的隊(duì)列是先進(jìn)先出隊(duì)列(FIFO),從尾部出入,頭部刪除。
對(duì)于數(shù)組是十分適合做隊(duì)列的,比如 ArrayBlockingQueue內(nèi)部的實(shí)現(xiàn)就是通過一個(gè)定長(zhǎng)數(shù)組來實(shí)現(xiàn)一個(gè)環(huán)形定長(zhǎng)隊(duì)列,使用兩個(gè)偏移量來標(biāo)記數(shù)組的讀位置和寫位置,如果超過長(zhǎng)度就折回到數(shù)組開頭。但是前提必須是一個(gè)定長(zhǎng)的數(shù)組。
因?yàn)樵贏rrayList中,底層雖然是數(shù)組,但是數(shù)組長(zhǎng)度是不確定的。這樣我們就需要進(jìn)行大量的增加和刪除操作,就算是指定位置的刪除和新增,它也是需要經(jīng)過數(shù)組復(fù)制,這樣的話,會(huì)比較消耗性能。
因此,定長(zhǎng)數(shù)組適合做隊(duì)列,ArrayList不適合做隊(duì)列


本站聲明: 本文章由作者或相關(guān)機(jī)構(gòu)授權(quán)發(fā)布,目的在于傳遞更多信息,并不代表本站贊同其觀點(diǎn),本站亦不保證或承諾內(nèi)容真實(shí)性等。需要轉(zhuǎn)載請(qǐng)聯(lián)系該專欄作者,如若文章內(nèi)容侵犯您的權(quán)益,請(qǐng)及時(shí)聯(lián)系本站刪除。
換一批
延伸閱讀

9月2日消息,不造車的華為或?qū)⒋呱龈蟮莫?dú)角獸公司,隨著阿維塔和賽力斯的入局,華為引望愈發(fā)顯得引人矚目。

關(guān)鍵字: 阿維塔 塞力斯 華為

倫敦2024年8月29日 /美通社/ -- 英國(guó)汽車技術(shù)公司SODA.Auto推出其旗艦產(chǎn)品SODA V,這是全球首款涵蓋汽車工程師從創(chuàng)意到認(rèn)證的所有需求的工具,可用于創(chuàng)建軟件定義汽車。 SODA V工具的開發(fā)耗時(shí)1.5...

關(guān)鍵字: 汽車 人工智能 智能驅(qū)動(dòng) BSP

北京2024年8月28日 /美通社/ -- 越來越多用戶希望企業(yè)業(yè)務(wù)能7×24不間斷運(yùn)行,同時(shí)企業(yè)卻面臨越來越多業(yè)務(wù)中斷的風(fēng)險(xiǎn),如企業(yè)系統(tǒng)復(fù)雜性的增加,頻繁的功能更新和發(fā)布等。如何確保業(yè)務(wù)連續(xù)性,提升韌性,成...

關(guān)鍵字: 亞馬遜 解密 控制平面 BSP

8月30日消息,據(jù)媒體報(bào)道,騰訊和網(wǎng)易近期正在縮減他們對(duì)日本游戲市場(chǎng)的投資。

關(guān)鍵字: 騰訊 編碼器 CPU

8月28日消息,今天上午,2024中國(guó)國(guó)際大數(shù)據(jù)產(chǎn)業(yè)博覽會(huì)開幕式在貴陽舉行,華為董事、質(zhì)量流程IT總裁陶景文發(fā)表了演講。

關(guān)鍵字: 華為 12nm EDA 半導(dǎo)體

8月28日消息,在2024中國(guó)國(guó)際大數(shù)據(jù)產(chǎn)業(yè)博覽會(huì)上,華為常務(wù)董事、華為云CEO張平安發(fā)表演講稱,數(shù)字世界的話語權(quán)最終是由生態(tài)的繁榮決定的。

關(guān)鍵字: 華為 12nm 手機(jī) 衛(wèi)星通信

要點(diǎn): 有效應(yīng)對(duì)環(huán)境變化,經(jīng)營(yíng)業(yè)績(jī)穩(wěn)中有升 落實(shí)提質(zhì)增效舉措,毛利潤(rùn)率延續(xù)升勢(shì) 戰(zhàn)略布局成效顯著,戰(zhàn)新業(yè)務(wù)引領(lǐng)增長(zhǎng) 以科技創(chuàng)新為引領(lǐng),提升企業(yè)核心競(jìng)爭(zhēng)力 堅(jiān)持高質(zhì)量發(fā)展策略,塑強(qiáng)核心競(jìng)爭(zhēng)優(yōu)勢(shì)...

關(guān)鍵字: 通信 BSP 電信運(yùn)營(yíng)商 數(shù)字經(jīng)濟(jì)

北京2024年8月27日 /美通社/ -- 8月21日,由中央廣播電視總臺(tái)與中國(guó)電影電視技術(shù)學(xué)會(huì)聯(lián)合牽頭組建的NVI技術(shù)創(chuàng)新聯(lián)盟在BIRTV2024超高清全產(chǎn)業(yè)鏈發(fā)展研討會(huì)上宣布正式成立。 活動(dòng)現(xiàn)場(chǎng) NVI技術(shù)創(chuàng)新聯(lián)...

關(guān)鍵字: VI 傳輸協(xié)議 音頻 BSP

北京2024年8月27日 /美通社/ -- 在8月23日舉辦的2024年長(zhǎng)三角生態(tài)綠色一體化發(fā)展示范區(qū)聯(lián)合招商會(huì)上,軟通動(dòng)力信息技術(shù)(集團(tuán))股份有限公司(以下簡(jiǎn)稱"軟通動(dòng)力")與長(zhǎng)三角投資(上海)有限...

關(guān)鍵字: BSP 信息技術(shù)
關(guān)閉
關(guān)閉