常見的集合容器應當避免的坑
前言
前不久幫同事一起 review 一個 job 執行緩慢的問題時，發現不少朋友在擼碼實現功能時，還是有細節不夠注意，于是便有了這篇文章。
ArrayList 踩坑
- List<String> temp = new ArrayList() ;
- //獲取一批數據
- List<String> all = getData();
- for(String str : all) {
- temp.add(str);
- }
首先大家看看這段代碼有什么問題嘛?
其實在大部分情況下這都是沒啥問題，無非就是循環的往 ArrayList 中寫入數據而已。
但在特殊情況下，比如這里的 getData() 返回數據非常巨大時后續 temp.add(str) 就會有問題了。
比如我們在 review 代碼時發現這里返回的數據有時會高達 2000W，這時 ArrayList 寫入的問題就凸顯出來了。
填坑指南
大家都知道 ArrayList 是由數組實現，而數據的長度有限；需要在合適的時機對數組擴容。
這里以插入到尾部為例 add(E e)。
- ArrayList<String> temp = new ArrayList<>(2) ;
- temp.add("1");
- temp.add("2");
- temp.add("3");
當我們初始化一個長度為 2 的 ArrayList ，并往里邊寫入三條數據時 ArrayList 就得擴容了，也就是將之前的數據復制一份到新的數組長度為 3 的數組中。
之所以是 3 ，是因為新的長度=原有長度 * 1.5
通過源碼，我們可以得知 ArrayList 的默認長度為 10。
但其實并不是在初始化的時候就創建了 DEFAULT_CAPACITY=10 的數組。
而是在往里邊 add ***個數據的時候會擴容到 10。
既然知道了默認的長度為 10 ，那說明后續一旦寫入到第九個元素的時候就會擴容為 10*1.5=15。這一步為數組復制，也就是要重新開辟一塊新的內存空間存放這 15 個數組。
一旦我們頻繁且數量巨大的進行寫入時就會導致許多的數組復制，這個效率是極低的。
但如果我們提前預知了可能會寫入多少條數據時，就可以提前避免這個問題。
比如我們往里邊寫入 1000W 條數據，在初始化的時候就給定數組長度與用默認 10 的長度之間性能是差距巨大的。
我用 JMH 基準測試，驗證如下：
- @Warmup(iterations = 5, time = 1, timeUnit = TimeUnit.SECONDS)
- @Measurement(iterations = 5, time = 1, timeUnit = TimeUnit.SECONDS)
- public class CollectionsTest {
- private static final int TEN_MILLION = 10000000;
- @Benchmark
- @BenchmarkMode(Mode.AverageTime)
- @OutputTimeUnit(TimeUnit.MICROSECONDS)
- public void arrayList() {
- List<String> array = new ArrayList<>();
- for (int i = 0; i < TEN_MILLION; i++) {
- array.add("123");
- }
- }
- @Benchmark
- @BenchmarkMode(Mode.AverageTime)
- @OutputTimeUnit(TimeUnit.MICROSECONDS)
- public void arrayListSize() {
- List<String> array = new ArrayList<>(TEN_MILLION);
- for (int i = 0; i < TEN_MILLION; i++) {
- array.add("123");
- }
- }
- public static void main(String[] args) throws RunnerException {
- Options opt = new OptionsBuilder()
- .include(CollectionsTest.class.getSimpleName())
- .forks(1)
- .build();
- new Runner(opt).run();
- }
- }
根據結果可以看出預設長度的效率會比用默認的效率高上很多(這里的 Score 指執行完函數所消耗的時間)。
所以這里強烈建議大家：在有大量數據寫入 ArrayList 時，一定要初始化指定長度。
再一個是一定要慎用 add(intindex,E element) 向指定位置寫入數據。
通過源碼我們可以看出，每一次寫入都會將 index 后的數據往后移動一遍，其實本質也是要復制數組。
但區別于往常規的往數組尾部寫入數據，它每次都會進行數組復制，效率極低。
LinkedList
提到 ArrayList 就不得不聊下 LinkedList 這個孿生兄弟;雖說都是 List 的容器，但本質實現卻完全不同。
LinkedList 是由鏈表組成，每個節點又有頭尾兩個節點分別引用了前后兩個節點;因此它也是一個雙向鏈表。
所以理論上來說它的寫入非常高效，將不會有 ArrayList 中效率極低的數組復制，每次只需要移動指針即可。
這里偷懶就不畫圖了，大家自行腦補下。
對比測試
坊間一直流傳：
LinkedList 的寫入效率高于 ArrayList，所以在寫大于讀的時候非常適用于 LinkedList 。
- @Benchmark
- @BenchmarkMode(Mode.AverageTime)
- @OutputTimeUnit(TimeUnit.MICROSECONDS)
- public void linkedList() {
- List<String> array = new LinkedList<>();
- for (int i = 0; i < TEN_MILLION; i++) {
- array.add("123");
- }
- }
這里測試看下結論是否符合;同樣的也是對 LinkedList 寫入 1000W 次數據，通過結果來看初始化數組長度的 ArrayList 效率明顯是要高于 LinkedList 。
但這里的前提是要提前預設 ArrayList 的數組長度，避免數組擴容，這樣 ArrayList 的寫入效率是非常高的，而 LinkedList 的雖然不需要復制內存，但卻需要創建對象，變換指針等操作。
而查詢就不用多說了， ArrayList 可以支持下標隨機訪問，效率非常高。
LinkedList 由于底層不是數組，不支持通過下標訪問，而是需要根據查詢 index 所在的位置來判斷是從頭還是從尾進行遍歷。
但不管是哪種都得需要移動指針來一個個遍歷，特別是 index 靠近中間位置時將會非常慢。
總結
高性能應用都是從小細節一點點堆砌起來的，就如這里提到的 ArrayList 的坑一樣，日常使用沒啥大問題，一旦數據量起來所有的小問題都會成為大問題。
所以再總結下：
- 再使用 ArrayList 時如果能提前預測到數據量大小，比較大時一定要指定其長度。
- 盡可能避免使用 add(index,e) api，會導致復制數組，降低效率。
- 再額外提一點，我們常用的另一個 Map 容器 HashMap 也是推薦要初始化長度從而避免擴容。
本文所有測試代碼：https://github.com/crossoverJie/JCSprout/blob/master/src/main/java/com/crossoverjie/basic/CollectionsTest.java
