老猿說說-ArrayList

1 概述

ArrayList 整體架構(gòu)比較簡單，就是一個數(shù)組結(jié)構(gòu)
比如：長度為10的數(shù)組，從1開始計數(shù)，index表示數(shù)組的下標，從0開始計數(shù)，

elementData表示數(shù)組本身，源碼中除了這兩個概念，還有以下三個基本概念：

  • DEFAULT_CAPACITY表示數(shù)組的初始大小，默認是10,這個數(shù)字要記住；
  • size表示當(dāng)前數(shù)組的大小，類型int,沒有使用volatile修飾，非線程安全的；
  • modCount統(tǒng)計當(dāng)前數(shù)組被修改的版本次數(shù)，數(shù)組結(jié)構(gòu)有變動，就會+1。
類注釋

看源碼，首先要看類注釋，我們看看類注釋上面都說了什么，如下：

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

2 源碼解析

2.1 初始化

我們有三種初始化辦法：無參數(shù)直接初始化、指定大小初始化、指定初始數(shù)據(jù)初始化，源碼如

private static final ObjectD DEFAULTCAPACITY_EMPTY_ELEMENTDATA = 0;
  //無參數(shù)直接初始化，數(shù)組大小為空
  public ArrayList(){
    this.elementData=DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
  }
  //指定初始數(shù)據(jù)初始化
  public ArrayList(Collection<? extends E> c){
      //elementData是保存數(shù)組的容器，默認為null
      elementData=c.toArray();
      //如果給定的集合（c)數(shù)據(jù)有值
      if((size=elementData.length)!=0){
        //c.toArray might(incorrectly)not return Object[](see 6260652)
        //如果集合元素類型不是Object類型，我們會轉(zhuǎn)成Object
      if(elementData.getClass()!=Object[].class){
        elementData=Arrays.copyOf(elementData,size,Object].class);
      }
    }else{
      //給定集合（c)無值，則默認空數(shù)組
      this.elementData=EMPTY_ELEMENTDATA
    }
  }
}

除了源碼的中文注釋，我們補充兩點：

  1. ArrayList無參構(gòu)造器初始化時，默認大小是空數(shù)組，并不是大家常說的10,10是在第一次add的時候擴容的數(shù)組值。
  2. 指定初始數(shù)據(jù)初始化時，我們發(fā)現(xiàn)一個這樣子的注釋see6260652,這是Java的一個
    bug,意思是當(dāng)給定集合內(nèi)的元素不是Object類型時，我們會轉(zhuǎn)化成Object的類型。一般情
    況下都不會觸發(fā)此bug,只有在下列場景下才會觸發(fā)：ArrayList初始化之后（ArrayList元素非Object類型）,再次調(diào)用toArray方法，得到Object數(shù)組，并且往Object數(shù)組賦值時，
    官方查看文檔地址：https://bugs.java.com/bugdatabase/view_bug.do?bug_id=6260652,問題在Java9中被解決。

2.2 新增和擴容實現(xiàn)

新增就是往數(shù)組中添加元素，主要分成兩步

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

兩步源碼體現(xiàn)如下：

public boolean add(E e){
  //確保數(shù)組大小是否足夠，不夠執(zhí)行擴容，size為當(dāng)前數(shù)組的大小
  ensureCapacitylnternal(size+1);//Increments modCount!!
  //直接賦值，線程不安全的
  elementData[size++]=e;
  return true;
}

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

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

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

//擴容，并把現(xiàn)有數(shù)據(jù)拷貝到新的數(shù)組里面去
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所能分配的數(shù)組的最大值，那么就用Integer的最大值
  if(newCapacity-MAX_ARRAY_SIZE>0)
    elementData=Arrays.copyOf(elementData,newCapacity);
}

注解應(yīng)該比較詳細，我們需要注意的四點是：

  1. 擴容的規(guī)則并不是翻倍，是原來容量大小+容量大小的一半，直白來說，擴容后的大小是原
    來容量的1.5倍；
  2. ArrayList中的數(shù)組的最大值是Integer.MAX_VALUE,超過這個值，JVM就不會給數(shù)組分配
    內(nèi)存空間了。
  3. 新增時，并沒有對值進行嚴格的校驗，所以ArrayList是允許null值的。

從新增和擴容源碼中，下面這點值得我們借鑒：

  • 源碼在擴容的時候，有數(shù)組大小溢出意識，就是說擴容后數(shù)組的大小下界不能小于0,上界不能大于Integer的最大值，這種意識我們可以學(xué)習(xí)

擴容完成之后，賦值是非常簡單的，直接往數(shù)組上添加元素即可：elementData[size++]=e
也正是通過這種簡單賦值，沒有任何鎖控制，所以這里的操作是線程不安全的

2.3 擴容的本質(zhì)

擴容是通過這行代碼來實現(xiàn)的：Arrays.copyOf(elementData,newCapacity);這行代碼描述的
本質(zhì)是數(shù)組之間的拷貝，擴容是會先新建一個符合我們預(yù)期容量的新數(shù)組，然后把老數(shù)組的數(shù)據(jù)
拷貝過去，我們通過System.arraycopy方法進行拷貝，此方法是native的方法，源碼如下：

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

我們可以通過下面這行代碼進行調(diào)用，newElementData表示新的數(shù)組：

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

2.4 刪除

ArrayList刪除元素有很多種方式，比如根據(jù)數(shù)組索引刪除、根據(jù)值刪除或批量刪除等等，原理
和思路都差不多，我們選取根據(jù)值刪除方式來進行源碼說明：

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++)
      //這里是根據(jù) equals來判斷值相等的，相等后再根據(jù)索引位置進行刪除
      if(o.equals(elementData[index]){
        fastRemove(index)
        return true;
      }
  }
  return false
}

我們需要注意的兩點是：

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

上面代碼已經(jīng)找到要刪除元素的索引位置了，下面代碼是根據(jù)索引位置進行元素的刪除：

private void fastRemove(int index){
  //記錄數(shù)組的結(jié)構(gòu)要發(fā)生變動了
  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);
  //數(shù)組最后一個位置賦值null,幫助GC
  elementData[--size] = null;
}

從源碼中，我們可以看出，某一個元素被刪除后，為了維護數(shù)組結(jié)構(gòu)，我們都會把數(shù)組后面的元素往前移動

2.5 迭代器

如果要自己實現(xiàn)迭代器，實現(xiàn)java.util.lterator類就好了，ArrayList也是這樣做的，我們來看下迭代器的幾個總要的參數(shù)

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

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

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

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

hasNext
public boolean hasNext0{
  return cursor!=size;//cursor表示下一個元素的位置，size表示實際大小，如果兩者相等，說明已經(jīng)到末尾
}
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方法就干了兩件事情，第一是檢驗?zāi)懿荒芾^續(xù)迭代，第二是找到迭代的值，并為下一次迭代做準備（cursor+1)。

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

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

  • lastRet=-1的操作目的，是防止重復(fù)刪除操作
  • 刪除元素成功，數(shù)組當(dāng)前modCount就會發(fā)生變化，這里會把expectedModCount重新
    賦值，下次迭代時兩者的值就會一致了

2.6 時間復(fù)雜度

從我們上面新增或刪除方法的源碼解析，對數(shù)組元素的操作，只需要根據(jù)數(shù)組索引，直接新增和
刪除，所以時間復(fù)雜度是O(1)

2.7 線程安全

我們需要強調(diào)的是，只有當(dāng)ArrayList作為共享變量時，才會有線程安全問題，當(dāng)ArrayList是
方法內(nèi)的局部變量時，是沒有線程安全的問題的
ArrayList有線程安全問題的本質(zhì)，是因為ArrayList自身的elementData、size、modConut
在進行各種操作時，都沒有加鎖，而且這些變量的類型并非是可見（volatile)的，所以如果多
個線程對這些變量進行操作時，可能會有值被覆蓋的情況。
類注釋中推薦我們使用Collections#synchronizedList來保證線程安全，SynchronizedList是
通過在每個方法上面加上鎖來實現(xiàn)，雖然實現(xiàn)了線程安全，但是性能大大降低，具體實現(xiàn)源碼：

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

總結(jié)

本文從ArrayList整體架構(gòu)出發(fā)，落地到初始化、新增、擴容、刪除、迭代等核心源碼實現(xiàn)，我
們發(fā)現(xiàn)ArrayList其實就是圍繞底層數(shù)組結(jié)構(gòu)，各個API都是對數(shù)組的操作進行封裝，讓使用者
無需感知底層實現(xiàn)，只需關(guān)注如何使用即可。

最后編輯于 ：
?著作權(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)容