6月iOS設(shè)備好評(píng)榜：第一蟬聯(lián)榜首近一年
作為安兔兔各種榜單里變化最小的那個(gè)，2023年6月的iOS好評(píng)榜和上個(gè)月相比沒有任何排名上的變化，僅僅是部分設(shè)備好評(píng)率的下降，長(zhǎng)年累月的用戶評(píng)價(jià)和逐漸退出市場(chǎng)的老款機(jī)器讓這
今天，我來(lái)和你說(shuō)說(shuō) List 列表操作有哪些坑。
Java 的集合類包括 Map 和 Collection 兩大類。Collection 包括 List、Set 和 Queue 三個(gè)小類，其中 List 列表集合是最重要也是所有業(yè)務(wù)代碼都會(huì)用到的。今天，我們就從把數(shù)組轉(zhuǎn)換為 List 集合、對(duì) List 進(jìn)行切片操作、List 搜索的性能問(wèn)題等幾個(gè)方面著手，來(lái)聊聊其中最可能遇到的一些坑。
Java 8 中 Stream 流式處理的各種功能，大大減少了集合類各種操作（投影、過(guò)濾、轉(zhuǎn)換）的代碼量。所以，在業(yè)務(wù)開發(fā)中，我們常常會(huì)把原始的數(shù)組轉(zhuǎn)換為 List 類數(shù)據(jù)結(jié)構(gòu)，來(lái)繼續(xù)展開各種 Stream 操作。
你可能也想到了，使用 Arrays.asList 方法可以把數(shù)組一鍵轉(zhuǎn)換為 List，但其實(shí)沒這么簡(jiǎn)單。接下來(lái)，就讓我們看看其中的緣由，以及使用 Arrays.asList 把數(shù)組轉(zhuǎn)換為 List 的幾個(gè)坑。
在如下代碼中，我們初始化三個(gè)數(shù)字的 int[]數(shù)組，然后使用 Arrays.asList 把數(shù)組轉(zhuǎn)換為 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 個(gè)數(shù)字的 List。通過(guò)日志可以發(fā)現(xiàn)，這個(gè) List 包含的其實(shí)是一個(gè) int 數(shù)組，整個(gè) List 的元素個(gè)數(shù)是 1，元素類型是整數(shù)數(shù)組。
12:50:39.445 [main] INFO AsListApplication - list:[[I@1c53fd30] size:1 class:class [I其原因是，只能是把 int 裝箱為 Integer，不可能把 int 數(shù)組裝箱為 Integer 數(shù)組。我們知道，Arrays.asList 方法傳入的是一個(gè)泛型 T 類型可變參數(shù)，最終 int 數(shù)組整體作為了一個(gè)對(duì)象成為了泛型類型 T：
public static <T> List<T> asList(T... a) { return new ArrayList<>(a);}直接遍歷這樣的 List 必然會(huì)出現(xiàn) Bug，修復(fù)方式有兩種，如果使用 Java8 以上版本可以使用 Arrays.stream 方法來(lái)轉(zhuǎn)換，否則可以把 int 數(shù)組聲明為包裝類型 Integer 數(shù)組：
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());修復(fù)后的代碼得到如下日志，可以看到 List 具有三個(gè)元素，元素類型是 Integer：
13:10:57.373 [main] INFO AsListApplication - list:[1, 2, 3] size:3 class:class java.lang.Integer可以看到第一個(gè)坑是，不能直接使用 Arrays.asList 來(lái)轉(zhuǎn)換基本類型數(shù)組。 那么，我們獲得了正確的 List，是不是就可以像普通的 List 那樣使用了呢？我們繼續(xù)往下看。
把三個(gè)字符串 1、2、3 構(gòu)成的字符串?dāng)?shù)組，使用 Arrays.asList 轉(zhuǎn)換為 List 后，將原始字符串?dāng)?shù)組的第二個(gè)字符修改為 4，然后為 List 增加一個(gè)字符串 5，最后數(shù)組和 List 會(huì)是怎樣呢？
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);可以看到，日志里有一個(gè) UnsupportedOperationException，為 List 新增字符串 5 的操作失敗了，而且把原始數(shù)組的第二個(gè)元素從 2 修改為 4 后，asList 獲得的 List 中的第二個(gè)元素也被修改為 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]這里，又引出了兩個(gè)坑。
第二個(gè)坑，Arrays.asList 返回的 List 不支持增刪操作。 Arrays.asList 返回的 List 并不是我們期望的 java.util.ArrayList，而是 Arrays 的內(nèi)部類 ArrayList。ArrayList 內(nèi)部類繼承自 AbstractList 類，并沒有覆寫父類的 add 方法，而父類中 add 方法的實(shí)現(xiàn)，就是拋出 UnsupportedOperationException。相關(guān)源碼如下所示：
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(); }}第三個(gè)坑，對(duì)原始數(shù)組的修改會(huì)影響到我們獲得的那個(gè) List。 看一下 ArrayList 的實(shí)現(xiàn)，可以發(fā)現(xiàn) ArrayList 其實(shí)是直接使用了原始的數(shù)組。所以，我們要特別小心，把通過(guò) Arrays.asList 獲得的 List 交給其他方法處理，很容易因?yàn)楣蚕砹藬?shù)組，相互修改產(chǎn)生 Bug。
修復(fù)方式比較簡(jiǎn)單，重新 new 一個(gè) 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);修改后的代碼實(shí)現(xiàn)了原始數(shù)組和 List 的“解耦”，不再相互影響。同時(shí)，因?yàn)椴僮鞯氖钦嬲?ArrayList，add 也不再出錯(cuò)：
13:34:50.829 [main] INFO AsListApplication - arr:[1, 4, 3] list:[1, 2, 3, 5]業(yè)務(wù)開發(fā)時(shí)常常要對(duì) List 做切片處理，即取出其中部分元素構(gòu)成一個(gè)新的 List，我們通常會(huì)想到使用 List.subList 方法。但，和 Arrays.asList 的問(wèn)題類似，List.subList 返回的子 List 不是一個(gè)普通的 ArrayList。這個(gè)子 List 可以認(rèn)為是原始 List 的視圖，會(huì)和原始 List 相互影響。如果不注意，很可能會(huì)因此產(chǎn)生 OOM 問(wèn)題。接下來(lái)，我們就一起分析下其中的坑。
如下代碼所示，定義一個(gè)名為 data 的靜態(tài) List 來(lái)存放 Integer 的 List，也就是說(shuō) data 的成員本身是包含了多個(gè)數(shù)字的 List。循環(huán) 1000 次，每次都從一個(gè)具有 10 萬(wàn)個(gè) Integer 的 List 中，使用 subList 方法獲得一個(gè)只包含一個(gè)數(shù)字的子 List，并把這個(gè)子 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)); }}你可能會(huì)覺得，這個(gè) data 變量里面最終保存的只是 1000 個(gè)具有 1 個(gè)元素的 List，不會(huì)占用很大空間，但程序運(yùn)行不久就出現(xiàn)了 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)出現(xiàn) OOM 的原因是，循環(huán)中的 1000 個(gè)具有 10 萬(wàn)個(gè)元素的 List 始終得不到回收，因?yàn)樗冀K被 subList 方法返回的 List 強(qiáng)引用。那么，返回的子 List 為什么會(huì)強(qiáng)引用原始的 List，它們又有什么關(guān)系呢？我們?cè)倮^續(xù)做實(shí)驗(yàn)觀察一下這個(gè)子 List 的特性。
首先初始化一個(gè)包含數(shù)字 1 到 10 的 ArrayList，然后通過(guò)調(diào)用 subList 方法取出 2、3、4；隨后刪除這個(gè) SubList 中的元素?cái)?shù)字 3，并打印原始的 ArrayList；最后為原始的 ArrayList 增加一個(gè)元素?cái)?shù)字 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();}代碼運(yùn)行后得到如下輸出：
[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)可以看到兩個(gè)現(xiàn)象：
原始 List 中數(shù)字 3 被刪除了，說(shuō)明刪除子 List 中的元素影響到了原始 List；
嘗試為原始 List 增加數(shù)字 0 之后再遍歷子 List，會(huì)出現(xiàn) ConcurrentModificationException。
我們分析下 ArrayList 的源碼，看看為什么會(huì)是這樣。
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 維護(hù)了一個(gè)叫作 modCount 的字段，表示集合結(jié)構(gòu)性修改的次數(shù)。所謂結(jié)構(gòu)性修改，指的是影響 List 大小的修改，所以 add 操作必然會(huì)改變 modCount 的值。
第二，分析第 21 到 24 行的 subList 方法可以看到，獲得的 List 其實(shí)是內(nèi)部類 SubList，并不是普通的 ArrayList，在初始化的時(shí)候傳入了 this。
第三，分析第 26 到 39 行代碼可以發(fā)現(xiàn)，這個(gè) SubList 中的 parent 字段就是原始的 List。SubList 初始化的時(shí)候，并沒有把原始 List 中的元素復(fù)制到獨(dú)立的變量中保存。我們可以認(rèn)為 SubList 是原始 List 的視圖，并不是獨(dú)立的 List。雙方對(duì)元素的修改會(huì)相互影響，而且 SubList 強(qiáng)引用了原始的 List，所以大量保存這樣的 SubList 會(huì)導(dǎo)致 OOM。
第四，分析第 47 到 55 行代碼可以發(fā)現(xiàn)，遍歷 SubList 的時(shí)候會(huì)先獲得迭代器，比較原始 ArrayList modCount 的值和 SubList 當(dāng)前 modCount 的值。獲得了 SubList 后，我們?yōu)樵?List 新增了一個(gè)元素修改了其 modCount，所以判等失敗拋出 ConcurrentModificationException 異常。
既然 SubList 相當(dāng)于原始 List 的視圖，那么避免相互影響的修復(fù)方式有兩種：
一種是，不直接使用 subList 方法返回的 SubList，而是重新使用 new ArrayList，在構(gòu)造方法傳入 SubList，來(lái)構(gòu)建一個(gè)獨(dú)立的 ArrayList；
另一種是，對(duì)于 Java 8 使用 Stream 的 skip 和 limit API 來(lái)跳過(guò)流中的元素，以及限制流中元素的個(gè)數(shù)，同樣可以達(dá)到 SubList 切片的目的。
//方式一：List<Integer> subList = new ArrayList<>(list.subList(1, 4));//方式二：List<Integer> subList = list.stream().skip(1).limit(3).collect(Collectors.toList());修復(fù)后代碼輸出如下：
[2, 3, 4][1, 2, 3, 4, 5, 6, 7, 8, 9, 10]24可以看到，刪除 SubList 的元素不再影響原始 List，而對(duì)原始 List 的修改也不會(huì)再出現(xiàn) List 迭代異常。
在使用 List 集合類的時(shí)候，不注意使用場(chǎng)景也會(huì)遇見兩個(gè)常見誤區(qū)。
第一個(gè)誤區(qū)是，使用數(shù)據(jù)結(jié)構(gòu)不考慮平衡時(shí)間和空間。
首先，定義一個(gè)只有一個(gè) int 類型訂單號(hào)字段的 Order 類：
@Data@NoArgsConstructor@AllArgsConstructorstatic class Order { private int orderId;}然后，定義一個(gè)包含 elementCount 和 loopCount 兩個(gè)參數(shù)的 listSearch 方法，初始化一個(gè)具有 elementCount 個(gè)訂單對(duì)象的 ArrayList，循環(huán) loopCount 次搜索這個(gè) ArrayList，每次隨機(jī)搜索一個(gè)訂單號(hào)：
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;}隨后，定義另一個(gè) mapSearch 方法，從一個(gè)具有 elementCount 個(gè)元素的 Map 中循環(huán) loopCount 次查找隨機(jī)訂單號(hào)。Map 的 Key 是訂單號(hào)，Value 是訂單對(duì)象：
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 的時(shí)間復(fù)雜度是 O(n)，而 HashMap 的 get 操作的時(shí)間復(fù)雜度是 O(1)。所以，要對(duì)大 List 進(jìn)行單值搜索的話，可以考慮使用 HashMap，其中 Key 是要搜索的值，Value 是原始對(duì)象，會(huì)比使用 ArrayList 有非常明顯的性能優(yōu)勢(shì)。
如下代碼所示，對(duì) 100 萬(wàn)個(gè)元素的 ArrayList 和 HashMap，分別調(diào)用 listSearch 和 mapSearch 方法進(jìn)行 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());通過(guò)運(yùn)行結(jié)果可以看到，僅僅是 1000 次搜索，listSearch 方法耗時(shí) 3.3 秒，而 mapSearch 耗時(shí)僅僅 108 毫秒。
即使我們要搜索的不是單值而是條件區(qū)間，也可以嘗試使用 HashMap 來(lái)進(jìn)行“搜索性能優(yōu)化”。如果你的條件區(qū)間是固定的話，可以提前把 HashMap 按照條件區(qū)間進(jìn)行分組，Key 就是不同的區(qū)間。
的確，如果業(yè)務(wù)代碼中有頻繁的大 ArrayList 搜索，使用 HashMap 性能會(huì)好很多。類似，如果要對(duì)大 ArrayList 進(jìn)行去重操作，也不建議使用 contains 方法，而是可以考慮使用 HashSet 進(jìn)行去重。說(shuō)到這里，還有一個(gè)問(wèn)題，使用 HashMap 是否會(huì)犧牲空間呢？
為此，我們使用 ObjectSizeCalculator 工具打印 ArrayList 和 HashMap 的內(nèi)存占用，可以看到 ArrayList 占用內(nèi)存 21M，而 HashMap 占用的內(nèi)存達(dá)到了 72M，是 List 的三倍多。進(jìn)一步使用 MAT 工具分析堆可以再次證明，ArrayList 在內(nèi)存占用上性價(jià)比很高，77% 是實(shí)際的數(shù)據(jù)（如第 1 個(gè)圖所示，16000000/20861992），而 HashMap 的“含金量”只有 22%。
所以，在應(yīng)用內(nèi)存吃緊的情況下，我們需要考慮是否值得使用更多的內(nèi)存消耗來(lái)?yè)Q取更高的性能。這里我們看到的是平衡的藝術(shù)，空間換時(shí)間，還是時(shí)間換空間，只考慮任何一個(gè)方面都是不對(duì)的。
第二個(gè)誤區(qū)是，過(guò)于迷信教科書的大 O 時(shí)間復(fù)雜度。
數(shù)據(jù)結(jié)構(gòu)中要實(shí)現(xiàn)一個(gè)列表，有基于連續(xù)存儲(chǔ)的數(shù)組和基于指針串聯(lián)的鏈表兩種方式。在 Java 中，有代表性的實(shí)現(xiàn)是 ArrayList 和 LinkedList，前者背后的數(shù)據(jù)結(jié)構(gòu)是數(shù)組，后者則是（雙向）鏈表。
在選擇數(shù)據(jù)結(jié)構(gòu)的時(shí)候，我們通常會(huì)考慮每種數(shù)據(jù)結(jié)構(gòu)不同操作的時(shí)間復(fù)雜度，以及使用場(chǎng)景兩個(gè)因素。查看這里，你可以看到數(shù)組和鏈表大 O 時(shí)間復(fù)雜度的顯著差異：
對(duì)于數(shù)組，隨機(jī)元素訪問(wèn)的時(shí)間復(fù)雜度是 O(1)，元素插入操作是 O(n)；
對(duì)于鏈表，隨機(jī)元素訪問(wèn)的時(shí)間復(fù)雜度是 O(n)，元素插入操作是 O(1)。
那么，在大量的元素插入、很少的隨機(jī)訪問(wèn)的業(yè)務(wù)場(chǎng)景下，是不是就應(yīng)該使用 LinkedList 呢？接下來(lái)，我們寫一段代碼測(cè)試下兩者隨機(jī)訪問(wèn)和插入的性能吧。
定義四個(gè)參數(shù)一致的方法，分別對(duì)元素個(gè)數(shù)為 elementCount 的 LinkedList 和 ArrayList，循環(huán) loopCount 次，進(jìn)行隨機(jī)訪問(wèn)和增加元素到隨機(jī)位置的操作：
//LinkedList訪問(wèn)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訪問(wèn)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));}測(cè)試代碼如下，10 萬(wàn)個(gè)元素，循環(huán) 10 萬(wàn)次：
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());運(yùn)行結(jié)果可能會(huì)讓你大跌眼鏡。在隨機(jī)訪問(wèn)方面，我們看到了 ArrayList 的絕對(duì)優(yōu)勢(shì)，耗時(shí)只有 11 毫秒，而 LinkedList 耗時(shí) 6.6 秒，這符合上面我們所說(shuō)的時(shí)間復(fù)雜度；但，隨機(jī)插入操作居然也是 LinkedList 落敗，耗時(shí) 9.3 秒，ArrayList 只要 1.5 秒：
---------------------------------------------ns % Task name---------------------------------------------6604199591 100% linkedListGet011494583 000% arrayListGetStopWatch '': running time = 10729378832 ns---------------------------------------------ns % Task name---------------------------------------------9253355484 086% linkedListAdd1476023348 014% arrayListAdd翻看 LinkedList 源碼發(fā)現(xiàn)，插入操作的時(shí)間復(fù)雜度是 O(1) 的前提是，你已經(jīng)有了那個(gè)要插入節(jié)點(diǎn)的指針。但，在實(shí)現(xiàn)的時(shí)候，我們需要先通過(guò)循環(huán)獲取到那個(gè)節(jié)點(diǎn)的 Node，然后再執(zhí)行插入操作。前者也是有開銷的，不可能只考慮插入操作本身的代價(jià)：
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; }}所以，對(duì)于插入操作，LinkedList 的時(shí)間復(fù)雜度其實(shí)也是 O(n)。繼續(xù)做更多實(shí)驗(yàn)的話你會(huì)發(fā)現(xiàn)，在各種常用場(chǎng)景下，LinkedList 幾乎都不能在性能上勝出 ArrayList。
諷刺的是，LinkedList 的作者約書亞 · 布洛克（Josh Bloch），在其推特上回復(fù)別人時(shí)說(shuō)，雖然 LinkedList 是我寫的但我從來(lái)不用，有誰(shuí)會(huì)真的用嗎？
圖片
這告訴我們，任何東西理論上和實(shí)際上是有差距的，請(qǐng)勿迷信教科書的理論，最好在下定論之前實(shí)際測(cè)試一下。拋開算法層面不談，由于 CPU 緩存、內(nèi)存連續(xù)性等問(wèn)題，鏈表這種數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)方式對(duì)性能并不友好，即使在它最擅長(zhǎng)的場(chǎng)景都不一定可以發(fā)揮威力。
今天，我分享了若干和 List 列表相關(guān)的錯(cuò)誤案例，基本都是由“想當(dāng)然”導(dǎo)致的。
第一，想當(dāng)然認(rèn)為，Arrays.asList 和 List.subList 得到的 List 是普通的、獨(dú)立的 ArrayList，在使用時(shí)出現(xiàn)各種奇怪的問(wèn)題。
Arrays.asList 得到的是 Arrays 的內(nèi)部類 ArrayList，List.subList 得到的是 ArrayList 的內(nèi)部類 SubList，不能把這兩個(gè)內(nèi)部類轉(zhuǎn)換為 ArrayList 使用。
Arrays.asList 直接使用了原始數(shù)組，可以認(rèn)為是共享“存儲(chǔ)”，而且不支持增刪元素；List.subList 直接引用了原始的 List，也可以認(rèn)為是共享“存儲(chǔ)”，而且對(duì)原始 List 直接進(jìn)行結(jié)構(gòu)性修改會(huì)導(dǎo)致 SubList 出現(xiàn)異常。
對(duì) Arrays.asList 和 List.subList 容易忽略的是，新的 List 持有了原始數(shù)據(jù)的引用，可能會(huì)導(dǎo)致原始數(shù)據(jù)也無(wú)法 GC 的問(wèn)題，最終導(dǎo)致 OOM。
第二，想當(dāng)然認(rèn)為，Arrays.asList 一定可以把所有數(shù)組轉(zhuǎn)換為正確的 List。當(dāng)傳入基本類型數(shù)組的時(shí)候，List 的元素是數(shù)組本身，而不是數(shù)組中的元素。
第三，想當(dāng)然認(rèn)為，內(nèi)存中任何集合的搜索都是很快的，結(jié)果在搜索超大 ArrayList 的時(shí)候遇到性能問(wèn)題。我們考慮利用 HashMap 哈希表隨機(jī)查找的時(shí)間復(fù)雜度為 O(1) 這個(gè)特性來(lái)優(yōu)化性能，不過(guò)也要考慮 HashMap 存儲(chǔ)空間上的代價(jià)，要平衡時(shí)間和空間。
第四，想當(dāng)然認(rèn)為，鏈表適合元素增刪的場(chǎng)景，選用 LinkedList 作為數(shù)據(jù)結(jié)構(gòu)。在真實(shí)場(chǎng)景中讀寫增刪一般是平衡的，而且增刪不可能只是對(duì)頭尾對(duì)象進(jìn)行操作，可能在 90% 的情況下都得不到性能增益，建議使用之前通過(guò)性能測(cè)試評(píng)估一下。
本文鏈接：http://www.www897cc.com/showinfo-26-80842-0.html小小ArrayList，居然這么多坑？！
聲明：本網(wǎng)頁(yè)內(nèi)容旨在傳播知識(shí)，若有侵權(quán)等問(wèn)題請(qǐng)及時(shí)與本網(wǎng)聯(lián)系，我們將在第一時(shí)間刪除處理。郵件：2376512515@qq.com
Copyright ? 2016-2023 天津谷騏科技有限公司 版權(quán)所有 sitemap.xml
違法及侵權(quán)請(qǐng)聯(lián)系：2376512515@qq.com 津ICP備18001702號(hào)
津公網(wǎng)安備 12010102000574號(hào)