ArrayList擴(kuò)容原理

ArrayList底層數(shù)據(jù)結(jié)構(gòu)是數(shù)組?。?！

數(shù)組的特點(diǎn)：固定長度，順序存儲(chǔ)，有下標(biāo)，可重復(fù)。

代碼

源碼

追進(jìn)ArrayList源碼

得到：

追入：DEFAULTCAPACITY_EMPTY_ELEMENTDATA

得到：-- 意思是：創(chuàng)建一個(gè)final修飾的Object類型的空的常量數(shù)組。

總結(jié)：

將空數(shù)組賦值給elementData這個(gè)屬性。此時(shí)elementData數(shù)組是空的。DEFAULTCAPACITY_EMPTY_ELEMENTDATA數(shù)組也是空的。

第一次追進(jìn)add源碼

得到：

• (E e)：就是你傳入的 "aa" 。
• size：現(xiàn)在等于0。

追入：ensureCapacityInternal

得到：

minCapacity：就等于 （size + 1）。--現(xiàn)在等于1。

然后利用 if判斷，前面提到過，elementData是DEFAULTCAPACITY_EMPTY_ELEMENTDATA賦值得到的，所以現(xiàn)在它們兩個(gè)相等。

條件成立，就進(jìn)入，Math.max(DEFAULT_CAPACITY, minCapacity)意思是取括號(hào)里的較大的值，咱們現(xiàn)在知道m(xù)inCapacity的值是1，所以現(xiàn)在追進(jìn)DEFAULT_CAPACITY的源碼去看看：

DEFAULT_CAPACITY的值是10。

所以這行代碼的意思是：

minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);

將10重新賦值給minCapacity。

此時(shí) minCapacity：等于10。

繼續(xù)執(zhí)行下一條語句：

追入：ensureExplicitCapacity

此時(shí) minCapacity =10。

第一條語句：modCount++；追進(jìn)去看看：

發(fā)現(xiàn) modCount =0。

然后判斷minCapacity - elementData.length是否大于 0 。因?yàn)榍懊嬲f過elementData數(shù)組是空的，所以 10 - 0是大于 0的。

條件成立，執(zhí)行g(shù)row(minCapacity);

 追入：grow

注意：重點(diǎn)來了

此時(shí) minCapacity = 10。

語句：int oldCapacity = elementData.length;

此時(shí) oldCapacity = 0。

語句：int newCapacity = oldCapacity + (oldCapacity >> 1);

位運(yùn)算符：>>意思是 / 2。 <<的意思是 * 2。

此時(shí)newCapacity = 0。

語句：if (newCapacity - minCapacity < 0)

newCapacity = minCapacity;

判斷 0 - 10是否小于 0 。

條件成立，執(zhí)行：newCapacity = minCapacity;

此時(shí)newCapacity = 10。

語句：if (newCapacity - MAX_ARRAY_SIZE > 0)

newCapacity = hugeCapacity(minCapacity);

判斷 10 -MAX_ARRAY_SIZE是否大于 0。

MAX_ARRAY_SIZE = 2147483639。

條件不成立，不執(zhí)行：newCapacity = hugeCapacity(minCapacity);

繼續(xù)往下走。

語句：elementData = Arrays.copyOf(elementData, newCapacity);

新數(shù)組 = Arrays.copyOf（舊的數(shù)組，新數(shù)組的長度）：意思是復(fù)制數(shù)組，將舊數(shù)組復(fù)制到新的數(shù)組。

此時(shí)elementData數(shù)組長度為 10。

然后返回到二、第一次追進(jìn)add源碼執(zhí)行下一條語句

elementData[size++] = e;

• 前面說過size = 0；e = "aa"；
• 所以：elementData[0] = "aa";
• 然后size++
• 此時(shí) size = 1。

第一遍追進(jìn)之后數(shù)據(jù)的改變

• size = 1。
• elementData數(shù)組長度為 10。
• newCapacity = 10。
• modCount = 1。

第二次追進(jìn)add源碼

得到：

此時(shí)size = 1。

追入：ensureCapacityInternal

此時(shí)minCapacity =size + 1。

minCapacity = 2。

判斷 elementData 和DEFAULTCAPACITY_EMPTY_ELEMENTDATA是否相等，因?yàn)榻?jīng)過第一次賦值導(dǎo)致 elementData已經(jīng)是 10了。所以條件不成立，不執(zhí)行里面的語句。

繼續(xù)執(zhí)行下一條語句。

追入：ensureExplicitCapacity

得到：

此時(shí)modCount = 1。

判斷 minCapacity -elementData.length是否大于 0 。

因?yàn)榇藭r(shí)elementData數(shù)組長度為 10。所以條件不成立，不執(zhí)行里面語句。

所以此時(shí)返回到三、第二次追進(jìn)add源碼執(zhí)行下一條語句。

elementData[size++] = e;

前面說過size = 1；e = "bb"；

• 所以：elementData[1] = "bb";
• 然后size++
• 此時(shí) size = 2。

第二遍追進(jìn)之后數(shù)據(jù)的改變

• size = 2。
• elementData數(shù)組長度為 10。
• newCapacity = 10。
• modCount = 2。

第十遍追進(jìn)之后數(shù)據(jù)的改變

size = 10。

elementData數(shù)組長度為 10。

newCapacity = 10。

modCount = 10。

第十一次追進(jìn)add源碼

得到：

此時(shí)size = 10 。

追入：ensureCapacityInternal

• 此時(shí)minCapacity =size + 1 。
• minCapacity = 11 。
• 判斷 elementData 和DEFAULTCAPACITY_EMPTY_ELEMENTDATA是否相等，因?yàn)榻?jīng)過前面賦值導(dǎo)致 elementData已經(jīng)是 10了。所以條件不成立，不執(zhí)行里面的語句。
• 繼續(xù)執(zhí)行下一條語句。

追入：ensureExplicitCapacity

• 此時(shí)modCount = 10。
• 判斷 minCapacity -elementData.length是否大于 0 。
• 因?yàn)?minCapacity = 11 。elementData數(shù)組長度為 10 。所以條件成立，執(zhí)行里面的語句。

追入：grow

重點(diǎn)：

此時(shí)minCapacity = 11 。elementData.length = 10 。

語句：int oldCapacity = elementData.length;

此時(shí)oldCapacity = 10 。

語句：int newCapacity = oldCapacity + (oldCapacity >> 1);

意思是：newCapacity = 10 + （10除以 2）

此時(shí)newCapacity = 15 。

語句：if (newCapacity - minCapacity < 0)

newCapacity = minCapacity;

判斷 15 - 11是否小于 0 。

不小于，所以不執(zhí)行里面的語句：newCapacity = minCapacity;

語句：if (newCapacity - MAX_ARRAY_SIZE > 0)

newCapacity = hugeCapacity(minCapacity);

判斷 15-MAX_ARRAY_SIZE是否大于 0。

MAX_ARRAY_SIZE = 2147483639。

條件不成立，不執(zhí)行：newCapacity = hugeCapacity(minCapacity);

繼續(xù)往下走。

語句：elementData = Arrays.copyOf(elementData, newCapacity);

意思是：新數(shù)組 =Arrays.copyOf（老數(shù)組，新數(shù)組長度）;

elementData = Arrays.copyOf(elementData,15);

所以這是后 elementData 數(shù)組長度為 15 。

然后返回到四、第十一次追進(jìn)add源碼執(zhí)行下一條語句

elementData[size++] = e;

所以：elementData[10] = "第十一次";

然后size++

此時(shí) size = 11。

總結(jié)

1、底層創(chuàng)建了一個(gè) Object[]的數(shù)組。數(shù)組名：elementData。此數(shù)組中沒有元素。

2、通過List.add 調(diào)用 grow()擴(kuò)容方法，數(shù)組長度變?yōu)?0。

3、在數(shù)組存滿之前 List.add中不會(huì)再調(diào)用grow()擴(kuò)容方法了。

4、當(dāng)?shù)谑淮未嫒霑r(shí)，List.add再次調(diào)用grow()擴(kuò)容方法。

數(shù)組長度會(huì)變?yōu)樵瓟?shù)組長度的1.5倍。

5、擴(kuò)容不是在老數(shù)組基礎(chǔ)上拼接的，而是創(chuàng)建了一個(gè)1.5倍長度的新數(shù)組。

并把老數(shù)組的元素復(fù)制到新數(shù)組。

面試時(shí)參考話術(shù)

ArrayList底層數(shù)據(jù)結(jié)構(gòu)是數(shù)組，當(dāng)創(chuàng)建ArrayList對(duì)象時(shí)，底層初始化了一個(gè)空數(shù)組，數(shù)組是Object類型，數(shù)組名是elementData。

當(dāng)?shù)谝淮翁砑釉貢r(shí)，數(shù)組長度擴(kuò)容為10。

……

當(dāng)?shù)?1次添加時(shí)，會(huì)觸發(fā)擴(kuò)容機(jī)制，其實(shí)就是調(diào)用 grow方法，擴(kuò)容為原數(shù)組長度的1.5倍。

每次擴(kuò)容時(shí)，都是創(chuàng)建一個(gè)新數(shù)組，將老數(shù)組的元素通過 Arrays工具類復(fù)制到新數(shù)組中。elementData 指向了新數(shù)組。

ArrayList和 LinkedList 區(qū)別？

ArrayList 底層數(shù)據(jù)結(jié)構(gòu) 數(shù)組。

LinkedList 底層數(shù)據(jù)結(jié)構(gòu) 鏈表。

功能上區(qū)別：

ArrayList 查詢快，增刪慢。

原因：順序存儲(chǔ)，有索引，可以根據(jù)索引，直接定位到元素，所以查詢快；由于是順序存儲(chǔ)，新增或者刪除，都會(huì)對(duì)后續(xù)的元素有影響。

LinkedList 查詢慢，增刪快。

原因：不是順序存儲(chǔ)，每個(gè)結(jié)點(diǎn)相連，一個(gè)結(jié)點(diǎn)中可以存儲(chǔ)下一個(gè)和上一個(gè)結(jié)點(diǎn)，這樣的話，增刪元素，只對(duì)相鄰的結(jié)點(diǎn)有影響，其他結(jié)點(diǎn)不受影響；由于沒有下標(biāo)，所以，查詢?cè)貢r(shí)，需要（從頭結(jié)點(diǎn)或尾結(jié)點(diǎn)）遍歷。

以上為個(gè)人經(jīng)驗(yàn)，希望能給大家一個(gè)參考，也希望大家多多支持腳本之家。

最新評(píng)論