Java中的ArrayList和contains函數(shù)和擴(kuò)容機(jī)制(源碼詳解)
起因
在Leetcode上做題寫(xiě)了兩種暴力解法,但是執(zhí)行效率上不太一樣。

時(shí)間上差很遠(yuǎn),內(nèi)存雖然差不多但是前者擊敗30%,后者擊敗94%。這兩種解法區(qū)別是用一條ArrayList還是兩條來(lái)存數(shù)據(jù),所以contains雖然執(zhí)行次數(shù)一樣但是檢測(cè)的長(zhǎng)度上不一樣,而且ArrayList的擴(kuò)容次數(shù)也不一樣,所以學(xué)習(xí)一下。
contains(Object o)
直接翻(JDK8)源碼:

null和object區(qū)分開(kāi)來(lái)還是因?yàn)?code>equals有一方是null的話都會(huì)導(dǎo)致異常. 合并一起寫(xiě)的話可以用Objects.equals(obj1, obj2)的寫(xiě)法.
所以顯然暴力解法用到的contains的原理就是樸實(shí)無(wú)華的一遍遍搜索所以時(shí)間特別長(zhǎng).
ArrayList擴(kuò)容機(jī)制
省流: 直接看最下面的grow函數(shù).
如果是默認(rèn)的ArrayList, 添加元素時(shí)會(huì)先計(jì)算數(shù)組長(zhǎng)度, 如果元素個(gè)數(shù)+1大于當(dāng)前數(shù)組長(zhǎng)度+1大于elementData.length時(shí)進(jìn)行擴(kuò)容,擴(kuò)容后的數(shù)組大小是: oldCapacity + (oldCapacity >> 1) 可以理解成1.5倍擴(kuò)容。
涉及到的源碼:
// 向指定索引位置插入元素
public void add(int index, E element) {
// 檢查索引范圍
rangeCheckForAdd(index);
// 確保容量足夠
ensureCapacityInternal(size + 1); // 增加 modCount(用于支持并發(fā)修改的計(jì)數(shù)器)
// 使用 System.arraycopy 將元素后移,為新元素騰出位置, 這是跟另一個(gè)add的區(qū)別?????
System.arraycopy(elementData, index, elementData, index + 1, size - index);
elementData[index] = element; // 在指定位置插入新元素
size++; // 更新列表大小
}
// 在列表末尾添加元素
public boolean add(E e) {
// 確保容量足夠
ensureCapacityInternal(size + 1); // 增加 modCount
elementData[size++] = e; // 在列表末尾添加新元素
return true;
}
// 內(nèi)部方法:確保容量足夠
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
// 內(nèi)部方法:計(jì)算容量
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
// 如果內(nèi)部數(shù)組為空,返回默認(rèn)容量或所需容量中的較大者
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity; // 否則返回所需容量
}
// 內(nèi)部方法:確保容量足夠
private void ensureExplicitCapacity(int minCapacity) {
modCount++; // 增加并發(fā)修改計(jì)數(shù)器
// 檢查容量是否足夠,如果不夠則擴(kuò)展
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
// 內(nèi)部方法:擴(kuò)展容量
private void grow(int minCapacity) {
// 溢出安全的代碼
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1); // 新容量通常為舊容量的1.5倍
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity; // 如果新容量小于所需容量,使用所需容量
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity); // 處理可能的巨大容量情況
// 使用 Arrays.copyOf 擴(kuò)展數(shù)組容量
elementData = Arrays.copyOf(elementData, newCapacity);
}實(shí)際上Array.copyof底層調(diào)用的還是System.arraycopy.
到此這篇關(guān)于Java的ArrayList和contains函數(shù)和擴(kuò)容機(jī)制的文章就介紹到這了,更多相關(guān)Java ArrayList和contains函數(shù)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
項(xiàng)目中配置Maven為國(guó)內(nèi)源實(shí)現(xiàn)方式
這篇文章主要介紹了項(xiàng)目中配置Maven為國(guó)內(nèi)源實(shí)現(xiàn)方式,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2026-03-03
Spring Boot Starters簡(jiǎn)介及其優(yōu)劣勢(shì)
在這篇文章中,我們將向你介紹Spring Boot Starters,并將討論Spring Boot Starters的優(yōu)點(diǎn)和優(yōu)勢(shì),感興趣的朋友跟隨腳本之家小編一起學(xué)習(xí)吧2018-05-05
簡(jiǎn)單談?wù)刯ava中匿名內(nèi)部類(lèi)構(gòu)造函數(shù)
這篇文章主要簡(jiǎn)單給我們介紹了java中匿名內(nèi)部類(lèi)構(gòu)造函數(shù),并附上了簡(jiǎn)單的示例,有需要的小伙伴可以參考下。2015-11-11
Mybatis控制臺(tái)打印SQL執(zhí)行信息的方法詳解
Mybatis原始執(zhí)行方式Executor代碼實(shí)例
Java使用Spire.Doc for Java輕松搞定Word文檔打印

