ArrayList源碼探秘之Java動態(tài)數(shù)組的實現(xiàn)
一、成員變量
讀者需先對源碼的成員變量閱覽一遍,看個眼熟,有助于后面源碼的理解
private static final long serialVersionUID = 8683452581122892189L; /** * 默認初始容量大小 */ private static final int DEFAULT_CAPACITY = 10; /** * 空數(shù)組(用于空實例)。 */ private static final Object[] EMPTY_ELEMENTDATA = {}; //用于默認大小空實例的共享空數(shù)組實例。 //我們把它從EMPTY_ELEMENTDATA數(shù)組中區(qū)分出來,以知道在添加第一個元素時容量需要增加多少。 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; /** * 存儲ArrayList元素的數(shù)組緩沖區(qū) */ transient Object[] elementData; /** * ArrayList 所包含的元素個數(shù) */ private int size;
二、構(gòu)造器
1、默認構(gòu)造器
/** *默認構(gòu)造函數(shù),使用初始容量10構(gòu)造一個空列表(無參數(shù)構(gòu)造) */ public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; }
以無參數(shù)構(gòu)造方法創(chuàng)建 ArrayList時,實際上初始化賦值的是一個空數(shù)組。此時并沒有為它創(chuàng)建對象,當(dāng)真正對數(shù)組進行添加元素操作時,才真正分配容量。即向數(shù)組中添加第一個元素時,數(shù)組容量擴為 10。
2、帶初始容量參數(shù)構(gòu)造器
/** * 帶初始容量參數(shù)的構(gòu)造函數(shù)。(用戶自己指定容量) */ public ArrayList(int initialCapacity) { if (initialCapacity > 0) {//初始容量大于0 //創(chuàng)建initialCapacity大小的數(shù)組 this.elementData = new Object[initialCapacity]; } else if (initialCapacity == 0) {//初始容量等于0 //創(chuàng)建空數(shù)組 this.elementData = EMPTY_ELEMENTDATA; } else {//初始容量小于0,拋出異常 throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); } }
3、指定collection元素參數(shù)構(gòu)造器
/** *構(gòu)造包含指定collection元素的列表,這些元素利用該集合的迭代器按順序返回 *如果指定的集合為null,throws NullPointerException。 */ public ArrayList(Collection<? extends E> c) { elementData = c.toArray(); if ((size = elementData.length) != 0) { // c.toArray might (incorrectly) not return Object[] (see 6260652) if (elementData.getClass() != Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); } else { // replace with empty array. this.elementData = EMPTY_ELEMENTDATA; } }
三、add()方法擴容機制
在進入ArrayList的核心源碼擴容機制前,我們首先需要對源碼中涉及到的一些變量進行一個初步的了解,這將有助于你對源碼的深入了解
minCapacity
:數(shù)組所需的最小容量
elementData
:存儲ArrayList元素的數(shù)組緩沖區(qū)
public boolean add(E e) { ensureCapacityInternal(size + 1); // size = 0 elementData[size++] = e; return true; }
private void ensureCapacityInternal(int minCapacity) {//minCapacity = 1 ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));//elementData = {} }
private static int calculateCapacity(Object[] elementData, int minCapacity) { //判斷elementData是否為空數(shù)組 if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {//DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {} return Math.max(DEFAULT_CAPACITY, minCapacity);//DEFAULT_CAPACITY = 10;minCapacity = 1 } return minCapacity; }
private void ensureCapacityInternal(int minCapacity) {//minCapacity = 1 ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));//ensureExplicitCapacity(10) }
private void ensureExplicitCapacity(int minCapacity) {//minCapacity = 10 modCount++; if (minCapacity - elementData.length > 0)//elementData.length = 0 grow(minCapacity); }
private void grow(int minCapacity) {//minCapacity = 10 int oldCapacity = elementData.length;//oldCapacity = 0 int newCapacity = oldCapacity + (oldCapacity >> 1);//newCapacity = 1.5*oldCapacity = 0 if (newCapacity - minCapacity < 0)//minCapacity = 10 newCapacity = minCapacity;//newCapacity = 10 if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); //利用Arrays.copyOf()方法進行擴容 elementData = Arrays.copyOf(elementData, newCapacity); }
private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) // overflow throw new OutOfMemoryError(); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; }
1.增加一個新元素,此時所需的最小容量是 minCapacity = size+1
2.首先判斷底層數(shù)組 elementData 是否是空數(shù)組
如果是空數(shù)組,則更新 minCapacity 為默認容量10,
如果不是空數(shù)組,則對 minCapacity 不做變更
3.判斷所需最小容量 minCapacity 是否大于緩沖數(shù)組 elementData 的長度:
如果大于,則進行擴容 grow(),
否則不做處理
4.擴容 grow()中,首先一上來就將 elementData 的長度擴長為原來長度的1.5倍,再對擴容后的 elementData 的長度和所需最小的容量 minCapacity進行判斷
如果擴容后的 elementData 的長度還小于 minCapacity 的長度,說明還是不夠,此時就直接將minCapacity的長度賦值給elementData
否則的話直接進行下一步即可
5.最后需要對 elementData 的長度進行一個是否超過最大限度值MAX_ARRAY_SIZE判斷
如果超過最大限度值,就看看所需的最小容量minCapacity是否大于最大限度值Integer.MAX_VALUE
如果不是,就將數(shù)組的長度擴容為數(shù)組的最大限度值MAX_ARRAY_SIZE,如果是,則返回Integer.MAX_VALUE
四、場景分析
1、對于ensureExplicitCapacity()方法
1.1 add 進第 1 個元素到 ArrayList 時
當(dāng)我們要 add
進第 1 個元素到 ArrayList
時,elementData.length
為 0 (因為還是一個空的 list),因為執(zhí)行了 ensureCapacityInternal()
方法 ,所以 minCapacity
此時為 10。此時,minCapacity - elementData.length > 0
成立,所以會進入 grow(minCapacity)
方法。
1.2 當(dāng) add 第 2 個元素時
當(dāng) add 第 2 個元素時,minCapacity
為 2,此時 elementData.length(容量)
在添加第一個元素后擴容成 10 了。此時,minCapacity - elementData.length > 0
不成立,所以不會進入 (執(zhí)行)grow(minCapacity)
方法。添加第 3、4···到第 10 個元素時,依然不會執(zhí)行 grow
方法,數(shù)組容量都為 10。
1.3 直到添加第 11 個元素
minCapacity(為 11)
比 elementData.length
(為 10)要大。進入 grow
方法進行擴容。
2、對于grow() 方法
2.1 當(dāng) add 第 1 個元素時
oldCapacity
為 0,經(jīng)比較后第一個 if 判斷成立,newCapacity = minCapacity(為 10)
。但是第二個 if 判斷不會成立,即 newCapacity
不比 MAX_ARRAY_SIZE
大,則不會進入 hugeCapacity
方法。數(shù)組容量為 10,add 方法中 return true,size 增為 1。
2.2 當(dāng) add 第 11 個元素進入 grow 方法時
newCapacity
為 15,比 minCapacity(為 11)
大,第一個 if 判斷不成立。新容量沒有大于數(shù)組最大 size,不會進入 hugeCapacity
方法。數(shù)組容量擴為 15,add 方法中 return true,size 增為 11。以此類推······
五、心得體會
變量 minCapacity 理解為我們添加元素進ArrayList集合中,底層數(shù)組所需的最小容量
變量 elementData.length 理解為我們添加元素進ArrayList集合中,底層數(shù)組的最大限度容量
當(dāng)最小容量 minCapacity> 最大限度容量 elementData.length ,必定會觸發(fā)擴容機制。
我們總是頻繁地向ArrayList集合添加元素,開發(fā)人員也想到了這點,所以在ArrayList集合的擴容機制中,當(dāng)我們添加第一個元素時,直接就把minCapacity設(shè)置為10,此處可以理解為,因為我們后續(xù)要頻繁添加元素,為了不總是觸發(fā)該集合的擴容機制,便“謊稱”所需的最小容量是10,所以系統(tǒng)就直接把elementData.length設(shè)置為10
六、源碼簡易流程圖
以上就是ArrayList源碼探秘之Java動態(tài)數(shù)組的實現(xiàn)的詳細內(nèi)容,更多關(guān)于Java動態(tài)數(shù)組的資料請關(guān)注腳本之家其它相關(guān)文章!
相關(guān)文章
導(dǎo)入項目出現(xiàn)Java多個工程相互引用異常A cycle was detected in the build path o
今天小編就為大家分享一篇關(guān)于導(dǎo)入項目出現(xiàn)Java多個工程相互引用異常A cycle was detected in the build path of project的解決辦法,小編覺得內(nèi)容挺不錯的,現(xiàn)在分享給大家,具有很好的參考價值,需要的朋友一起跟隨小編來看看吧2018-12-12Java AQS中CyclicBarrier回環(huán)柵欄的使用
這篇文章主要介紹了Java中的 CyclicBarrier詳解,CyclicBarrier沒有顯示繼承哪個父類或者實現(xiàn)哪個父接口, 所有AQS和重入鎖不是通過繼承實現(xiàn)的,而是通過組合實現(xiàn)的,下文相關(guān)內(nèi)容需要的小伙伴可以參考一下2023-02-02java中堆內(nèi)存與棧內(nèi)存的知識點總結(jié)
在本篇文章里小編給大家整理的是關(guān)于java中堆內(nèi)存與棧內(nèi)存的知識點總結(jié),有需要的朋友們可以跟著學(xué)習(xí)下。2019-12-12Java HashSet(散列集),HashMap(散列映射)的簡單介紹
這篇文章主要介紹了Java HashSet(散列集),HashMap(散列映射)的簡單介紹,幫助大家更好的理解和學(xué)習(xí)Java集合框架的相關(guān)知識,感興趣的朋友可以了解下2021-01-01Java調(diào)用ChatGPT(基于SpringBoot和Vue)實現(xiàn)可連續(xù)對話和流式輸出的ChatGPT API
這篇文章主要介紹了Java調(diào)用ChatGPT(基于SpringBoot和Vue),實現(xiàn)可連續(xù)對話和流式輸出的ChatGPT API(可自定義實現(xiàn)AI助手),文中代碼示例介紹的非常詳細,感興趣的朋友可以參考下2023-04-04