Java的ArrayList擴容源碼解析
ArrayList擴容源碼
1、擴容原理概括
ArrayList的擴容原理如下:
- 初始容量:在創(chuàng)建ArrayList對象時,默認會分配一個初始容量。初始容量可以通過構造函數(shù)進行指定,若未指定,則默認為10。例如,ArrayList<String> list = new ArrayList<>();會創(chuàng)建一個初始容量為10的ArrayList。
- 添加元素:當向ArrayList中添加元素時,會先檢查當前元素個數(shù)是否已經達到了數(shù)組的容量上限。如果元素個數(shù)等于或超過了容量上限,就需要進行擴容。
- 擴容機制:擴容時,ArrayList會創(chuàng)建一個更大的新數(shù)組,并將原有的元素復制到新數(shù)組中。默認情況下,新數(shù)組的大小是原來容量的1.5倍(即增長50%)。例如,如果當前容量為10,那么擴容后的新容量為15。
- 數(shù)組復制:在擴容時,ArrayList使用System.arraycopy()方法將原始數(shù)組中的元素復制到新的數(shù)組中。這是一個底層的高效數(shù)組復制方法,可以快速地將原有的數(shù)據(jù)移動到新數(shù)組中。
- 更新引用:在完成數(shù)組復制后,ArrayList會更新內部的引用,指向新的數(shù)組。這樣,原先的數(shù)組就會被垃圾回收器回收。
通過動態(tài)擴容,ArrayList能夠在添加元素時保持高效的性能。擴容操作是有一定開銷的,但由于擴容的時間復雜度為O(n),其中n是當前元素個數(shù),所以平均情況下,每次添加元素的時間復雜度仍然是O(1)。
同時,擴容的增長因子(即容量的增加比例)也可以被修改,以滿足特定需求。
2、源碼解析
例如,對于如下list進行添加元素,初始容量設置為5,添加6個元素:
ArrayList<String> list = new ArrayList<>(5);
list.add("1");
list.add("2");
list.add("3");
list.add("777");
list.add("888");
list.add("999");對于一開始的前五個元素而言:
public boolean add(E e) {
modCount++;
add(e, elementData, size);//e是“1”,size是0,即目前元素數(shù)量,也可以理解為數(shù)組的索引
return true;
}
//add源碼:
private void add(E e, Object[] elementData, int s) {
if (s == elementData.length)//當元素數(shù)量等于arraylist數(shù)組長度,才grow擴容
elementData = grow();
elementData[s] = e;//否則直接在索引位置賦值
size = s + 1;//并將索引右移
}但在第6個元素“999”添加進去的時候,要進入grow方法進行擴容:
private void add(E e, Object[] elementData, int s) { //e是“999”,s為5
if (s == elementData.length)//已經相等
elementData = grow();//步入grow
elementData[s] = e;
size = s + 1;
}
//grow源碼:輸入size + 1
private Object[] grow(int minCapacity) {
int oldCapacity = elementData.length;//舊的數(shù)組大小
//接下來,檢查當前數(shù)組是否為空,或者不是使用默認初始容量的空數(shù)組(即DEFAULTCAPACITY_EMPTY_ELEMENTDATA)。如果是空數(shù)組,則說明是第一次添加元素,使用默認初始容量。
if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
int newCapacity = ArraysSupport.newLength(oldCapacity,
minCapacity - oldCapacity, /* minimum growth */
oldCapacity >> 1 /* preferred growth */);//計算新數(shù)組大小
return elementData = Arrays.copyOf(elementData, newCapacity);
} else {
return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
}
}
//ArraysSupport.newLength源碼:
public static int newLength(int oldLength, int minGrowth, int prefGrowth) {
// assert oldLength >= 0
// assert minGrowth > 0
//minGrowth就是6 - 5 = 1,即,至少需要增大的容量
//prefGrowth為數(shù)組的舊容量的1/2
//求其max,一般為1/2。加上oldlength,所以為1.5倍
int newLength = Math.max(minGrowth, prefGrowth) + oldLength;
if (newLength - MAX_ARRAY_LENGTH <= 0) {
return newLength;
}
return hugeLength(oldLength, minGrowth);
}
//最后調用Arrays.copyOf,內部使用System.arraycopy()方法將原始數(shù)組中的元素復制到新的數(shù)組中實現(xiàn)擴容后,添加元素步驟同上,結束,return true
到此這篇關于Java的ArrayList擴容源碼解析的文章就介紹到這了,更多相關ArrayList擴容源碼內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家!
相關文章
詳解Spring Boot對 Apache Pulsar的支持
Spring Boot通過提供spring-pulsar和spring-pulsar-reactive自動配置支持Apache Pulsar,類路徑中這些依賴存在時,Spring Boot自動配置命令式和反應式Pulsar組件,PulsarClient自動注冊,默認連接本地Pulsar實例,感興趣的朋友一起看看吧2024-11-11
SpringBoot詳解整合MyBatis過程中可能遇到的問題
因為Spring Boot框架開發(fā)的便利性,所以實現(xiàn)Spring Boot與數(shù)據(jù)訪問層框架(例如MyBatis)的整合非常簡單,主要是引入對應的依賴啟動器,并進行數(shù)據(jù)庫相關參數(shù)設置即可2022-07-07
SpringBoot中注解@ConfigurationProperties與@Value的區(qū)別與使用詳解
本文主要介紹了SpringBoot中注解@ConfigurationProperties與@Value的區(qū)別與使用,具有一定的參考價值,感興趣的小伙伴們可以參考一下2021-09-09

