滿地坑！細(xì)數(shù)List的10個(gè)坑！
1. Arrays.asList轉(zhuǎn)換基本類型數(shù)組的坑
在實(shí)際的業(yè)務(wù)開(kāi)發(fā)中，我們通常會(huì)進(jìn)行數(shù)組轉(zhuǎn)List的操作，通常我們會(huì)使用Arrays.asList來(lái)進(jìn)行轉(zhuǎn)換
但是在轉(zhuǎn)換基本類型的數(shù)組的時(shí)候，卻出現(xiàn)轉(zhuǎn)換的結(jié)果和我們想象的不一致。
上代碼
int[] arr = {1, 2, 3};
List list = Arrays.asList(arr);
System.out.println(list.size());
// 1
實(shí)際上，我們想要轉(zhuǎn)成的List應(yīng)該是有三個(gè)對(duì)象而現(xiàn)在只有一個(gè)
public static List asList(T... a) {
return new ArrayList<>(a);
}
可以觀察到 asList方法 接收的是一個(gè)泛型T類型的參數(shù)，T繼承Object對(duì)象
所以通過(guò)斷點(diǎn)我們可以看到把 int數(shù)組 整體作為一個(gè)對(duì)象,返回了一個(gè) List<int[]>
那我們?cè)撊绾谓鉀Q呢？
方案一：Java8以上，利用Arrays.stream(arr).boxed()將裝箱為Integer數(shù)組
List collect = Arrays.stream(arr).boxed().collect(Collectors.toList()); System.out.println(collect.size());
System.out.println(collect.get(0).getClass());
// 3
// class java.lang.Integer
方案二：聲明數(shù)組的時(shí)候，聲明類型改為包裝類型
Integer[] integerArr = {1, 2, 3};
List integerList = Arrays.asList(integerArr);
System.out.println(integerList.size()); System.out.println(integerList.get(0).getClass());
// 3
// class java.lang.Integer
2. Arrays.asList返回的List不支持增刪操作
我們將數(shù)組對(duì)象轉(zhuǎn)成List數(shù)據(jù)結(jié)構(gòu)之后，竟然不能進(jìn)行增刪操作了
private static void asListAdd(){
String[] arr = {"1", "2", "3"};
List<String> strings = new ArrayList<>(Arrays.asList(arr));
arr[2] = "4";
System.out.println(strings.toString());
Iterator<String> iterator = strings.iterator();
while (iterator.hasNext()){
if ("4".equals(iterator.next())){
iterator.remove();
}
}
strings.forEach(val ->{
strings.remove("4");
strings.add("3");
});
System.out.println(Arrays.asList(arr).toString());
}
[1, 2, 4]
Exception in thread "main" java.lang.UnsupportedOperationException at java.util.AbstractList.remove(AbstractList.java:161) at java.util.AbstractList$Itr.remove(AbstractList.java:374) at java.util.AbstractCollection.remove(AbstractCollection.java:293) at JavaBase.List.AsListTest.lambda$asListAdd$0(AsListTest.java:47) at java.util.Arrays$ArrayList.forEach(Arrays.java:3880) at JavaBase.List.AsListTest.asListAdd(AsListTest.java:46) at JavaBase.List.AsListTest.main(AsListTest.java:20)
初始化一個(gè)字符串?dāng)?shù)組，將字符串?dāng)?shù)組轉(zhuǎn)換為 List，在遍歷List的時(shí)候進(jìn)行移除和新增的操作
拋出異常信息UnsupportedOperationException。
根據(jù)異常信息java.lang.UnsupportedOperationException，我們看到他是從AbstractList里面出來(lái)的，讓我們進(jìn)入源碼一看究竟
我們?cè)谑裁磿r(shí)候調(diào)用到了這個(gè) AbstractList 呢？
其實(shí) Arrays.asList(arr) 返回的 ArrayList 不是 java.util.ArrayList，而是 Arrays的內(nèi)部類
private static class ArrayList<E> extends AbstractList<E>
implements RandomAccess, java.io.Serializable{
private static final long serialVersionUID = -2764017481108945198L;
private final E[] a;
ArrayList(E[] array) {
a = Objects.requireNonNull(array);
}
@Override
public E get(int index) {}
@Override
public E set(int index, E element) {...}
...
}
public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> {
public boolean add(E e) {
add(size(), e);
return true;
}
public void add(int index, E element) {
throw new UnsupportedOperationException();
}
public E remove(int index) {
throw new UnsupportedOperationException();
}
}
他是沒(méi)有實(shí)現(xiàn) AbstractList 中的 add() 和 remove() 方法,這里就很清晰了為什么不支持新增和刪除，因?yàn)楦緵](méi)有實(shí)現(xiàn)。
3. 對(duì)原始數(shù)組的修改會(huì)影響到我們獲得的那個(gè)List
一不小心修改了父List，卻影響到了子List，在業(yè)務(wù)代碼中，這會(huì)導(dǎo)致產(chǎn)生的數(shù)據(jù)發(fā)生變化，嚴(yán)重的話會(huì)造成影響較大的生產(chǎn)問(wèn)題。
第二個(gè)坑的源碼中，完成字符串?dāng)?shù)組轉(zhuǎn)換為L(zhǎng)ist之后，
我們將字符串?dāng)?shù)組的第三個(gè)對(duì)象的值修改為4，但是很奇怪在打印List的時(shí)候，發(fā)現(xiàn)List也發(fā)生了變化。
public static <T> List<T> asList(T... a) {
return new ArrayList<>(a);
}
ArrayList(E[] array) {
a = Objects.requireNonNull(array);
}
asList中創(chuàng)建了 ArrayList，但是他直接引用了原本的數(shù)組對(duì)象
所以只要原本的數(shù)組對(duì)象一發(fā)生變化，List也跟著變化
所以在使用到引用的時(shí)候，我們需要特別的注意。
解決方案：
重新new一個(gè)新的 ArrayList 來(lái)裝返回的 List
List strings = new ArrayList<>(Arrays.asList(arr));
4. java.util.ArrayList如果不正確操作也不支持增刪操作
在第二個(gè)坑的時(shí)候，我們說(shuō)到了 Arrays.asList 返回的 List 不支持增刪操作，
是因?yàn)樗淖约簩?shí)現(xiàn)了一個(gè)內(nèi)部類 ArrayList，這個(gè)內(nèi)部類繼承了 AbstractList 沒(méi)有實(shí)現(xiàn) add() 和 remove() 方法導(dǎo)致操作失敗。
但是第三個(gè)坑的時(shí)候，我們利用 java.util.ArrayList 包裝了返回的 List，進(jìn)行增刪操作還是會(huì)失敗，那是為什么呢？
刪除方法邏輯：
在foreach中操作增刪，因?yàn)橐驗(yàn)?modCount 會(huì)被修改，與第一步保存的數(shù)組修改次數(shù)不一致，拋出異常 ConcurrentModificationException
在正確操作是什么？我總結(jié)了四種方式
5. ArrayList中的 subList 強(qiáng)轉(zhuǎn) ArrayList 導(dǎo)致異常
阿里《Java開(kāi)發(fā)手冊(cè)》上提過(guò)
★[強(qiáng)制] ArrayList的sublist結(jié)果不可強(qiáng)轉(zhuǎn)成ArrayList,否則會(huì)拋出ClassCastException
異常，即java.util.RandomAccesSubList cannot be cast to java. util.ArrayList.
說(shuō)明: subList 返回的是ArrayList 的內(nèi)部類SubList, 并不是ArrayList ，而是
ArrayList的一個(gè)視圖，対于SubList子列表的所有操作最終會(huì)反映到原列表上。
”
private static void subListTest(){
List<String> names = new ArrayList<String>() {{
add("one");
add("two");
add("three");
}};
ArrayList strings = (ArrayList) names.subList(0, 1);
System.out.println(strings.toString());
}
Exception in thread "main" java.lang.ClassCastException: java.util.ArrayList$SubList cannot be cast to java.util.ArrayList
我猜問(wèn)題是有八九就是出現(xiàn)在subList這個(gè)方法上了
private class SubList extends AbstractList<E> implements RandomAccess {
private final AbstractList<E> parent;
private final int parentOffset;
private final int offset;
int size;
SubList(AbstractList<E> parent,
int offset, int fromIndex, int toIndex) {
this.parent = parent;
this.parentOffset = fromIndex;
this.offset = offset + fromIndex;
this.size = toIndex - fromIndex;
this.modCount = ArrayList.this.modCount;
}
}
其實(shí) SubList 是一個(gè)繼承 AbstractList 的內(nèi)部類，在 SubList 的構(gòu)建函數(shù)中的將 List 中的部分屬性直接賦予給自己
SubList 沒(méi)有創(chuàng)建一個(gè)新的 List，而是直接引用了原來(lái)的 List(this.parent = parent)，指定了元素的范圍
所以 subList 方法不能直接轉(zhuǎn)成 ArrayList，他只是ArrayList的內(nèi)部類，沒(méi)有其他的關(guān)系
因?yàn)槭且玫年P(guān)系，所以在這里也需要特別的注意，如果對(duì)原來(lái)的List進(jìn)行修改，會(huì)對(duì)產(chǎn)生的 subList結(jié)果產(chǎn)生影響。
List<String> names = new ArrayList<String>() {{
add("one");
add("two");
add("three");
}};
List strings = names.subList(0, 1);
strings.add(0, "ongChange");
System.out.println(strings.toString());
System.out.println(names.toString());
[ongChange, one]
[ongChange, one, two, three]
對(duì)subList產(chǎn)生的List做出結(jié)構(gòu)型修改，操作會(huì)反應(yīng)到原來(lái)的List上，ongChange也添加到了names中
如果修改原來(lái)的List則會(huì)拋出異常ConcurrentModificationException
List<String> names = new ArrayList<String>() {{
add("one");
add("two");
add("three");
}};
List strings = names.subList(0, 1);
names.add("four");
System.out.println(strings.toString());
System.out.println(names.toString());
Exception in thread "main" java.util.ConcurrentModificationException
原因：
subList的時(shí)候記錄this.modCount為3
原來(lái)的List插入了一個(gè)新元素，導(dǎo)致this.modCount不第一次保存的不一致則拋出異常
解決方案：在操作SubList的時(shí)候，new一個(gè)新的ArrayList來(lái)接收創(chuàng)建subList結(jié)果的拷貝
List strings = new ArrayList(names.subList(0, 1));
6. ArrayList中的subList切片造成OOM
在業(yè)務(wù)開(kāi)發(fā)中的時(shí)候，他們經(jīng)常通過(guò)subList來(lái)獲取所需要的那部分?jǐn)?shù)據(jù)
在上面的例子中，我們知道了subList所產(chǎn)生的List，其實(shí)是對(duì)原來(lái)List對(duì)象的引用
這個(gè)產(chǎn)生的List只是原來(lái)List對(duì)象的視圖，也就是說(shuō)雖然值切片獲取了一小段數(shù)據(jù)，但是原來(lái)的List對(duì)象卻得不到回收，這個(gè)原來(lái)的List對(duì)象可能是一個(gè)很大的對(duì)象
為了方便我們測(cè)試，將vm調(diào)整一下 -Xms20m -Xmx40m
private static void subListOomTest(){
IntStream.range(0, 1000).forEach(i ->{
List<Integer> collect = IntStream.range(0, 100000).boxed().collect(Collectors.toList());
data.add(collect.subList(0, 1));
});
}}
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
出現(xiàn)OOM的原因，循環(huán)1000次創(chuàng)建了1000個(gè)具有10萬(wàn)個(gè)元素的List
因?yàn)槭冀K被collect.subList(0, 1)強(qiáng)引用，得不到回收
解決方式：
在subList方法返回SubList，重新使用new ArrayList，來(lái)構(gòu)建一個(gè)獨(dú)立的ArrayList
List list = new ArrayList<>(collect.subList(0, 1));
利用Java8的Stream中的skip和limit來(lái)達(dá)到切片的目的
List list = collect.stream().skip(0).limit(1).collect(Collectors.toList());
在這里我們可以看到，只要用一個(gè)新的容器來(lái)裝結(jié)果，就可以切斷與原始List的關(guān)系
7. LinkedList的插入速度不一定比ArrayList快
學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的時(shí)候，我們就已經(jīng)得出了結(jié)論
●對(duì)于數(shù)組，隨機(jī)元素訪問(wèn)的時(shí)間復(fù)雜度是0(1)， 元素插入操作是O(n);
●對(duì)于鏈表，隨機(jī)元素訪問(wèn)的時(shí)間復(fù)雜度是O(n), 元素插入操作是0(1).
元素插入對(duì)于鏈表來(lái)說(shuō)應(yīng)該是他的優(yōu)勢(shì)
但是他就一定比數(shù)組快? 我們執(zhí)行插入1000w次的操作
private static void test(){
StopWatch stopWatch = new StopWatch();
int elementCount = 100000;
stopWatch.start("ArrayList add");
List<Integer> arrayList = IntStream.rangeClosed(1, elementCount).boxed().collect(Collectors.toCollection(ArrayList::new));
// ArrayList插入數(shù)據(jù)
IntStream.rangeClosed(0, elementCount).forEach(i ->arrayList.add(ThreadLocalRandom.current().nextInt(elementCount), 1));
stopWatch.stop();
stopWatch.start("linkedList add");
List<Integer> linkedList = IntStream.rangeClosed(1, elementCount).boxed().collect(Collectors.toCollection(LinkedList::new));
// ArrayList插入數(shù)據(jù)
IntStream.rangeClosed(0, elementCount).forEach(i -> linkedList.add(ThreadLocalRandom.current().nextInt(elementCount), 1));
stopWatch.stop();
System.out.println(stopWatch.prettyPrint());
}
StopWatch '': running time = 44507882 ns
---------------------------------------------
ns % Task name
---------------------------------------------
043836412 098% elementCount 100 ArrayList add
000671470 002% elementCount 100 linkedList add
StopWatch '': running time = 196325261 ns
---------------------------------------------
ns % Task name
---------------------------------------------
053848980 027% elementCount 10000 ArrayList add
142476281 073% elementCount 10000 linkedList add
StopWatch '': running time = 26384216979 ns
---------------------------------------------
ns % Task name
---------------------------------------------
978501580 004% elementCount 100000 ArrayList add
25405715399 096% elementCount 100000 linkedList add
看到在執(zhí)行插入1萬(wàn)、10完次操作的時(shí)候，LinkedList的插入操作時(shí)間是 ArrayList的兩倍以上
那問(wèn)題主要就是出現(xiàn)在linkedList的 add()方法上
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
/**
* Returns the (non-null) Node at the specified element index.
*/
Node<E> node(int index) {
// assert isElementIndex(index);
if(index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
linkedList的 add()方法主要邏輯
通過(guò)遍歷找到那個(gè)節(jié)點(diǎn)的Node 執(zhí)行插入操作
ArrayList的 add()方法
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
復(fù)制代碼
計(jì)算最小容量 最小容量大于數(shù)組對(duì)象，則進(jìn)行擴(kuò)容 進(jìn)行數(shù)組復(fù)制,根據(jù)插入的index將數(shù)組向后移動(dòng)一位 最后在空位上插入新值
根據(jù)試驗(yàn)的測(cè)試，我們得出了在實(shí)際的隨機(jī)插入中，LinkedList并沒(méi)有比ArrayList的速度快
所以在實(shí)際的使用中，如果涉及到頭尾對(duì)象的操作，可以使用LinkedList數(shù)據(jù)結(jié)構(gòu)來(lái)進(jìn)行增刪的操作，發(fā)揮LinkedList的優(yōu)勢(shì)
最好再進(jìn)行實(shí)際的性能測(cè)試評(píng)估，來(lái)得到最合適的數(shù)據(jù)結(jié)構(gòu)。
8. CopyOnWriteArrayList內(nèi)存占用過(guò)多
CopyOnWrite，顧名思義就是寫的時(shí)候會(huì)將共享變量新復(fù)制一份出來(lái)，這樣做的好處是讀操作完全無(wú)鎖。
CopyOnWriteArrayList的add()方法
public boolean add(E e) {
// 獲取獨(dú)占鎖
final ReentrantLock lock = this.lock;
lock.lock();
try {
// 獲取array
Object[] elements = getArray();
// 復(fù)制array到新數(shù)組，添加元素到新數(shù)組
int len = elements.length;
Object[] newElements = Arrays.copyOf(elements, len + 1);
newElements[len] = e;
// 替換數(shù)組
setArray(newElements);
return true;
} finally {
// 釋放鎖
lock.unlock();
}
}
CopyOnWriteArrayList 內(nèi)部維護(hù)了一個(gè)數(shù)組，成員變量 array 就指向這個(gè)內(nèi)部數(shù)組，所有的讀操作都是基于新的array對(duì)象進(jìn)行的。
因?yàn)樯狭霜?dú)占鎖，所以如果多個(gè)線程調(diào)用add()方法只有一個(gè)線程會(huì)獲得到該鎖，其他線程被阻塞，知道鎖被釋放， 由于加了鎖，所以整個(gè)操作的過(guò)程是原子性操作
CopyOnWriteArrayList 會(huì)將 新的array復(fù)制一份，然后在新復(fù)制處理的數(shù)組上執(zhí)行增加元素的操作，執(zhí)行完之后再將復(fù)制的結(jié)果指向這個(gè)新的數(shù)組。
由于每次寫入的時(shí)候都會(huì)對(duì)數(shù)組對(duì)象進(jìn)行復(fù)制，復(fù)制過(guò)程不僅會(huì)占用雙倍內(nèi)存，還需要消耗 CPU 等資源，所以當(dāng)列表中的元素比較少的時(shí)候，這對(duì)內(nèi)存和 GC 并沒(méi)有多大影響，但是當(dāng)列表保存了大量元素的時(shí)候，
對(duì) CopyOnWriteArrayList 每一次修改，都會(huì)重新創(chuàng)建一個(gè)大對(duì)象，并且原來(lái)的大對(duì)象也需要回收，這都可能會(huì)觸發(fā) GC，如果超過(guò)老年代的大小則容易觸發(fā)Full GC，引起應(yīng)用程序長(zhǎng)時(shí)間停頓。
9. CopyOnWriteArrayList是弱一致性的
public Iterator<E> iterator() {
return new COWIterator<E>(getArray(), 0);
}
static final class COWIterator<E> implements ListIterator<E> {
/** Snapshot of the array */
private final Object[] snapshot;
/** Index of element to be returned by subsequent call to next. */
private int cursor;
private COWIterator(Object[] elements, int initialCursor) {
cursor = initialCursor;
snapshot = elements;
}
public boolean hasNext() {
return cursor < snapshot.length;
}
public boolean hasPrevious() {
return cursor > 0;
}
@SuppressWarnings("unchecked")
public E next() {
if (! hasNext())
throw new NoSuchElementException();
return (E) snapshot[cursor++];
}
調(diào)用iterator方法獲取迭代器返回一個(gè)COWIterator對(duì)象
COWIterator的構(gòu)造器里主要是 保存了當(dāng)前的list對(duì)象的內(nèi)容和遍歷list時(shí)數(shù)據(jù)的下標(biāo)。
snapshot是list的快照信息，因?yàn)镃opyOnWriteArrayList的讀寫策略中都會(huì)使用getArray()來(lái)獲取一個(gè)快照信息，生成一個(gè)新的數(shù)組。
所以在使用該迭代器元素時(shí)，其他線程對(duì)該lsit操作是不可見(jiàn)的，因?yàn)椴僮鞯氖莾蓚€(gè)不同的數(shù)組所以造成弱一致性。
private static void CopyOnWriteArrayListTest(){
CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList();
list.add("test1");
list.add("test2");
list.add("test3");
list.add("test4");
Thread thread = new Thread(() -> {
System.out.println(">>>> start");
list.add(1, "replaceTest");
list.remove(2);
});
// 在啟動(dòng)線程前獲取迭代器
Iterator<String> iterator = list.iterator();
thread.start();
try {
// 等待線程執(zhí)行完畢
thread.join();
} catch (InterruptedException e) {
e.printStackTrace();
}
while (iterator.hasNext()){
System.out.println(iterator.next());
}
}
>>>> start
test1
test2
test3
test4
上面的demo中在啟動(dòng)線程前獲取到了原來(lái)list的迭代器，
在之后啟動(dòng)新建一個(gè)線程，在線程里面修改了第一個(gè)元素的值，移除了第二個(gè)元素
在執(zhí)行完子線程之后，遍歷了迭代器的元素，發(fā)現(xiàn)子線程里面操作的一個(gè)都沒(méi)有生效，這里提現(xiàn)了迭代器弱一致性。
10. CopyOnWriteArrayList的迭代器不支持增刪改
private static void CopyOnWriteArrayListTest(){
CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<>();
list.add("test1");
list.add("test2");
list.add("test3");
list.add("test4");
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()){
if ("test1".equals(iterator.next())){
iterator.remove();
}
}
System.out.println(list.toString());
}
Exception in thread "main" java.lang.UnsupportedOperationException
at java.util.concurrent.CopyOnWriteArrayList$COWIterator.remove(CopyOnWriteArrayList.java:1178)
CopyOnWriteArrayList 迭代器是只讀的，不支持增刪操作
CopyOnWriteArrayList迭代器中的 remove()和 add()方法，沒(méi)有支持增刪而是直接拋出了異常
因?yàn)榈鞅闅v的僅僅是一個(gè)快照，而對(duì)快照進(jìn)行增刪改是沒(méi)有意義的。
/**
* Not supported. Always throws UnsupportedOperationException.
* @throws UnsupportedOperationException always; {@code remove}
* is not supported by this iterator.
*/
public void remove() {
throw new UnsupportedOperationException();
}
/**
* Not supported. Always throws UnsupportedOperationException.
* @throws UnsupportedOperationException always; {@code set}
* is not supported by this iterator.
*/
public void set(E e) {
throw new UnsupportedOperationException();
}
/**
* Not supported. Always throws UnsupportedOperationException.
* @throws UnsupportedOperationException always; {@code add}
* is not supported by this iterator.
*/
public void add(E e) {
throw new UnsupportedOperationException();
}
總結(jié)
由于篇幅的限制，我們只對(duì)一些在業(yè)務(wù)開(kāi)發(fā)中常見(jiàn)的關(guān)鍵點(diǎn)進(jìn)行梳理和介紹
在實(shí)際的工作中，我們不單單是要清除不同類型容器的特性，還要選擇適合的容器才能做到事半功倍。
我們主要介紹了Arrays.asList轉(zhuǎn)換過(guò)程中的一些坑，以及因?yàn)椴僮鞑划?dāng)造成的OOM和異常，
到最后介紹了線程安全類CopyOnWriteArrayList的一些坑，讓我們認(rèn)識(shí)到在豐富的API下藏著許多的陷阱。
在使用的過(guò)程中，需要更加充分的考慮避免這些隱患的發(fā)生。
最后一張思維導(dǎo)圖來(lái)回顧一下~
來(lái)源：juejin.cn/post/7143266514722881544
歡迎關(guān)注“Java引導(dǎo)者”，我們分享最有價(jià)值的Java的干貨文章，助力您成為有思想的Java開(kāi)發(fā)工程師！