ArrayList 源碼分析

ArrayList 源碼分析

作者:vwFisher

時間:2019-11-04

GitHub代碼:https://github.com/vwFisher/JavaBasicGuide

目錄



1 構(gòu)造函數(shù) 和 屬性

    private static final int DEFAULT_CAPACITY = 10; // 初始容量
    private static final Object[] EMPTY_ELEMENTDATA = {};
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    transient Object[] elementData; // non-private to simplify nested class access
    private int size; // 數(shù)組當前容量

    /**
     * 默認構(gòu)造函數(shù),使用初始容量10構(gòu)造一個空列表(無參數(shù)構(gòu)造)
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

    /**
     * 帶初始容量參數(shù)的構(gòu)造函數(shù)撤嫩。(用戶自己指定容量)
     */
    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

    /**
     * 構(gòu)造包含指定collection元素的列表蠢终,這些元素利用該集合的迭代器按順序返回
     * 如果指定的集合為null寻拂,throws NullPointerException。 
     */
    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

注意梦染,無參構(gòu)造函數(shù)朴皆,創(chuàng)建ArrayList遂铡,此時 容量是為0的,當添加元素才擴容為10

2. 擴容機制

一伪货、先看 add 方法

    /**
     * Appends the specified element to the end of this list.
     *
     * @param e element to be appended to this list
     * @return <tt>true</tt> (as specified by {@link Collection#add})
     */
    public boolean add(E e) {
        // 擴容方法
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

二、ensureCapacityInternal() 方法

    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }

    private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

如果 采用默認采購函數(shù)蒙挑,當 要 add 進第1個元素時愚臀,minCapacity為1,在Math.max()方法比較后馋袜,minCapacity 為10舶斧。

三、ensureExplicitCapacity() 方法

判斷是否需要擴容泽台,如果需要 則 調(diào)用 grow 方法

    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

我們來仔細分析一下:

  1. 當我們要 add 進第1個元素到 ArrayList 時师痕,elementData.length 為0 (因為還是一個空的 list)而账,因為執(zhí)行了 ensureCapacityInternal() 方法 因篇,所以 minCapacity 此時為10。此時咐吼,minCapacity - elementData.length > 0 成立商佑,所以會進入 grow(minCapacity) 方法。
  2. 當add第2個元素時肌幽,minCapacity 為2喂急,此時e lementData.length(容量)在添加第一個元素后擴容成 10 了笛求。此時,minCapacity - elementData.length > 0 不成立析蝴,所以不會進入 (執(zhí)行)grow(minCapacity) 方法。
  3. 添加第3响禽、4···到第10個元素時荚醒,依然不會執(zhí)行g(shù)row方法,數(shù)組容量都為10侯繁。

直到添加第11個元素泡躯,minCapacity(為11)比elementData.length(為10)要大。進入grow方法進行擴容咕别。

四惰拱、grow() 方法

    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    
    private void grow(int minCapacity) {
        // oldCapacity為舊容量啊送,newCapacity為新容量
        int oldCapacity = elementData.length;
        
        //將oldCapacity 右移一位,其效果相當于oldCapacity /2昔逗,
        //我們知道位運算的速度遠遠快于整除運算,整句運算式的結(jié)果就是將新容量更新為舊容量的1.5倍勾怒,
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        
        //然后檢查新容量是否大于最小需要容量声旺,若還是小于最小需要容量,那么就把最小需要容量當作數(shù)組的新容量卡乾,
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
            
        // 如果新容量大于 MAX_ARRAY_SIZE,進入(執(zhí)行) `hugeCapacity()` 方法來比較 minCapacity 和 MAX_ARRAY_SIZE幔妨,
        //如果minCapacity大于最大容量,則新容量則為`Integer.MAX_VALUE`误堡,否則,新容量大小則為 MAX_ARRAY_SIZE 即為 `Integer.MAX_VALUE - 8`陪踩。
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
            
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

int newCapacity = oldCapacity + (oldCapacity >> 1),所以 ArrayList 每次擴容之后容量都會變?yōu)樵瓉淼?1.5 倍肩狂!(JDK1.6版本以后)

JDk1.6版本時姥饰,擴容之后容量為 1.5 倍+1!詳情請參考源碼

3 System.arraycopy() 和 Arrays.copyOf()方法

在 ArrayList 源碼大量調(diào)用了這兩個方法审磁。比如:我們上面講的擴容操作以及add(int index, E element)岂座、toArray() 等方法中都用到了該方法!

3.1 System.arraycopy() 方法

   /**
    * 在此列表中的指定位置插入指定的元素钾恢。 
    *先調(diào)用 rangeCheckForAdd 對index進行界限檢查吕喘;然后調(diào)用 ensureCapacityInternal 方法保證capacity足夠大刑桑;
    *再將從index開始之后的所有成員后移一個位置祠斧;將element插入index位置;最后size加1辕漂。
    */
   public void add(int index, E element) {
       rangeCheckForAdd(index);

       ensureCapacityInternal(size + 1);  // Increments modCount!!
       //arraycopy()方法實現(xiàn)數(shù)組自己復(fù)制自己
       //elementData:源數(shù)組;index:源數(shù)組中的起始位置;elementData:目標數(shù)組吴超;index + 1:目標數(shù)組中的起始位置; size - index:要復(fù)制的數(shù)組元素的數(shù)量跋涣;
       System.arraycopy(elementData, index, elementData, index + 1, size - index);
       elementData[index] = element;
       size++;
   }

我們寫一個簡單的方法測試以下:

public class ArraycopyTest {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] a = new int[10];
        a[0] = 0;
        a[1] = 1;
        a[2] = 2;
        a[3] = 3;
        System.arraycopy(a, 2, a, 3, 3);
        a[2]=99;
        for (int i = 0; i < a.length; i++) {
            System.out.println(a[i]);
        }
    }
}

結(jié)果:

0 1 99 2 3 0 0 0 0 0 

3.2 Arrays.copyOf()方法

   /**
     以正確的順序返回一個包含此列表中所有元素的數(shù)組(從第一個到最后一個元素); 返回的數(shù)組的運行時類型是指定數(shù)組的運行時類型。 
     */
    public Object[] toArray() {
    //elementData:要復(fù)制的數(shù)組奖年;size:要復(fù)制的長度
        return Arrays.copyOf(elementData, size);
    }

個人覺得使用 Arrays.copyOf()方法主要是為了給原有數(shù)組擴容沛贪,測試代碼如下:

public class ArrayscopyOfTest {

    public static void main(String[] args) {
        int[] a = new int[3];
        a[0] = 0;
        a[1] = 1;
        a[2] = 2;
        int[] b = Arrays.copyOf(a, 10);
        System.out.println("b.length"+b.length);
    }
}

結(jié)果:

10

3.3 兩者聯(lián)系和區(qū)別

聯(lián)系:看兩者源代碼可以發(fā)現(xiàn) copyOf() 內(nèi)部實際調(diào)用了 System.arraycopy() 方法

區(qū)別:

  1. arraycopy() 需要目標數(shù)組利赋,將原數(shù)組拷貝到你自己定義的數(shù)組里或者原數(shù)組,而且可以選擇拷貝的起點和長度以及放入新數(shù)組中的位置之碗。
  2. copyOf() 是系統(tǒng)自動在內(nèi)部新建一個數(shù)組季希,并返回該數(shù)組。

4 ensureCapacity方法

ArrayList 源碼中有一個 ensureCapacity 方法不知道大家注意到?jīng)]有博敬,這個方法 ArrayList 內(nèi)部沒有被調(diào)用過峰尝,所以很顯然是提供給用戶調(diào)用的,那么這個方法有什么作用呢祭往?

    /**
    如有必要火窒,增加此 ArrayList 實例的容量,以確保它至少可以容納由minimum capacity參數(shù)指定的元素數(shù)已骇。
     *
     * @param   minCapacity   所需的最小容量
     */
    public void ensureCapacity(int minCapacity) {
        int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
            // any size if not default element table
            ? 0
            // larger than default for default empty table. It's already
            // supposed to be at default size.
            : DEFAULT_CAPACITY;

        if (minCapacity > minExpand) {
            ensureExplicitCapacity(minCapacity);
        }
    }

最好在 add 大量元素之前用 ensureCapacity 方法票编,以減少增量重新分配的次數(shù)

我們通過下面的代碼實際測試以下這個方法的效果:

public class EnsureCapacityTest {
    public static void main(String[] args) {
        ArrayList<Object> list = new ArrayList<Object>();
        final int N = 10000000;
        long startTime = System.currentTimeMillis();
        for (int i = 0; i < N; i++) {
            list.add(i);
        }
        long endTime = System.currentTimeMillis();
        System.out.println("使用ensureCapacity方法前:"+(endTime - startTime));

        list = new ArrayList<Object>();
        long startTime1 = System.currentTimeMillis();
        list.ensureCapacity(N);
        for (int i = 0; i < N; i++) {
            list.add(i);
        }
        long endTime1 = System.currentTimeMillis();
        System.out.println("使用ensureCapacity方法后:"+(endTime1 - startTime1));
    }
}

運行結(jié)果:

使用ensureCapacity方法前:4637
使用ensureCapacity方法后:241

通過運行結(jié)果慧域,我們可以很明顯的看出向 ArrayList 添加大量元素之前最好先使用ensureCapacity 方法,以減少增量重新分配的次數(shù)

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末辛藻,一起剝皮案震驚了整個濱河市,隨后出現(xiàn)的幾起案子蛹屿,更是在濱河造成了極大的恐慌岩榆,老刑警劉巖,帶你破解...
    沈念sama閱讀 216,372評論 6 498
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件犹撒,死亡現(xiàn)場離奇詭異粒褒,居然都是意外死亡,警方通過查閱死者的電腦和手機祥款,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 92,368評論 3 392
  • 文/潘曉璐 我一進店門刃跛,熙熙樓的掌柜王于貴愁眉苦臉地迎上來苛萎,“玉大人,你說我怎么就攤上這事蛙酪∏谈牵” “怎么了?”我有些...
    開封第一講書人閱讀 162,415評論 0 353
  • 文/不壞的土叔 我叫張陵藐俺,是天一觀的道長泥彤。 經(jīng)常有香客問我卿啡,道長,這世上最難降的妖魔是什么剑逃? 我笑而不...
    開封第一講書人閱讀 58,157評論 1 292
  • 正文 為了忘掉前任,我火速辦了婚禮蛹磺,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘裙品。我一直安慰自己俗或,他們只是感情好,可當我...
    茶點故事閱讀 67,171評論 6 388
  • 文/花漫 我一把揭開白布区匠。 她就那樣靜靜地躺著帅腌,像睡著了一般。 火紅的嫁衣襯著肌膚如雪揩懒。 梳的紋絲不亂的頭發(fā)上挽封,一...
    開封第一講書人閱讀 51,125評論 1 297
  • 那天,我揣著相機與錄音智亮,去河邊找鬼点待。 笑死,一個胖子當著我的面吹牛状原,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播颠区,決...
    沈念sama閱讀 40,028評論 3 417
  • 文/蒼蘭香墨 我猛地睜開眼毕莱,長吁一口氣:“原來是場噩夢啊……” “哼!你這毒婦竟也來了蛹稍?” 一聲冷哼從身側(cè)響起部服,我...
    開封第一講書人閱讀 38,887評論 0 274
  • 序言:老撾萬榮一對情侶失蹤,失蹤者是張志新(化名)和其女友劉穎厦酬,沒想到半個月后瘫想,有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 45,310評論 1 310
  • 正文 獨居荒郊野嶺守林人離奇死亡减噪,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 37,533評論 2 332
  • 正文 我和宋清朗相戀三年车吹,在試婚紗的時候發(fā)現(xiàn)自己被綠了。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片朝卒。...
    茶點故事閱讀 39,690評論 1 348
  • 序言:一個原本活蹦亂跳的男人離奇死亡乐埠,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出丈咐,到底是詐尸還是另有隱情,我是刑警寧澤伤疙,帶...
    沈念sama閱讀 35,411評論 5 343
  • 正文 年R本政府宣布辆影,位于F島的核電站,受9級特大地震影響蛙讥,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜谬墙,卻給世界環(huán)境...
    茶點故事閱讀 41,004評論 3 325
  • 文/蒙蒙 一经备、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧侵蒙,春花似錦、人聲如沸纷闺。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,659評論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽浸卦。三九已至,卻和暖如春靴庆,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背怒医。 一陣腳步聲響...
    開封第一講書人閱讀 32,812評論 1 268
  • 我被黑心中介騙來泰國打工稚叹, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留,地道東北人蛤奥。 一個月前我還...
    沈念sama閱讀 47,693評論 2 368
  • 正文 我出身青樓僚稿,卻偏偏與公主長得像,于是被迫代替她去往敵國和親蚀同。 傳聞我的和親對象是個殘疾皇子,可洞房花燭夜當晚...
    茶點故事閱讀 44,577評論 2 353

推薦閱讀更多精彩內(nèi)容

  • 首先看一下集合體系繼承樹 Collection接口 Collection是最基本的集合接口衰猛,一個Collectio...
    SnowDragonYY閱讀 946評論 0 2
  • interface Iterable : //實現(xiàn)此接口使集合對象可以通過迭代器遍歷自身元素 Iterator...
    阿桃_28e7閱讀 229評論 0 0
  • ArrayList是最常用的數(shù)組啡省,這里我們分析一下源碼: ArrayList繼承了AbstractList<E> ...
    說dian什么好呢閱讀 758評論 0 0
  • ArrayList ArrayList就是傳說中的動態(tài)數(shù)組卦睹,就是Array的復(fù)雜版本,它提供了如下一些好處:動態(tài)的...
    史路比閱讀 223評論 0 0
  • ArrayList是在Java中最常用的集合之一障斋,其本質(zhì)上可以當做是一個可擴容的數(shù)組,可以添加重復(fù)的數(shù)據(jù)垃环,也支持隨...
    ShawnIsACoder閱讀 571評論 4 7