Java容器類框架(1)ArrayList源碼分析

概述

在分析ArrayList源碼之前，先看一下ArrayList在數(shù)據(jù)結(jié)構(gòu)中的位置，常見的數(shù)據(jù)結(jié)構(gòu)按照邏輯結(jié)構(gòu)跟存儲結(jié)構(gòu)如下：

數(shù)據(jù)結(jié)構(gòu)分類

先看看源碼的注釋：

  • Resizable-array implementation of the <tt>List</tt> interface. Implements all optional list operations, and permits all elements, including
    <tt>null</tt>. In addition to implementing the <tt>List</tt> interface,
    this class provides methods to manipulate the size of the array that is
    used internally to store the list. (This class is roughly equivalent to
    <tt>Vector</tt>, except that it is unsynchronized.)
  • 實(shí)現(xiàn)了List接口的可調(diào)整大小的數(shù)組，也就是經(jīng)常說的動態(tài)數(shù)組，實(shí)現(xiàn)了所有的可選的列表的操作，并且能夠插入任何元素，包括空值。除了實(shí)現(xiàn)了List接口之外，對于內(nèi)部存儲的數(shù)組，也提供了相應(yīng)的改變數(shù)組大小的方法。(這個類除了不是線程安全的，幾乎可以相當(dāng)于Vector)

很明顯，ArrayList是一個線性結(jié)構(gòu)，底層通過數(shù)組實(shí)現(xiàn)，并且是動態(tài)數(shù)組。

下面看一下ArrayList的繼承關(guān)系，這個是通過IDEA生成的繼承關(guān)系圖，很清晰，終于不用自己畫了。

ArrayList繼承關(guān)系

通過圖可以看到ArrayList繼承自AbstractList，并且實(shí)現(xiàn)了List<E>, RandomAccess, Cloneable, Serializable接口，而AbstractList實(shí)現(xiàn)了Collection接口，則ArrayList具有Collection的所有方法，而且能夠進(jìn)行clone,序列化，下面開始開始對ArrayList的源碼進(jìn)行分析，吼吼。

正文

成員變量

//序列化ID
 private static final long serialVersionUID = 8683452581122892189L;
//默認(rèn)的初始化數(shù)組的容量為10
 private static final int DEFAULT_CAPACITY = 10;
//共享的空數(shù)組，也就是調(diào)用空的構(gòu)造方法的時候會進(jìn)行默認(rèn)用這個數(shù)組進(jìn)行初始化
private static final Object[] EMPTY_ELEMENTDATA = {};
//數(shù)組緩沖區(qū)，也就是從來存放List元素的數(shù)組。ArrayList的容量就是緩沖區(qū)數(shù)組的長度。對于一個空數(shù)組，在添加第一個元素的時候，List的容量會被設(shè)置成默認(rèn)的DEFAULT_CAPACITY，也就是10，
transient Object[] elementData;
//elementData的長度
private int size;

構(gòu)造方法

構(gòu)造一個空數(shù)組，采用默認(rèn)容量(Constructs an empty list with an initial capacity of ten)

  public ArrayList() {
        super();
        this.elementData = EMPTY_ELEMENTDATA;
    }
    
  public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
    
     private void ensureCapacityInternal(int minCapacity) {
        if (elementData == EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }

前面有提到過，當(dāng)初始化數(shù)組為空的時候，在add的時候會進(jìn)行判斷，如果數(shù)組的長度為0，數(shù)組的長度就是默認(rèn)的數(shù)組長度

構(gòu)造一個空的數(shù)組，自定義數(shù)組容量(Constructs an empty list with the specified initial capacity)

  public ArrayList(int initialCapacity) {
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        this.elementData = new Object[initialCapacity];
    }

這個跟上面的區(qū)別在于創(chuàng)建了一個新的數(shù)組，數(shù)組的最大長度就是傳入的初始化容量，數(shù)組的長度為0。

傳入一個集合進(jìn)行初始化(Constructs a list containing the elements of the specified collection, in the order they are returned by the collection's iterator.)

 public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        size = elementData.length;
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    }

數(shù)組的長度就是傳入的集合的長度，將集合傳入緩沖數(shù)組

Add方法

在末尾添加一個元素(Appends the specified element to the end of this list.)

   public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

在指定位置添加一個元素(Inserts the specified element at the specified position in this list.)

 public void add(int index, E element) {
 //判斷index是否合乎規(guī)范
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
//檢查是否需要擴(kuò)容
        ensureCapacityInternal(size + 1);  // Increments modCount!!
//拷貝數(shù)組
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
//進(jìn)行賦值
        elementData[index] = element;
//將數(shù)組的長度自增
        size++;
    }

在末尾添加一個集合(Appends all of the elements in the specified collection to the end of this list)

 public boolean addAll(Collection<? extends E> c) {
        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);  // Increments modCount
        System.arraycopy(a, 0, elementData, size, numNew);
        size += numNew;
        return numNew != 0;
    }

在指定位置添加集合(Inserts all of the elements in the specified collection into this list, starting at the specified position)

  public boolean addAll(int index, Collection<? extends E> c) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);  // Increments modCount
        int numMoved = size - index;
        if (numMoved > 0)
            System.arraycopy(elementData, index, elementData, index + numNew, numMoved);
        System.arraycopy(a, 0, elementData, index, numNew);
        size += numNew;
        return numNew != 0;
    }

Add操作有如上幾個重載方法，仔細(xì)觀察一下，大同小異，我們選擇第二個重載方法，也就是在指定位置添加一個元素：

  1. 判斷index是否合理
  2. 檢查是否需要擴(kuò)容
  3. 拷貝數(shù)組
  4. 進(jìn)行賦值
  5. 將數(shù)組的長度自增

這里面比較有營養(yǎng)的就是第二步了，下面重點(diǎn)分析第二步：

調(diào)用ensureCapacityInternal(size++1)

   private void ensureCapacityInternal(int minCapacity) {
        if (elementData == EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }

傳入了此時數(shù)組需要的長度，只要數(shù)組為初始化的時候沒有指定容量，就會在minCapacity(size+1)跟DEFAULT_CAPACITY中間取一個最大值，之所以這樣，是因?yàn)槿绻麑?shù)組的容量設(shè)置成太小，會導(dǎo)致數(shù)組頻繁的擴(kuò)容，影響性能。

調(diào)用ensureExplicitCapacity(minCapacity)

    private void ensureExplicitCapacity(int minCapacity) {
    //這個變量來自于ArrayList的父類AbstractList，主要用來記錄集合的操作次數(shù)
        modCount++;
        // overflow-conscious code
        //如果此時需要的數(shù)組長度大于數(shù)組本身的長度，則進(jìn)行擴(kuò)容
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

執(zhí)行擴(kuò)容操作grow(minCapacity)

   private void grow(int minCapacity) {
        // overflow-conscious code
        //數(shù)組當(dāng)前的容量
        int oldCapacity = elementData.length;
        //擴(kuò)容后新數(shù)組的容量,增大了0.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        
        //如果擴(kuò)容后的數(shù)組比當(dāng)前的所需要的數(shù)組長度要小，則區(qū)當(dāng)前需要的長度
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        //將擴(kuò)容后的數(shù)組長度跟定義的數(shù)組最大長度進(jìn)行比較，防止越界
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        //進(jìn)行擴(kuò)容操作
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

Remove方法

remove指定位置元素（Removes the element at the specified position in this list）

  public E remove(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

        modCount++;
        E oldValue = (E) elementData[index];

        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // clear to let GC do its work

        return oldValue;
    }

移除某個具體元素(Removes the first occurrence of the specified element from this list,if it is present. If the list does not contain the element, it is unchanged)

    public boolean remove(Object o) {
    
        if (o == null) {
            for (int index = 0; index < size; index++)
                if (elementData[index] == null) {
                    fastRemove(index);
                    return true;
                }
        } else {
            for (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) {
            
                    fastRemove(index);
                    return true;
                }
        }
        return false;
    }

  //此時執(zhí)行的代碼就是刪除指定位置的代碼
    private void fastRemove(int index) {
        modCount++;
        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // clear to let GC do its work
    }

仔細(xì)觀察一下上面兩個重載方法，其實(shí)是差不多的，刪除元素分兩步走：

  1. 找到這個元素
  2. 執(zhí)行刪除操作

比較簡單，不過多描述

Set方法

    public E set(int index, E element) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

        E oldValue = (E) elementData[index];
        elementData[index] = element;
        return oldValue;
    }

直接替換掉對應(yīng)的元素

查找索引操作

尋找元素第一次出現(xiàn)的下標(biāo)(Returns the index of the first occurrence of the specified element)

  public int indexOf(Object o) {
        if (o == null) {
            for (int i = 0; i < size; i++)
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = 0; i < size; i++)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }

尋找最后出現(xiàn)的某個元素的索引(Returns the index of the last occurrence of the specified element in this list)

   public int lastIndexOf(Object o) {
        if (o == null) {
            for (int i = size-1; i >= 0; i--)
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = size-1; i >= 0; i--)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }

這些都是通過遍歷對元素進(jìn)行查找，一個是從頭到尾遍歷，一個是從未到頭遍歷，查到結(jié)構(gòu)就返回對應(yīng)的下表，否則返回-1.

Get方法

   public E get(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

        return (E) elementData[index];
    }

總結(jié)

ArrayList的特點(diǎn)

  • 有序的，元素可以重復(fù)
  • 查詢快，增刪慢
  • 當(dāng)容量不夠的時候，會進(jìn)行擴(kuò)容至當(dāng)前size的1.5倍
  • 非線程安全

關(guān)于ArrayList的源碼就分析到這里，因?yàn)榈讓拥膶?shí)現(xiàn)是數(shù)組，所以不管是擴(kuò)容還是其它的增刪改查操作都是對數(shù)組進(jìn)行操作，所以只要對數(shù)組足夠了解，基本上還是挺好理解的。

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

相關(guān)閱讀更多精彩內(nèi)容

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