ArrayList 源碼理解（一）

List

是一個接口，它繼承于Collection,是一個有序集合，我們可以精確控制每個元素的插入位置，和集合不同，列表支持重復(fù)的元素。

JDK版本11.04

ArrayList

ArrayList 是List的一個實現(xiàn)類，底層是基于動態(tài)數(shù)組的形式實現(xiàn)的ArrayList
[圖片上傳失敗...(image-83d310-1569232991949)]

ArrayList的源碼

常量
/**
     * Default initial capacity.
     */
    private static final int DEFAULT_CAPACITY = 10;

    /**
     * Shared empty array instance used for empty instances.
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};

    /**
     * Shared empty array instance used for default sized empty instances. We
     * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
     * first element is added.
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**
     * The array buffer into which the elements of the ArrayList are stored.
     * The capacity of the ArrayList is the length of this array buffer. Any
     * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
     * will be expanded to DEFAULT_CAPACITY when the first element is added.
     */
    transient Object[] elementData; // non-private to simplify nested class access

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

 public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }



    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            // defend against c.toArray (incorrectly) not returning Object[]
            // (see e.g. https://bugs.openjdk.java.net/browse/JDK-6260652)
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }


常量介紹:
DEFAULT_CAPACITY 是一個被final修飾的int型的常量，代表ArrayList默認(rèn)初始容量。
EMPTY_ELEMENTDATA 是一個空的列表，將會和上面的DEFAULT_CAPACITY聯(lián)系起來，創(chuàng)造一個容量的10的列表
DEFAULTCAPACITY_EMPTY_ELEMENTDATA也是一個空列表，但它和上面的不同，第一次添加元素時知道該 elementData 
從空的構(gòu)造函數(shù)還是有參構(gòu)造函數(shù)被初始化的。以便確認(rèn)如何擴容。

從上面的代碼可以看出，ArrayList有三個構(gòu)造函數(shù)，第一個構(gòu)造函數(shù)是指定容量的構(gòu)造函數(shù)。有如下幾點，第一：如果容量傳入一個負(fù)數(shù)，將會拋出一個IllegalArgumentException異常，第二：如果容量>0,就創(chuàng)造一個容量大小的列表，如果容量為0，便指定這個列表是一個EMPTY_ELEMENTDATA空列表。

第二個無參構(gòu)造函數(shù)，按照注釋解釋，構(gòu)造一個容量大小為 10 的空的 list 集合，但構(gòu)造函數(shù)了只是給 elementData 賦值了一個空的數(shù)組，其實是在第一次添加元素時容量擴大至 10 的。

第三個構(gòu)造函數(shù)，將 Collection 轉(zhuǎn)化為數(shù)組并賦值給 elementData，把 elementData 中元素的個數(shù)賦值給 size。 如果 size 不為零，則判斷 elementData 的 class 類型是否為 Object[]，不是的話則做一次轉(zhuǎn)換。 如果 size 為零，則把 EMPTY_ELEMENTDATA 賦值給 elementData，相當(dāng)于new ArrayList(0)。

重要函數(shù)

   /**
     * This helper method split out from add(E) to keep method
     * bytecode size under 35 (the -XX:MaxInlineSize default value),
     * which helps when add(E) is called in a C1-compiled loop.
     */
    private void add(E e, Object[] elementData, int s) {
        if (s == elementData.length)
            elementData = grow();
        elementData[s] = e;
        size = s + 1;
    }

    /**
     * Appends the specified element to the end of this list.
     *
     * @param e element to be appended to this list
     * @return {@code true} (as specified by {@link Collection#add})
     */
    public boolean add(E e) {
        modCount++;
        add(e, elementData, size);
        return true;
    }

    /**
     * Inserts the specified element at the specified position in this
     * list. Shifts the element currently at that position (if any) and
     * any subsequent elements to the right (adds one to their indices).
     *
     * @param index index at which the specified element is to be inserted
     * @param element element to be inserted
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public void add(int index, E element) {
        rangeCheckForAdd(index);
        modCount++;
        final int s;
        Object[] elementData;
        if ((s = size) == (elementData = this.elementData).length)
            elementData = grow();
        System.arraycopy(elementData, index,
                         elementData, index + 1,
                         s - index);
        elementData[index] = element;
        size = s + 1;
    }

首先我們觀察 add 函數(shù)

看源碼時你會發(fā)現(xiàn)，有一個modCount++的操作，這是為什么呢？ 通過查看，modCount是AbstractList中定義的一個保護變量，源碼注釋中給出了比較詳細的解釋，作用大概是用于記錄list結(jié)構(gòu)被修改的次數(shù)。

image

平常很少用到add(int index, E element)這個函數(shù),這個函數(shù)有一個陷阱。在本文最下方講解。

當(dāng)我們執(zhí)行 list.add（Element）時，會調(diào)用了add(E e, Object[] elementData, int s)這個函數(shù)，并進行了一次判斷，如果當(dāng)前元素的個數(shù)已經(jīng)和list的長度相同，也就是俗話說裝滿了，便會執(zhí)行g(shù)row（）函數(shù),用來改變list空間的大小。elementData代表著list，grow（）函數(shù)調(diào)用了newCapacity(minCapacity) minCapacity的大小為size+1。

在newCapacity（）函數(shù)內(nèi)部，使用了移位操作符將新容量擴容為老容量的1.5倍，然后判斷新容量和所需容量，如果新容量小于所需容量，就把新容量大小改成所需容量


    private Object[] grow(int minCapacity) {
        return elementData = Arrays.copyOf(elementData,
                                           newCapacity(minCapacity));
    }

    private Object[] grow() {
        return grow(size + 1);
    }


    /**
     * Returns a capacity at least as large as the given minimum capacity.
     * Returns the current capacity increased by 50% if that suffices.
     * Will not return a capacity greater than MAX_ARRAY_SIZE unless
     * the given minimum capacity is greater than MAX_ARRAY_SIZE.
     *
     * @param minCapacity the desired minimum capacity
     * @throws OutOfMemoryError if minCapacity is less than zero
     */
    private int newCapacity(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity <= 0) {
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
                return Math.max(DEFAULT_CAPACITY, minCapacity);
            if (minCapacity < 0) // overflow
                throw new OutOfMemoryError();
            return minCapacity;
        }
        return (newCapacity - MAX_ARRAY_SIZE <= 0)
            ? newCapacity
            : hugeCapacity(minCapacity);
    }

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

在newCapacity函數(shù)的的下方，將新容量將MAX_ARRAY_SIZE進行了比較，其大小為Integer.MAX_VALUE-8，在注釋中也給出了解釋，虛擬機在數(shù)組中存在一些保留字。MAX_VALUE的值為0x7fffffff，這是int類型（有符號）的最大值，有21億多個，準(zhǔn)確數(shù)值為2147483648

image

陷阱

借鑒地址

結(jié)合我自己的理解，當(dāng)我們執(zhí)行
ArrayList<Integer> integers = new ArrayList<>(3);時并不是創(chuàng)造了一個長度為3的數(shù)組隊列，結(jié)合構(gòu)造函數(shù)的源碼可知，在底層時創(chuàng)造了一個長度為3的空數(shù)組集合，當(dāng)前l(fā)ist集合仍然是一個帶有初始容量3的empty list。

例子

 ArrayList<Integer> integers = new ArrayList<>(3);
        integers.add(1);
        integers.add(2);
        System.out.println(integers);
//        integers.add(1,4);
        integers.set(2,4);
//        integers.add(2,3);
//        integers.set(2,3);
        System.out.println(integers);

在上面的代碼中，我創(chuàng)造了一個大小為3的集合，并添加了第一個和第二個元素，在嘗試使用
integers.set(2,4);來添加第三個元素時，運行出錯。原因如下


image

image

image

在if判斷中判斷index >= length（length就是傳過來的size值）index(2)=size(2)進而導(dǎo)致出錯，只有這種index大于等于size的情況下set才會出現(xiàn)錯誤

image

add情況是在index大于size的情況下報錯

閑扯一句

JAVA中初始化ArrayList的三種方式

一、最常用的初始化方式

     List<String> list1 = new ArrayList<String>();
     list1.add("apple");
     list1.add("banana");
     list1.add("orange");

二、使用一個List來初始化。

  List<String> list2 = new ArrayList<String>(Arrays.asList("apple", "banana", "orange"));

三、使用匿名內(nèi)部類來初始化。

 List<String> list4 = new ArrayList<String>() {
         {
             add("apple");
             add("banana");
             add("orange");
         }
     };

未完待續(xù)

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

友情鏈接更多精彩內(nèi)容