小小ArrayList，居然這么多坑？！
今天，我來和你說說 List 列表操作有哪些坑。
Java 的集合類包括 Map 和 Collection 兩大類。Collection 包括 List、Set 和 Queue 三個小類，其中 List 列表集合是最重要也是所有業務代碼都會用到的。今天，我們就從把數組轉換為 List 集合、對 List 進行切片操作、List 搜索的性能問題等幾個方面著手，來聊聊其中最可能遇到的一些坑。
使用 Arrays.asList 把數據轉換為 List 的三個坑
Java 8 中 Stream 流式處理的各種功能，大大減少了集合類各種操作（投影、過濾、轉換）的代碼量。所以，在業務開發中，我們常常會把原始的數組轉換為 List 類數據結構，來繼續展開各種 Stream 操作。
你可能也想到了，使用 Arrays.asList 方法可以把數組一鍵轉換為 List，但其實沒這么簡單。接下來，就讓我們看看其中的緣由，以及使用 Arrays.asList 把數組轉換為 List 的幾個坑。
在如下代碼中，我們初始化三個數字的 int[]數組，然后使用 Arrays.asList 把數組轉換為 List：
int[] arr = {1, 2, 3};
List list = Arrays.asList(arr);
log.info("list:{} size:{} class:{}", list, list.size(), list.get(0).getClass());但，這樣初始化的 List 并不是我們期望的包含 3 個數字的 List。通過日志可以發現，這個 List 包含的其實是一個 int 數組，整個 List 的元素個數是 1，元素類型是整數數組。
12:50:39.445 [main] INFO AsListApplication - list:[[I@1c53fd30] size:1 class:class [I其原因是，只能是把 int 裝箱為 Integer，不可能把 int 數組裝箱為 Integer 數組。我們知道，Arrays.asList 方法傳入的是一個泛型 T 類型可變參數，最終 int 數組整體作為了一個對象成為了泛型類型 T：
public static <T> List<T> asList(T... a) {
return new ArrayList<>(a);
}直接遍歷這樣的 List 必然會出現 Bug，修復方式有兩種，如果使用 Java8 以上版本可以使用 Arrays.stream 方法來轉換，否則可以把 int 數組聲明為包裝類型 Integer 數組：
int[] arr1 = {1, 2, 3};
List list1 = Arrays.stream(arr1).boxed().collect(Collectors.toList());
log.info("list:{} size:{} class:{}", list1, list1.size(), list1.get(0).getClass());
Integer[] arr2 = {1, 2, 3};
List list2 = Arrays.asList(arr2);
log.info("list:{} size:{} class:{}", list2, list2.size(), list2.get(0).getClass());修復后的代碼得到如下日志，可以看到 List 具有三個元素，元素類型是 Integer：
13:10:57.373 [main] INFO AsListApplication - list:[1, 2, 3] size:3 class:class java.lang.Integer可以看到第一個坑是，不能直接使用 Arrays.asList 來轉換基本類型數組。 那么，我們獲得了正確的 List，是不是就可以像普通的 List 那樣使用了呢？我們繼續往下看。
把三個字符串 1、2、3 構成的字符串數組，使用 Arrays.asList 轉換為 List 后，將原始字符串數組的第二個字符修改為 4，然后為 List 增加一個字符串 5，最后數組和 List 會是怎樣呢？
String[] arr = {"1", "2", "3"};
List list = Arrays.asList(arr);
arr[1] = "4";
try {
list.add("5");
} catch (Exception ex) {
ex.printStackTrace();
}
log.info("arr:{} list:{}", Arrays.toString(arr), list);可以看到，日志里有一個 UnsupportedOperationException，為 List 新增字符串 5 的操作失敗了，而且把原始數組的第二個元素從 2 修改為 4 后，asList 獲得的 List 中的第二個元素也被修改為 4 了：
java.lang.UnsupportedOperationException
at java.util.AbstractList.add(AbstractList.java:148)
at java.util.AbstractList.add(AbstractList.java:108)
at AsListApplication.wrong2(AsListApplication.java:41)
at AsListApplication.main(AsListApplication.java:15)
13:15:34.699 [main] INFO AsListApplication - arr:[1, 4, 3] list:[1, 4, 3]這里，又引出了兩個坑。
第二個坑，Arrays.asList 返回的 List 不支持增刪操作。 Arrays.asList 返回的 List 并不是我們期望的 java.util.ArrayList，而是 Arrays 的內部類 ArrayList。ArrayList 內部類繼承自 AbstractList 類，并沒有覆寫父類的 add 方法，而父類中 add 方法的實現，就是拋出 UnsupportedOperationException。相關源碼如下所示：
public static <T> List<T> asList(T... a) {
return new ArrayList<>(a);
}
private static class ArrayList<E> extends AbstractList<E> implements RandomAccess, java.io.Serializable {
private final E[] a;
ArrayList(E[] array) {
a = Objects.requireNonNull(array);
}
...
@Override
public E set(int index, E element) {
E oldValue = a[index];
a[index] = element;
return oldValue;
}
...
}
public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> {
...
public void add(int index, E element) {
throw new UnsupportedOperationException();
}
}第三個坑，對原始數組的修改會影響到我們獲得的那個 List。 看一下 ArrayList 的實現，可以發現 ArrayList 其實是直接使用了原始的數組。所以，我們要特別小心，把通過 Arrays.asList 獲得的 List 交給其他方法處理，很容易因為共享了數組，相互修改產生 Bug。
修復方式比較簡單，重新 new 一個 ArrayList 初始化 Arrays.asList 返回的 List 即可：
String[] arr = {"1", "2", "3"};
List list = new ArrayList(Arrays.asList(arr));
arr[1] = "4";
try {
list.add("5");
} catch (Exception ex) {
ex.printStackTrace();
}
log.info("arr:{} list:{}", Arrays.toString(arr), list);修改后的代碼實現了原始數組和 List 的“解耦”，不再相互影響。同時，因為操作的是真正的 ArrayList，add 也不再出錯：
13:34:50.829 [main] INFO AsListApplication - arr:[1, 4, 3] list:[1, 2, 3, 5]使用 List.subList 進行切片操作居然會導致 OOM？
業務開發時常常要對 List 做切片處理，即取出其中部分元素構成一個新的 List，我們通常會想到使用 List.subList 方法。但，和 Arrays.asList 的問題類似，List.subList 返回的子 List 不是一個普通的 ArrayList。這個子 List 可以認為是原始 List 的視圖，會和原始 List 相互影響。如果不注意，很可能會因此產生 OOM 問題。接下來，我們就一起分析下其中的坑。
如下代碼所示，定義一個名為 data 的靜態 List 來存放 Integer 的 List，也就是說 data 的成員本身是包含了多個數字的 List。循環 1000 次，每次都從一個具有 10 萬個 Integer 的 List 中，使用 subList 方法獲得一個只包含一個數字的子 List，并把這個子 List 加入 data 變量：
private static List<List<Integer>> data = new ArrayList<>();
private static void oom() {
for (int i = 0; i < 1000; i++) {
List<Integer> rawList = IntStream.rangeClosed(1, 100000).boxed().collect(Collectors.toList());
data.add(rawList.subList(0, 1));
}
}你可能會覺得，這個 data 變量里面最終保存的只是 1000 個具有 1 個元素的 List，不會占用很大空間，但程序運行不久就出現了 OOM：
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
at java.util.Arrays.copyOf(Arrays.java:3181)
at java.util.ArrayList.grow(ArrayList.java:265)出現 OOM 的原因是，循環中的 1000 個具有 10 萬個元素的 List 始終得不到回收，因為它始終被 subList 方法返回的 List 強引用。那么，返回的子 List 為什么會強引用原始的 List，它們又有什么關系呢？我們再繼續做實驗觀察一下這個子 List 的特性。
首先初始化一個包含數字 1 到 10 的 ArrayList，然后通過調用 subList 方法取出 2、3、4；隨后刪除這個 SubList 中的元素數字 3，并打印原始的 ArrayList；最后為原始的 ArrayList 增加一個元素數字 0，遍歷 SubList 輸出所有元素：
List<Integer> list = IntStream.rangeClosed(1, 10).boxed().collect(Collectors.toList());
List<Integer> subList = list.subList(1, 4);
System.out.println(subList);
subList.remove(1);
System.out.println(list);
list.add(0);
try {
subList.forEach(System.out::println);
} catch (Exception ex) {
ex.printStackTrace();
}代碼運行后得到如下輸出：
[2, 3, 4]
[1, 2, 4, 5, 6, 7, 8, 9, 10]
java.util.ConcurrentModificationException
at java.util.ArrayList$SubList.checkForComodification(ArrayList.java:1239)
at java.util.ArrayList$SubList.listIterator(ArrayList.java:1099)
at java.util.AbstractList.listIterator(AbstractList.java:299)
at java.util.ArrayList$SubList.iterator(ArrayList.java:1095)
at java.lang.Iterable.forEach(Iterable.java:74)可以看到兩個現象：
原始 List 中數字 3 被刪除了，說明刪除子 List 中的元素影響到了原始 List；
嘗試為原始 List 增加數字 0 之后再遍歷子 List，會出現 ConcurrentModificationException。
我們分析下 ArrayList 的源碼，看看為什么會是這樣。
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
protected transient int modCount = 0;
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
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++;
}
public List<E> subList(int fromIndex, int toIndex) {
subListRangeCheck(fromIndex, toIndex, size);
return new SubList(this, offset, fromIndex, toIndex);
}
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;
}
public E set(int index, E element) {
rangeCheck(index);
checkForComodification();
return l.set(index+offset, element);
}
public ListIterator<E> listIterator(final int index) {
checkForComodification();
...
}
private void checkForComodification() {
if (ArrayList.this.modCount != this.modCount)
throw new ConcurrentModificationException();
}
...
}
}第一，ArrayList 維護了一個叫作 modCount 的字段，表示集合結構性修改的次數。所謂結構性修改，指的是影響 List 大小的修改，所以 add 操作必然會改變 modCount 的值。
第二，分析第 21 到 24 行的 subList 方法可以看到，獲得的 List 其實是內部類 SubList，并不是普通的 ArrayList，在初始化的時候傳入了 this。
第三，分析第 26 到 39 行代碼可以發現，這個 SubList 中的 parent 字段就是原始的 List。SubList 初始化的時候，并沒有把原始 List 中的元素復制到獨立的變量中保存。我們可以認為 SubList 是原始 List 的視圖，并不是獨立的 List。雙方對元素的修改會相互影響，而且 SubList 強引用了原始的 List，所以大量保存這樣的 SubList 會導致 OOM。
第四，分析第 47 到 55 行代碼可以發現，遍歷 SubList 的時候會先獲得迭代器，比較原始 ArrayList modCount 的值和 SubList 當前 modCount 的值。獲得了 SubList 后，我們為原始 List 新增了一個元素修改了其 modCount，所以判等失敗拋出 ConcurrentModificationException 異常。
既然 SubList 相當于原始 List 的視圖，那么避免相互影響的修復方式有兩種：
一種是，不直接使用 subList 方法返回的 SubList，而是重新使用 new ArrayList，在構造方法傳入 SubList，來構建一個獨立的 ArrayList；
另一種是，對于 Java 8 使用 Stream 的 skip 和 limit API 來跳過流中的元素，以及限制流中元素的個數，同樣可以達到 SubList 切片的目的。
//方式一：
List<Integer> subList = new ArrayList<>(list.subList(1, 4));
//方式二：
List<Integer> subList = list.stream().skip(1).limit(3).collect(Collectors.toList());修復后代碼輸出如下：
[2, 3, 4]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
2
4可以看到，刪除 SubList 的元素不再影響原始 List，而對原始 List 的修改也不會再出現 List 迭代異常。
一定要讓合適的數據結構做合適的事情
在使用 List 集合類的時候，不注意使用場景也會遇見兩個常見誤區。
第一個誤區是，使用數據結構不考慮平衡時間和空間。
首先，定義一個只有一個 int 類型訂單號字段的 Order 類：
@Data
@NoArgsConstructor
@AllArgsConstructor
static class Order {
private int orderId;
}然后，定義一個包含 elementCount 和 loopCount 兩個參數的 listSearch 方法，初始化一個具有 elementCount 個訂單對象的 ArrayList，循環 loopCount 次搜索這個 ArrayList，每次隨機搜索一個訂單號：
private static Object listSearch(int elementCount, int loopCount) {
List<Order> list = IntStream.rangeClosed(1, elementCount).mapToObj(i -> new Order(i)).collect(Collectors.toList());
IntStream.rangeClosed(1, loopCount).forEach(i -> {
int search = ThreadLocalRandom.current().nextInt(elementCount);
Order result = list.stream().filter(order -> order.getOrderId() == search).findFirst().orElse(null);
Assert.assertTrue(result != null && result.getOrderId() == search);
});
return list;
}隨后，定義另一個 mapSearch 方法，從一個具有 elementCount 個元素的 Map 中循環 loopCount 次查找隨機訂單號。Map 的 Key 是訂單號，Value 是訂單對象：
private static Object mapSearch(int elementCount, int loopCount) {
Map<Integer, Order> map = IntStream.rangeClosed(1, elementCount).boxed().collect(Collectors.toMap(Function.identity(), i -> new Order(i)));
IntStream.rangeClosed(1, loopCount).forEach(i -> {
int search = ThreadLocalRandom.current().nextInt(elementCount);
Order result = map.get(search);
Assert.assertTrue(result != null && result.getOrderId() == search);
});
return map;
}我們知道，搜索 ArrayList 的時間復雜度是 O(n)，而 HashMap 的 get 操作的時間復雜度是 O(1)。所以，要對大 List 進行單值搜索的話，可以考慮使用 HashMap，其中 Key 是要搜索的值，Value 是原始對象，會比使用 ArrayList 有非常明顯的性能優勢。
如下代碼所示，對 100 萬個元素的 ArrayList 和 HashMap，分別調用 listSearch 和 mapSearch 方法進行 1000 次搜索：
int elementCount = 1000000;
int loopCount = 1000;
StopWatch stopWatch = new StopWatch();
stopWatch.start("listSearch");
Object list = listSearch(elementCount, loopCount);
System.out.println(ObjectSizeCalculator.getObjectSize(list));
stopWatch.stop();
stopWatch.start("mapSearch");
Object map = mapSearch(elementCount, loopCount);
stopWatch.stop();
System.out.println(ObjectSizeCalculator.getObjectSize(map));
System.out.println(stopWatch.prettyPrint());通過運行結果可以看到，僅僅是 1000 次搜索，listSearch 方法耗時 3.3 秒，而 mapSearch 耗時僅僅 108 毫秒。
即使我們要搜索的不是單值而是條件區間，也可以嘗試使用 HashMap 來進行“搜索性能優化”。如果你的條件區間是固定的話，可以提前把 HashMap 按照條件區間進行分組，Key 就是不同的區間。
的確，如果業務代碼中有頻繁的大 ArrayList 搜索，使用 HashMap 性能會好很多。類似，如果要對大 ArrayList 進行去重操作，也不建議使用 contains 方法，而是可以考慮使用 HashSet 進行去重。說到這里，還有一個問題，使用 HashMap 是否會犧牲空間呢？
為此，我們使用 ObjectSizeCalculator 工具打印 ArrayList 和 HashMap 的內存占用，可以看到 ArrayList 占用內存 21M，而 HashMap 占用的內存達到了 72M，是 List 的三倍多。進一步使用 MAT 工具分析堆可以再次證明，ArrayList 在內存占用上性價比很高，77% 是實際的數據（如第 1 個圖所示，16000000/20861992），而 HashMap 的“含金量”只有 22%。
所以，在應用內存吃緊的情況下，我們需要考慮是否值得使用更多的內存消耗來換取更高的性能。這里我們看到的是平衡的藝術，空間換時間，還是時間換空間，只考慮任何一個方面都是不對的。
第二個誤區是，過于迷信教科書的大 O 時間復雜度。
數據結構中要實現一個列表，有基于連續存儲的數組和基于指針串聯的鏈表兩種方式。在 Java 中，有代表性的實現是 ArrayList 和 LinkedList，前者背后的數據結構是數組，后者則是（雙向）鏈表。
在選擇數據結構的時候，我們通常會考慮每種數據結構不同操作的時間復雜度，以及使用場景兩個因素。查看這里，你可以看到數組和鏈表大 O 時間復雜度的顯著差異：
對于數組，隨機元素訪問的時間復雜度是 O(1)，元素插入操作是 O(n)；
對于鏈表，隨機元素訪問的時間復雜度是 O(n)，元素插入操作是 O(1)。
那么，在大量的元素插入、很少的隨機訪問的業務場景下，是不是就應該使用 LinkedList 呢？接下來，我們寫一段代碼測試下兩者隨機訪問和插入的性能吧。
定義四個參數一致的方法，分別對元素個數為 elementCount 的 LinkedList 和 ArrayList，循環 loopCount 次，進行隨機訪問和增加元素到隨機位置的操作：
//LinkedList訪問
private static void linkedListGet(int elementCount, int loopCount) {
List<Integer> list = IntStream.rangeClosed(1, elementCount).boxed().collect(Collectors.toCollection(LinkedList::new));
IntStream.rangeClosed(1, loopCount).forEach(i -> list.get(ThreadLocalRandom.current().nextInt(elementCount)));
}
//ArrayList訪問
private static void arrayListGet(int elementCount, int loopCount) {
List<Integer> list = IntStream.rangeClosed(1, elementCount).boxed().collect(Collectors.toCollection(ArrayList::new));
IntStream.rangeClosed(1, loopCount).forEach(i -> list.get(ThreadLocalRandom.current().nextInt(elementCount)));
}
//LinkedList插入
private static void linkedListAdd(int elementCount, int loopCount) {
List<Integer> list = IntStream.rangeClosed(1, elementCount).boxed().collect(Collectors.toCollection(LinkedList::new));
IntStream.rangeClosed(1, loopCount).forEach(i -> list.add(ThreadLocalRandom.current().nextInt(elementCount),1));
}
//ArrayList插入
private static void arrayListAdd(int elementCount, int loopCount) {
List<Integer> list = IntStream.rangeClosed(1, elementCount).boxed().collect(Collectors.toCollection(ArrayList::new));
IntStream.rangeClosed(1, loopCount).forEach(i -> list.add(ThreadLocalRandom.current().nextInt(elementCount),1));
}測試代碼如下，10 萬個元素，循環 10 萬次：
int elementCount = 100000;
int loopCount = 100000;
StopWatch stopWatch = new StopWatch();
stopWatch.start("linkedListGet");
linkedListGet(elementCount, loopCount);
stopWatch.stop();
stopWatch.start("arrayListGet");
arrayListGet(elementCount, loopCount);
stopWatch.stop();
System.out.println(stopWatch.prettyPrint());
StopWatch stopWatch2 = new StopWatch();
stopWatch2.start("linkedListAdd");
linkedListAdd(elementCount, loopCount);
stopWatch2.stop();
stopWatch2.start("arrayListAdd");
arrayListAdd(elementCount, loopCount);
stopWatch2.stop();
System.out.println(stopWatch2.prettyPrint());運行結果可能會讓你大跌眼鏡。在隨機訪問方面，我們看到了 ArrayList 的絕對優勢，耗時只有 11 毫秒，而 LinkedList 耗時 6.6 秒，這符合上面我們所說的時間復雜度；但，隨機插入操作居然也是 LinkedList 落敗，耗時 9.3 秒，ArrayList 只要 1.5 秒：
---------------------------------------------
ns % Task name
---------------------------------------------
6604199591 100% linkedListGet
011494583 000% arrayListGet
StopWatch '': running time = 10729378832 ns
---------------------------------------------
ns % Task name
---------------------------------------------
9253355484 086% linkedListAdd
1476023348 014% arrayListAdd翻看 LinkedList 源碼發現，插入操作的時間復雜度是 O(1) 的前提是，你已經有了那個要插入節點的指針。但，在實現的時候，我們需要先通過循環獲取到那個節點的 Node，然后再執行插入操作。前者也是有開銷的，不可能只考慮插入操作本身的代價：
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(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 的時間復雜度其實也是 O(n)。繼續做更多實驗的話你會發現，在各種常用場景下，LinkedList 幾乎都不能在性能上勝出 ArrayList。
諷刺的是，LinkedList 的作者約書亞 · 布洛克（Josh Bloch），在其推特上回復別人時說，雖然 LinkedList 是我寫的但我從來不用，有誰會真的用嗎？
圖片
這告訴我們，任何東西理論上和實際上是有差距的，請勿迷信教科書的理論，最好在下定論之前實際測試一下。拋開算法層面不談，由于 CPU 緩存、內存連續性等問題，鏈表這種數據結構的實現方式對性能并不友好，即使在它最擅長的場景都不一定可以發揮威力。
小結
今天，我分享了若干和 List 列表相關的錯誤案例，基本都是由“想當然”導致的。
第一，想當然認為，Arrays.asList 和 List.subList 得到的 List 是普通的、獨立的 ArrayList，在使用時出現各種奇怪的問題。
Arrays.asList 得到的是 Arrays 的內部類 ArrayList，List.subList 得到的是 ArrayList 的內部類 SubList，不能把這兩個內部類轉換為 ArrayList 使用。
Arrays.asList 直接使用了原始數組，可以認為是共享“存儲”，而且不支持增刪元素；List.subList 直接引用了原始的 List，也可以認為是共享“存儲”，而且對原始 List 直接進行結構性修改會導致 SubList 出現異常。
對 Arrays.asList 和 List.subList 容易忽略的是，新的 List 持有了原始數據的引用，可能會導致原始數據也無法 GC 的問題，最終導致 OOM。
第二，想當然認為，Arrays.asList 一定可以把所有數組轉換為正確的 List。當傳入基本類型數組的時候，List 的元素是數組本身，而不是數組中的元素。
第三，想當然認為，內存中任何集合的搜索都是很快的，結果在搜索超大 ArrayList 的時候遇到性能問題。我們考慮利用 HashMap 哈希表隨機查找的時間復雜度為 O(1) 這個特性來優化性能，不過也要考慮 HashMap 存儲空間上的代價，要平衡時間和空間。
第四，想當然認為，鏈表適合元素增刪的場景，選用 LinkedList 作為數據結構。在真實場景中讀寫增刪一般是平衡的，而且增刪不可能只是對頭尾對象進行操作，可能在 90% 的情況下都得不到性能增益，建議使用之前通過性能測試評估一下。
