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

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

List temp = new ArrayList() ;

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

首先大家看看這段代碼有什么問(wèn)題嘛？

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

但在特殊情況下，比如這里的 getData() 返回?cái)?shù)據(jù)非常巨大時(shí)后續(xù) temp.add(str) 就會(huì)有問(wèn)題了。

比如我們?cè)?review 代碼時(shí)發(fā)現(xiàn)這里返回的數(shù)據(jù)有時(shí)會(huì)高達(dá) 2000W，這時(shí) ArrayList 寫入的問(wèn)題就凸顯出來(lái)了。

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

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

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

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

之所以是 3 ，是因?yàn)樾碌拈L(zhǎng)度=原有長(zhǎng)度 * 1.5

通過(guò)源碼我們可以得知 ArrayList 的默認(rèn)長(zhǎng)度為 10.

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

而是在往里邊 add 第一個(gè)數(shù)據(jù)的時(shí)候會(huì)擴(kuò)容到 10.

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

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

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

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

我用 JMH 基準(zhǔn)測(cè)試驗(yà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è)長(zhǎng)度的效率會(huì)比用默認(rèn)的效率高上很多（這里的 Score 指執(zhí)行完函數(shù)所消耗的時(shí)間）。

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

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

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

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

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

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

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

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

坊間一直流傳：

LinkedList 的寫入效率高于 ArrayList，所以在寫大于讀的時(shí)候非常適用于 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");
        }

    }

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

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

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

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

但不管是哪種都得需要移動(dòng)指針來(lái)一個(gè)個(gè)遍歷，特別是 index 靠近中間位置時(shí)將會(huì)非常慢。

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

所以再總結(jié)下：

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

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

再額外提一點(diǎn)，我們常用的另一個(gè) Map 容器 HashMap 也是推薦要初始化長(zhǎng)度從而避免擴(kuò)容。

本文所有測(cè)試代碼：

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

你的點(diǎn)贊與分享是對(duì)我最大的支持