<input id="ohw05"></input>
  • <table id="ohw05"><menu id="ohw05"></menu></table>
  • <var id="ohw05"></var>
  • <code id="ohw05"><cite id="ohw05"></cite></code>
    <label id="ohw05"></label>
    <var id="ohw05"></var>
  • ArrayList源碼解析

    在平時Java,存儲數據需要用到列表,而大多時候都能用到ArrayList,比如Mybatis查詢數據列表,返回列表都是ArrayList,很多數據的存放也用到了ArrayList

    jdk 版本: 1.8

    ArrayList 是基于大小可變的數組實現,并允許添加null值, 根據下標就能數據查詢快。數組一旦初始化就確定好了大小,如果需要添加數據,就需要做數據的復制,這些操作比較耗時。

    數組拷貝

    ArrayList數組的擴容、添加和刪除需要用到數組的拷貝,主要用到了以下兩個方法:

    • System.arraycopy
    • Arrays.copyOf

    System.arraycopy

    System.arraycopy()Java的原生的靜態方法,該方法將源數組元素拷貝到目標數組中去。

    參數詳解:

    • src 源數組
    • srcPos 源數組拷貝的起始索引
    • dest 目標數組
    • destPos 拷貝到目標數組的起始索引
    • length 拷貝元素的個數
      src源數組,起始索引為srcPos,個數為length,復制到起始索引為destPosdest目標數組。

    比如:

    int[] srcArray = new int[]{1,2,3,4,5,6};
    int[] desArray = new int[5];
    System.arraycopy(srcArray,1,desArray,2,3);
    System.out.println("desArray: " + Arrays.toString(desArray));
    

    輸出:

    [0, 0, 2, 3, 4]
    

    Arrays.copyOf

    Arrays.copyOf本質也是調用System.arraycopy方法:

     public static int[] copyOf(int[] original, int newLength) {
        int[] copy = new int[newLength];
        System.arraycopy(original, 0, copy, 0,
                         Math.min(original.length, newLength));
        return copy;
    }
    

    首先創建一個新的數組copy,將original數組全部復制給copy數組。

    主要字段:

    // 底層數組
    transient Object[] elementData;
    // 數組個數大小
    private int size;
    // 默認空數組
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    
    • ArrayList是基于數組的一個實現,elementData就是底層的數組。
    • size 是記錄數組的個數。

    構造方法

    ArrayList()

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

    無參構造方法,創建數據直接賦值一個空數組

    ArrayList(int initialCapacity)

    賦一個初始化容量initialCapacity:

    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);
        }
    }
    
    • 初始化容量initialCapacity大于零,新建長度initialCapacity的數組。
    • 初始化容量initialCapacity等于零,新建一個空數組。

    添加數據

    添加數據有兩個方法:

    • add(E e) 直接添加在數組尾部。
    • add(int index, E element) 根據下標添加數據。

    add(E e)

    在列表尾部添加數據:

    /**
     * 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;
    }
    

    ensureCapacityInternal 判斷添加數據后的容量是否足夠,如果不夠,做擴容操作。

    private void ensureCapacityInternal(int minCapacity) {
      ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }
    
    private static int calculateCapacity(Object[] elementData, int minCapacity) {
      if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
          return Math.max(DEFAULT_CAPACITY, minCapacity);
      }
      return minCapacity;
    }
    
    private void ensureExplicitCapacity(int minCapacity) {
      modCount++;
    
      // overflow-conscious code
      if (minCapacity - elementData.length > 0)
          grow(minCapacity);
    }
    

    ensureCapacityInternal 作用是判斷容量當前容量是否足夠存放新的數據,如果不夠就做擴容操作。

    calculateCapacity計算容量,如果數組為null,返回minCapacity10的最大值,否則返回minCapacity。這個方法就是返回數組的大小。

    調用無參構造方法ArrayList(),再調用add()方法,首先數組容量會變成10。這也是為什么無參構造方法ArrayList()上面有會有注解Constructs an empty list with an initial capacity of ten.

    ensureExplicitCapacity 判斷需要的容量minCapacity大于當前數組的長度elementData.length,將會做擴容處理,也是調用grow方法:

    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        // 新長度是原來長度的 1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            // 新長度比需要長度更小,賦值給新長度
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // 拷貝數組到新的長度數組
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
    

    group 主要做了兩件事:

    • 長度擴大到原來的 1.5倍
    • 拷貝數組到新長度的數組

    做完判斷是否要做擴容之后,直接在size位置上賦值要添加的元素,然后size再自增。

    elementData[size++] = e;
    

    add(E e)流程總結

    • 判斷數據容量是否足夠,如果是空數組,返回10,其他容量返回當前數組size + 1
    • 返回容量和當前數組長度對比,小于做擴容處理。
    • 擴容長度為原來長度的1.5倍,將數組賦值給長度為原來數組1.5倍的新數組。
    • 在數組的最末尾size賦值。

    add(int index, E element)

    此添加數據是在指定的下標添加數據。

    public void add(int index, E element) {
        // 下標是否越界
        rangeCheckForAdd(index);
        // 判斷是否要擴容
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        // 復制i到size的數據到i+1 到size +1
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }
    

    add(int index, E element)index下標添加數據,

    • 首先判斷index 是否在0 ~size之間。
    • 判斷是否要擴容,需要擴容,進行1.5倍擴容。
    • 數據遷移,把index以后的數據全部往后移動一位。
    • 賦值index 下標數據。

    獲取數據

    獲取數據只有通過數組下標獲取數據 get(int index)

    public E get(int index) {
      //檢查是否超過數組范圍 
      rangeCheck(index);
      
      return elementData(index);
    }
    
    @SuppressWarnings("unchecked")
    E elementData(int index) {
        // 通過下標獲取數據 
        return (E) elementData[index];
    }
    

    這里獲取數據就比較簡單:

    • 檢查下標是否超過數組范圍。
    • 通過下標訪問數據。

    刪除數據

    remove(Object o)

    刪除列表中第一個匹配的元素:

    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;
    }
    

    判斷要刪除數據是否為null:

    • 為空,判斷elementData[index]是否為空。
    • 不為空,判斷元素equals是否匹配elementData[index]

    上面判斷都為true時,調用fastRemove方法:

    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
    }
    

    移動數組數據,index+1 以及之后的數據往前移動一位,最后一位size-1賦值為null

    remove(int index)

    根據index下標刪除數據。

    public E remove(int index) {
        // 是否越界 
        rangeCheck(index);
    
        modCount++;
        E oldValue = 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;
    }
    

    總結

    • 數組的擴容、添加和刪除都需要用到System.arraycopy方法,System.arraycopy是將src源數組,起始索引為srcPos,個數為length,復制到起始索引為destPosdest目標數組。
    • ArrayList主要是基于Object[] elementData動態數組實現。
    • 調用構造方法,無參的就賦值一個空數組,有初始容量的就賦值一個初始容量。
    • add 添加數組首先判斷是否需要擴容,需要擴容,長度擴大成原來的1.5倍。
      • add(E e) 在size賦值添加數據
      • add(int index, E element) 將數組從index往后移動一位,新數據添加到index上。
    • 獲取數據get(int index)利用數組的特定,根據下標獲取數據。
    • remove(int index)index之后的數據全部往前移動一位,size - 1賦為null
    posted @ 2022-06-28 10:26  小碼code  閱讀(174)  評論(2編輯  收藏  舉報
    国产美女a做受大片观看