技術文章 » 老猿說說-ArrayList

老猿說說-ArrayList

2020-10-11 16:00:18

1 概述

ArrayList 整體架構比較簡單，就是一個陣列結構
比如：長度為10的陣列，從1開始計數，index表示陣列的下標，從0開始計數，

elementData表示陣列本身，原始碼中除了這兩個概念，還有以下三個基本概念：

  • DEFAULT_CAPACITY表示陣列的初始大小，預設是10,這個數位要記住；
  • size表示當前陣列的大小，型別int,沒有使用volatile修飾，非執行緒安全的；
  • modCount統計當前陣列被修改的版本次數，陣列結構有變動，就會+1。
類註釋

看原始碼，首先要看類註釋，我們看看類註釋上面都說了什麼，如下：

  • 允許 put null值，會自動擴容；
  • size、isEmpty、get、set、add等方法時間複雜度都是O(1);
    除了上述註釋中提到的4點，初始化、擴容的本質、迭代器等問題也經常被問，接下來我們從原始碼出發，——解析。

2 原始碼解析

2.1 初始化

我們有三種初始化辦法：無引數直接初始化、指定大小初始化、指定初始資料初始化，原始碼如

private static final ObjectD DEFAULTCAPACITY_EMPTY_ELEMENTDATA = 0;
  //無引數直接初始化，陣列大小為空
  public ArrayList(){
    this.elementData=DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
  }
  //指定初始資料初始化
  public ArrayList(Collection<? extends E> c){
      //elementData是儲存陣列的容器，預設為null
      elementData=c.toArray();
      //如果給定的集合（c)資料有值
      if((size=elementData.length)!=0){
        //c.toArray might(incorrectly)not return Object[](see 6260652)
        //如果集合元素型別不是Object型別，我們會轉成Object
      if(elementData.getClass()!=Object[].class){
        elementData=Arrays.copyOf(elementData,size,Object].class);
      }
    }else{
      //給定集合（c)無值，則預設空陣列
      this.elementData=EMPTY_ELEMENTDATA
    }
  }
}

除了原始碼的中文註釋，我們補充兩點：

  1. ArrayList無參構造器初始化時，預設大小是空陣列，並不是大家常說的10,10是在第一次add的時候擴容的陣列值。
  2. 指定初始資料初始化時，我們發現一個這樣子的註釋see6260652,這是Java的一個
    bug,意思是當給定集合內的元素不是Object型別時，我們會轉化成Object的型別。一般情
    況下都不會觸發此bug,只有在下列場景下才會觸發：ArrayList初始化之後（ArrayList元素非Object型別）,再次呼叫toArray方法，得到Object陣列，並且往Object陣列賦值時，
    官方檢視檔案地址：https://bugs.java.com/bugdatabase/view_bug.do?bug_id=6260652,問題在Java9中被解決。

2.2 新增和擴容實現

新增就是往陣列中新增元素，主要分成兩步

  • 判斷是否需要擴容，如果需要執行擴容操作；
  • 直接賦值。

兩步原始碼體現如下：

public boolean add(E e){
  //確保陣列大小是否足夠，不夠執行擴容，size為當前陣列的大小
  ensureCapacitylnternal(size+1);//Increments modCount!!
  //直接賦值，執行緒不安全的
  elementData[size++]=e;
  return true;
}

我們先看下擴容（ensureCapacitylnternal)的原始碼：

private void ensureCapacitylnternal(int minCapacity){
  //如果初始化陣列大小時，有給定初始值，以給定的大小為準，不走if邏輯
  if(elementData==DEFAULTCAPACITY_EMPTY_ELEMENTDATA){
    minCapacity=Math.max(DEFAULT_CAPACITY,minCapacity);
  }
  //確保容積足夠
  ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity){
  //記錄陣列被修改
  modCount++;
  //如果我們期望的最小容量大於目前陣列的長度，那麼就擴容
  if(minCapacity-elementData.length>0)
    grow(minCapacity);
}

//擴容，並把現有資料拷貝到新的陣列裡面去
private void grow(int minCapacity){
  int oldCapacity = elementData.length;
  //oldCapacity>>1是把oldCapacity除以2的意思
  int newCapacity=oldCapacity+(oldCapacity>>1);
  //如果擴容後的值<我們的期望值，擴容後的值就等於我們的期望值
  if(newCapacity-minCapacity<0)
    newCapacity = minCapacity;
  //如果擴容後的值>jvm所能分配的陣列的最大值，那麼就用Integer的最大值
  if(newCapacity-MAX_ARRAY_SIZE>0)
    elementData=Arrays.copyOf(elementData,newCapacity);
}

註解應該比較詳細，我們需要注意的四點是：

  1. 擴容的規則並不是翻倍，是原來容量大小+容量大小的一半，直白來說，擴容後的大小是原
    來容量的1.5倍；
  2. ArrayList中的陣列的最大值是Integer.MAX_VALUE,超過這個值，JVM就不會給陣列分配
    記憶體空間了。
  3. 新增時，並沒有對值進行嚴格的校驗，所以ArrayList是允許null值的。

從新增和擴容原始碼中，下面這點值得我們借鑑：

  • 原始碼在擴容的時候，有陣列大小溢位意識，就是說擴容後陣列的大小下界不能小於0,上界不能大於Integer的最大值，這種意識我們可以學習

擴容完成之後，賦值是非常簡單的，直接往陣列上新增元素即可：elementData[size++]=e
也正是通過這種簡單賦值，沒有任何鎖控制，所以這裡的操作是執行緒不安全的

2.3 擴容的本質

擴容是通過這行程式碼來實現的：Arrays.copyOf(elementData,newCapacity);這行程式碼描述的
本質是陣列之間的拷貝，擴容是會先新建一個符合我們預期容量的新陣列，然後把老陣列的資料
拷貝過去，我們通過System.arraycopy方法進行拷貝，此方法是native的方法，原始碼如下：

/**
*@param src 被拷貝的陣列
*@param srcPos 從陣列那裡開始
*@param dest 目標陣列
*@param destPos從目標陣列那個索引位置開始拷貝
*@param length 拷貝的長度
*此方法是沒有返回值的，通過dest的參照進行傳值
*/
public static native void arraycopy(Object src, int srcPos,Object dest, int destPos,int length);

我們可以通過下面這行程式碼進行呼叫，newElementData表示新的陣列：

System.arraycopy(elementData,0,newElementData,0,Math.min(elementData.length,newCapcity));

2.4 刪除

ArrayList刪除元素有很多種方式，比如根據陣列索引刪除、根據值刪除或批次刪除等等，原理
和思路都差不多，我們選取根據值刪除方式來進行原始碼說明：

public boolean remove(Object o) {
  //如果要刪除的值是null,找到第一個值是null的刪除
  if(o==null){
    for(int index=0;index<size;index++)
      if(elementData[index]==null){
        fastRemove(index)
        return true
      }
  }else{
    //如果要刪除的值不為null,找到第一個和要刪除的值相等的刪除
    for(int index=0;index<size;index++)
      //這裡是根據 equals來判斷值相等的，相等後再根據索引位置進行刪除
      if(o.equals(elementData[index]){
        fastRemove(index)
        return true;
      }
  }
  return false
}

我們需要注意的兩點是：

  1. 新增的時候是沒有對null進行校驗的，所以刪除的時候也是允許刪除null值的；
  2. 找到值在陣列中的索引位置，是通過equals來判斷的，如果陣列元素不是基本型別，需要我們關注equals的具體實現。

上面程式碼已經找到要刪除元素的索引位置了，下面程式碼是根據索引位置進行元素的刪除：

private void fastRemove(int index){
  //記錄陣列的結構要發生變動了
  nodCount++;
  //numMoved表示刪除index位置的元素後，需要從index後移動多少個元素到前面去
  //減1的原因，是因為size從1開始算起，index從0開始算起
  int numMoved=size-index-1;
  if(numMoved>0)
    //從index+1位置開始被拷貝，拷貝的起始位置是index,長度是numMoved
    System.arraycopy(elementData, index+1, elementData, index, numMoved);
  //陣列最後一個位置賦值null,幫助GC
  elementData[--size] = null;
}

從原始碼中，我們可以看出，某一個元素被刪除後，為了維護陣列結構，我們都會把陣列後面的元素往前移動

2.5 迭代器

如果要自己實現迭代器，實現java.util.lterator類就好了，ArrayList也是這樣做的，我們來看下迭代器的幾個總要的引數

int cursor;//迭代過程中，下一個元素的位置，預設從0開始。
int lastRet=-1;//新增場景：表示上一次迭代過程中，索引的位置；刪除場景：為-1。
int expectedModCount=modCount;//expectedModCount表示迭代過程中，期望的版本號

迭代器一般來說有三個方法

  • hasNext 還有沒有值可以迭代
  • next 如果有值可以迭代，迭代的值是多少
  • remove 刪除當前迭代的值

我們來分別看下三個方法的原始碼：

hasNext
public boolean hasNext0{
  return cursor!=size;//cursor表示下一個元素的位置，size表示實際大小，如果兩者相等，說明已經到末尾
}
next
public E next(){
  //迭代過程中，判斷版本號有無被修改，有被修改，拋ConcurrentModificationException異常
  checkForComodification();
  //本次迭代過程中，元素的索引位置
  int i=cursor;
  if(i>=size)
    throw new NoSuchElementException();
  Object[] elementData = Array List. this. elementData;
  if(i>=elementData.length)
    throw new ConcurrentModificationException0;
  //下一次迭代時，元素的位置，為下一次迭代做準備
  cursor=i+1;
  //返回元素值
  return (E)elementData[lastRet=i];
}
  //版本號比較
final void checkForComodification(){
  if(modCount!=expectedModCount)
    throw new ConcurrentModificationException0;
}

從原始碼中可以看到，next方法就幹了兩件事情，第一是檢驗能不能繼續迭代，第二是找到迭代的值，併為下一次迭代做準備（cursor+1)。

remove
public void remove(){
  //如果上一次操作時，陣列的位置已經小於0了，說明陣列已經被刪除完了
  if(lastRet<0)
    throw new IllegalStateException();
  checkForComodification();
  try {
    ArrayList.this.remove(lastRet);
    cursor=lastRet;
    //-1表示元素已經被刪除，這裡也防止重複刪除
    lastRet=-1;
    //刪除元素時modCount的值已經發生變化，在此賦值給expectedModCount
    //這樣下次迭代時，兩者的值是一致的了
    expectedModCount=modCount;
  } catch (IndexOutOfBoundsException ex){
    throw new ConcurrentModificationException();
  }
}

這裡我們需要注意的兩點是：

  • lastRet=-1的操作目的，是防止重複刪除操作
  • 刪除元素成功，陣列當前modCount就會發生變化，這裡會把expectedModCount重新
    賦值，下次迭代時兩者的值就會一致了

2.6 時間複雜度

從我們上面新增或刪除方法的原始碼解析，對陣列元素的操作，只需要根據陣列索引，直接新增和
刪除，所以時間複雜度是O(1)

2.7 執行緒安全

我們需要強調的是，只有當ArrayList作為共用變數時，才會有執行緒安全問題，當ArrayList是
方法內的區域性變數時，是沒有執行緒安全的問題的
ArrayList有執行緒安全問題的本質，是因為ArrayList自身的elementData、size、modConut
在進行各種操作時，都沒有加鎖，而且這些變數的型別並非是可見（volatile)的，所以如果多
個執行緒對這些變數進行操作時，可能會有值被覆蓋的情況。
類註釋中推薦我們使用Collections#synchronizedList來保證執行緒安全，SynchronizedList是
通過在每個方法上面加上鎖來實現，雖然實現了執行緒安全，但是效能大大降低，具體實現原始碼：

public boolean add(E e){
  synchronized(mutex){//synchronized是一種輕量鎖，mutex表示一個當前SynchronizedList
    return c.add(e);
  }
}

總結

本文從ArrayList整體架構出發，落地到初始化、新增、擴容、刪除、迭代等核心原始碼實現，我
們發現ArrayList其實就是圍繞底層陣列結構，各個API都是對陣列的操作進行封裝，讓使用者
無需感知底層實現，只需關注如何使用即可。