摘要：盡可能避免使用，會導(dǎo)致復(fù)制數(shù)組，降低效率。再額外提一點，我們常用的另一個容器也是推薦要初始化長度從而避免擴容。

前不久幫同事一起 review 一個 job 執(zhí)行緩慢的問題時發(fā)現(xiàn)不少朋友在擼碼實現(xiàn)功能時還是有需要細節(jié)不夠注意，于是便有了這篇文章。

List temp = new ArrayList() ;

//獲取一批數(shù)據(jù)
List all = getData();
for(String str : all) {
    temp.add(str);
}

首先大家看看這段代碼有什么問題嘛？

其實在大部分情況下這都是沒啥問題，無非就是循環(huán)的往 ArrayList 中寫入數(shù)據(jù)而已。

但在特殊情況下，比如這里的 getData() 返回數(shù)據(jù)非常巨大時后續(xù) temp.add(str) 就會有問題了。

比如我們在 review 代碼時發(fā)現(xiàn)這里返回的數(shù)據(jù)有時會高達 2000W，這時 ArrayList 寫入的問題就凸顯出來了。

大家都知道 ArrayList 是由數(shù)組實現(xiàn)，而數(shù)據(jù)的長度有限；需要在合適的時機對數(shù)組擴容。

這里以插入到尾部為例 add(E e)。

ArrayList temp = new ArrayList<>(2) ;
temp.add("1");
temp.add("2");
temp.add("3");

當(dāng)我們初始化一個長度為 2 的 ArrayList ，并往里邊寫入三條數(shù)據(jù)時 ArrayList 就得擴容了，也就是將之前的數(shù)據(jù)復(fù)制一份到新的數(shù)組長度為 3 的數(shù)組中。

之所以是 3 ，是因為新的長度=原有長度 * 1.5

通過源碼我們可以得知 ArrayList 的默認長度為 10.

但其實并不是在初始化的時候就創(chuàng)建了 DEFAULT_CAPACITY = 10 的數(shù)組。

而是在往里邊 add 第一個數(shù)據(jù)的時候會擴容到 10.

既然知道了默認的長度為 10 ，那說明后續(xù)一旦寫入到第九個元素的時候就會擴容為 10*1.5 =15。
這一步為數(shù)組復(fù)制，也就是要重新開辟一塊新的內(nèi)存空間存放這 15 個數(shù)組。

一旦我們頻繁且數(shù)量巨大的進行寫入時就會導(dǎo)致許多的數(shù)組復(fù)制，這個效率是極低的。

但如果我們提前預(yù)知了可能會寫入多少條數(shù)據(jù)時就可以提前避免這個問題。

比如我們往里邊寫入 1000W 條數(shù)據(jù)，在初始化的時候就給定數(shù)組長度與用默認 10 的長度之間性能是差距巨大的。

我用 JMH 基準(zhǔn)測試驗證如下：

@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 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 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();
    }
}

根據(jù)結(jié)果可以看出預(yù)設(shè)長度的效率會比用默認的效率高上很多（這里的 Score 指執(zhí)行完函數(shù)所消耗的時間）。

所以這里強烈建議大家：在有大量數(shù)據(jù)寫入 ArrayList 時，一定要初始化指定長度。

再一個是一定要慎用 add(int index, E element) 向指定位置寫入數(shù)據(jù)。

通過源碼我們可以看出，每一次寫入都會將 index 后的數(shù)據(jù)往后移動一遍，其實本質(zhì)也是要復(fù)制數(shù)組；

但區(qū)別于往常規(guī)的往數(shù)組尾部寫入數(shù)據(jù)，它每次都會進行數(shù)組復(fù)制，效率極低。

提到 ArrayList 就不得不聊下 LinkedList 這個孿生兄弟；雖說都是 List 的容器，但本質(zhì)實現(xiàn)卻完全不同。

LinkedList 是由鏈表組成，每個節(jié)點又有頭尾兩個節(jié)點分別引用了前后兩個節(jié)點；因此它也是一個雙向鏈表。

所以理論上來說它的寫入非常高效，將不會有 ArrayList 中效率極低的數(shù)組復(fù)制，每次只需要移動指針即可。

這里偷懶就不畫圖了，大家自行腦補下。

坊間一直流傳：

LinkedList 的寫入效率高于 ArrayList，所以在寫大于讀的時候非常適用于 LinkedList 。

    @Benchmark
    @BenchmarkMode(Mode.AverageTime)
    @OutputTimeUnit(TimeUnit.MICROSECONDS)
    public void linkedList() {
        List array = new LinkedList<>();

        for (int i = 0; i < TEN_MILLION; i++) {
            array.add("123");
        }

    }

這里測試看下結(jié)論是否符合；同樣的也是對 LinkedList 寫入 1000W 次數(shù)據(jù)，通過結(jié)果來看初始化數(shù)組長度的 ArrayList 效率明顯是要高于 LinkedList 。

但這里的前提是要提前預(yù)設(shè) ArrayList 的數(shù)組長度，避免數(shù)組擴容，這樣 ArrayList 的寫入效率是非常高的，而 LinkedList 的雖然不需要復(fù)制內(nèi)存，但卻需要創(chuàng)建對象，變換指針等操作。

而查詢就不用多說了，ArrayList 可以支持下標(biāo)隨機訪問，效率非常高。

LinkedList 由于底層不是數(shù)組，不支持通過下標(biāo)訪問，而是需要根據(jù)查詢 index 所在的位置來判斷是從頭還是從尾進行遍歷。

但不管是哪種都得需要移動指針來一個個遍歷，特別是 index 靠近中間位置時將會非常慢。

高性能應(yīng)用都是從小細節(jié)一點點堆砌起來的，就如這里提到的 ArrayList 的坑一樣，日常使用沒啥大問題，一旦數(shù)據(jù)量起來所有的小問題都會成為大問題。

所以再總結(jié)下：

再使用 ArrayList 時如果能提前預(yù)測到數(shù)據(jù)量大小，比較大時一定要指定其長度。

盡可能避免使用 add(index,e) api，會導(dǎo)致復(fù)制數(shù)組，降低效率。

再額外提一點，我們常用的另一個 Map 容器 HashMap 也是推薦要初始化長度從而避免擴容。

本文所有測試代碼：

https://github.com/crossoverJie/JCSprout/blob/master/src/main/java/com/crossoverjie/basic/CollectionsTest.java

你的點贊與分享是對我最大的支持