ArrayList擴容原理

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

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

代碼

源碼

追進ArrayList源碼

得到：

追入：DEFAULTCAPACITY_EMPTY_ELEMENTDATA

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

總結(jié)：

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

第一次追進add源碼

得到：

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

追入：ensureCapacityInternal

得到：

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

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

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

DEFAULT_CAPACITY的值是10。

所以這行代碼的意思是：

minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);

將10重新賦值給minCapacity。

此時 minCapacity：等于10。

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

追入：ensureExplicitCapacity

此時 minCapacity =10。

第一條語句：modCount++；追進去看看：

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

然后判斷minCapacity - elementData.length是否大于 0 。因為前面說過elementData數(shù)組是空的，所以 10 - 0是大于 0的。

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

 追入：grow

注意：重點來了

此時 minCapacity = 10。

語句：int oldCapacity = elementData.length;

此時 oldCapacity = 0。

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

位運算符：>>意思是 / 2。 <<的意思是 * 2。

此時newCapacity = 0。

語句：if (newCapacity - minCapacity < 0)

newCapacity = minCapacity;

判斷 0 - 10是否小于 0 。

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

此時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ù)組。

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

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

elementData[size++] = e;

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

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

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

第二次追進add源碼

得到：

此時size = 1。

追入：ensureCapacityInternal

此時minCapacity =size + 1。

minCapacity = 2。

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

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

追入：ensureExplicitCapacity

得到：

此時modCount = 1。

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

因為此時elementData數(shù)組長度為 10。所以條件不成立，不執(zhí)行里面語句。

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

elementData[size++] = e;

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

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

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

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

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

size = 10。

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

newCapacity = 10。

modCount = 10。

第十一次追進add源碼

得到：

此時size = 10 。

追入：ensureCapacityInternal

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

追入：ensureExplicitCapacity

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

追入：grow

重點：

此時minCapacity = 11 。elementData.length = 10 。

語句：int oldCapacity = elementData.length;

此時oldCapacity = 10 。

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

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

此時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 。

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

elementData[size++] = e;

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

然后size++

此時 size = 11。

總結(jié)

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

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

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

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

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

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

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

面試時參考話術(shù)

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

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

……

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

每次擴容時，都是創(chuàng)建一個新數(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 查詢快，增刪慢。

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

LinkedList 查詢慢，增刪快。

原因：不是順序存儲，每個結(jié)點相連，一個結(jié)點中可以存儲下一個和上一個結(jié)點，這樣的話，增刪元素，只對相鄰的結(jié)點有影響，其他結(jié)點不受影響；由于沒有下標(biāo)，所以，查詢元素時，需要（從頭結(jié)點或尾結(jié)點）遍歷。

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

最新評論