前言
List、Set、HashMap作為Java中常用的集合，需要深入認(rèn)識(shí)其原理和特性。
本篇博客介紹常見的關(guān)于Java中List集合的面試問題，結(jié)合源碼分析題目背后的知識(shí)點(diǎn)。
關(guān)于的Set的博客文章如下：
- Java進(jìn)階（Set）——面試時(shí)Set常見問題解讀 & 結(jié)合源碼分析
關(guān)于HaseMap的博客文章如下：
- Java進(jìn)階（HashMap）——面試時(shí)HashMap常見問題解讀 & 結(jié)合源碼分析
- Java進(jìn)階（ConcurrentHashMap）——面試時(shí)ConcurrentHashMap常見問題解讀 & 結(jié)合源碼分析 & 多線程CAS比較并交換 初識(shí)
其他相關(guān)的List的文章合集如下：
-
手動(dòng)實(shí)現(xiàn)ArrayList & 源碼的初步理解分析 & 數(shù)組插入數(shù)據(jù)和刪除數(shù)據(jù)的問題
-
Java學(xué)數(shù)據(jù)結(jié)構(gòu)（1）——抽象數(shù)據(jù)類型ADT & 表List、棧Stack和隊(duì)列Qeue
引出
1.ArrayList如何擴(kuò)容，1.5倍；
2.ArrayList如何拷貝，深拷貝，淺拷貝；
3.ArrayList的增加或者刪除效率低，arraycopy方法；
4.指定長(zhǎng)度創(chuàng)建ArrayList對(duì)象，避免頻繁擴(kuò)容；
5.線程安全的ArrayList集合：Collections.synchronizedList；
6.LinkedList 和 ArrayList 該如何選擇：ArrayList增刪效率低，查詢效率高；LinkedList 查詢效率低，增刪效率高
7.Vector 集合和 ArrayList 區(qū)別：Vector擴(kuò)容機(jī)制為原始的2倍，線程安全；文章來源地址http://www.zghlxwxcb.cn/news/detail-740670.html
ArrayList 如何擴(kuò)容的？/ArrayList的大小是如何自動(dòng)增加的？
ArrayList初始化的時(shí)候，若沒有給定長(zhǎng)度，則默認(rèn)調(diào)用無參構(gòu)造
此處elelmentData為ArrayList底層數(shù)組，后面DEFAULTCAPACITY_EMPTY_ELEMENTDATA 為常量數(shù)組初值為空，即長(zhǎng)度為0
1.add添加第一個(gè)元素
當(dāng)執(zhí)行add方法添加第一個(gè)元素時(shí)，執(zhí)行下面的代碼
此處涉及到兩條代碼：
- ensureCapacityInternal方法內(nèi)會(huì)調(diào)用calculateCapacity方法，此處才是賦予數(shù)組長(zhǎng)度為10
ensureCapacityInternal 方法
calculateCapacity方法
private static int calculateCapacity(Object[] elementData, int minCapacity) {
//如果數(shù)組是空的
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
//返回?cái)?shù)組的容量，DEFAULT_CAPACITY=10
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
此時(shí)集合可以添加默認(rèn)的10個(gè)元素
2.添加第11個(gè)元素時(shí)
當(dāng)添加第11個(gè)元素時(shí)，ensureExplicitCapacity方法中，minCapacity為11，而原數(shù)組長(zhǎng)度為10，所以if結(jié)構(gòu)進(jìn)入grow方法-擴(kuò)容核心方法
ensureExplicitCapacity方法
grow方法-擴(kuò)容核心方法
private void grow(int minCapacity) {
// overflow-conscious code
//把舊的長(zhǎng)度賦值給oldCapacity
int oldCapacity = elementData.length;
//新的長(zhǎng)度就=舊的長(zhǎng)度*1.5
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
//按照新的長(zhǎng)度復(fù)制出一個(gè)新的數(shù)組
elementData = Arrays.copyOf(elementData, newCapacity);
}
-
oldCapacity賦值為原數(shù)組長(zhǎng)度，為10 ，newCapacity賦值為原長(zhǎng)度1.5倍，即15
-
調(diào)用復(fù)制數(shù)組方法，將之前的數(shù)組復(fù)制到新的數(shù)組中，并將需要添加的元素加到數(shù)組最后一位，完成擴(kuò)容！
如何復(fù)制某個(gè)ArrayList到另一個(gè)Arraylist中去？
重寫clone方法，ArrayList克隆
厘清概念：深淺拷貝
Java進(jìn)階（4）——結(jié)合類加載JVM的過程理解創(chuàng)建對(duì)象的幾種方式：new，反射Class，克隆clone（拷貝），序列化反序列化
淺拷貝：雖然返回一個(gè)元素一樣的ArrayList，復(fù)制的是元素的引用，即其中一個(gè)改變了元素，另一個(gè)也會(huì)跟著改變
兩個(gè)集合中間存儲(chǔ)了同一份元素的引用
例如：
深拷貝：重寫clone方法，利用迭代器iterator或遍歷集合，重新創(chuàng)建引用對(duì)象，逐個(gè)添加
例如：
復(fù)制的方法
list.clone()
clone.addALl(list);
Collections.copy(clone,list);
在索引中ArrayList的增加或者刪除某個(gè)對(duì)象的運(yùn)行過程？效率很低嗎？解釋一下為什么？
效率確實(shí)低
效率是很低的，因?yàn)锳rrayList無論是增加或者刪除某個(gè)對(duì)象，我們都要通過對(duì)數(shù)組中的元素進(jìn)行移位來實(shí)現(xiàn)。
- 增加元素時(shí)，我們要把要增加位置及以后的所有元素都往后移一位，先騰出一個(gè)空間，然后再進(jìn)行添加。
- 刪除某個(gè)元素時(shí)，我們也要把刪除位置以后的元素全部元素往前挪一位，通過覆蓋的方式來刪除。
而這種移位就需要不斷的arraycopy，是很耗時(shí)間的，所以效率自然也很低。
源碼arraycopy方法
增加元素時(shí)
刪除元素時(shí)
現(xiàn)在我有一個(gè)很大的數(shù)組需要拷貝，原數(shù)組大小是 5k，請(qǐng)問如何快速拷貝？
指定長(zhǎng)度創(chuàng)建ArrayList對(duì)象，避免頻繁擴(kuò)容
如何獲得一個(gè)線程安全的ArrayList集合？
Collections.synchronizedList
List<Object> datas = Collections.synchronizedList(new ArrayList<>());
源碼分析
從源碼可以看到集合操作都加了synchronized 關(guān)鍵字，保證了在同一時(shí)刻，數(shù)組和鏈表只會(huì)被一個(gè)線程所修改。
LinkedList 和 ArrayList 該如何選擇？
選擇原則
- ArrayList 底層為數(shù)組，在增加和刪除元素時(shí)會(huì)頻繁的調(diào)用arraycopy，所以查詢效率高，增刪效率低
- LinkedList 底層為鏈表，故查詢效率低，但增刪效率高。
LinkedList源碼node節(jié)點(diǎn)
- item 為當(dāng)前元素
- next指向下一個(gè)元素，若為最后一個(gè)則為null
- prev指向上一個(gè)元素，若為第一個(gè)則為null
Vector 集合
- vector 和 ArrayList 基本一樣
- 區(qū)別在于 vector擴(kuò)容機(jī)制為原始的2倍，ArrayList為之前的1.5倍
- vector 是線程安全的，ArrayList是非線程安全的
文章來源：http://www.zghlxwxcb.cn/news/detail-740670.html
總結(jié)
1.ArrayList如何擴(kuò)容，1.5倍；
2.ArrayList如何拷貝，深拷貝，淺拷貝；
3.ArrayList的增加或者刪除效率低，arraycopy方法；
4.指定長(zhǎng)度創(chuàng)建ArrayList對(duì)象，避免頻繁擴(kuò)容；
5.線程安全的ArrayList集合：Collections.synchronizedList；
6.LinkedList 和 ArrayList 該如何選擇：ArrayList增刪效率低，查詢效率高；LinkedList 查詢效率低，增刪效率高
7.Vector 集合和 ArrayList 區(qū)別：Vector擴(kuò)容機(jī)制為原始的2倍，線程安全；
到了這里，關(guān)于Java進(jìn)階（List）——面試時(shí)List常見問題解讀 & 結(jié)合源碼分析的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
