Java基礎集合---ArrayList

ArrayList源碼解析

• 簡介

  ArrayList是基于數組實作的，是一個動态數組，其容量能自動增長，類似于C語言中的動态申請記憶體，動态增長記憶體。

  ArrayList不是線程安全的，隻能用在單線程環境下，多線程環境下可以考慮用Collections.synchronizedList(List l)函數傳回一個線程安全的ArrayList類，也可以使用concurrent并發包下的CopyOnWriteArrayList類。

  ArrayList實作了Serializable接口，是以它支援序列化，能夠通過序列化傳輸，實作了RandomAccess接口，支援快速随機通路，實際上就是通過下标序号進行快速通路，實作了Cloneable接口，能被克隆。

  *由add()方法中檢查擴容操作可以看出：ArrayList初始化時最好指定可預測的數組長度，避免擴容導緻系統消耗

• 構造函數

/**
 Constructs an empty list with an initial capacity of ten.
構造初始容量為10的空清單。
*/
public ArrayList() {
  this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

/**
     * Constructs an empty list with the specified initial capacity.
     *用指定的初始容量構造空清單。
     * @param  initialCapacity  the initial capacity of the list
     初始容量清單的初始容量
     * @throws IllegalArgumentException if the specified initial capacity is negative
     指定的初始容量為負
     */
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);
        }
}

/**
     * Constructs a list containing the elements of the specified
     * collection, in the order they are returned by the collection's
     * iterator.
     *構造包含指定集合的元素的清單，按集合的疊代器傳回這些元素的順序
     * @param c the collection whose elements are to be placed into this list
     * @throws NullPointerException if the specified collection is null
     */
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;
    }
}

           

• 插入資料

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

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

  ensureCapacityInternal(size + 1);  // Increments modCount!!
  System.arraycopy(elementData, index, elementData, index + 1,
                   size - index);
  elementData[index] = element;
  size++;
}
           

• 擴容檢查

/**
 檢查arrayList數組是否需要擴容
 */ 
 private void ensureCapacityInternal(int minCapacity) {
   //目前數組是否是空數組
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
      //空數組，傳回預設長度
      minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    //檢查擴容
    ensureExplicitCapacity(minCapacity);
  }

  private void ensureExplicitCapacity(int minCapacity) {
    //記錄操作次數
    modCount++;

    // overflow-conscious code
    //如果長度-數組長度>0，進行擴容處理
    if (minCapacity - elementData.length > 0)
      grow(minCapacity);
  }
  /**
  * Increases the capacity to ensure that it can hold at least the
  * number of elements specified by the minimum capacity argument.
  *
  * @param minCapacity the desired minimum capacity
  */
  private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    //新的數組長度 = 舊長度+舊長度*0.5（即：arrayList預設擴容1.5倍）
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
      newCapacity = minCapacity;
    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);
  }
           

• 删除方法

• //根據下标删除
      public E remove(int index) {
        //檢查下标是否越界
          rangeCheck(index);
        //增加操作次數
          modCount++;
        //擷取下标對應的元素
          E oldValue = elementData(index);
         //資料移動量
         //将index+1及之後的元素向前移動一位 
         //例： size =10 目前數組最大index =9
         //對應index為0，1，2，3，4，5，6，7，8，9
         //index =2 則需要将index為3，4，5，6，7，8，9的資料向前移動一位
      	 //即：對應的移動量為 size-index-1 =7
          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;
      }
  
      //删除第一次出現的元素
      public boolean remove(Object o) {
        //判斷元素是否為null 如果為null 則删除第一個為null的元素下标
          if (o == null) {
              for (int index = 0; index < size; index++)
                //找出第一個為null的下标，根據下标進行删除
                  if (elementData[index] == null) {
                      fastRemove(index);
                      return true;
                  }
          } else {
              for (int index = 0; index < size; index++)
                //找出第一個元素為o的下标，根據下标進行删除
                  if (o.equals(elementData[index])) {
                      fastRemove(index);
                      return true;
                  }
          }
          return false;
      }
  	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
      }