老猿說說-ArrayList

1 概述

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

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

DEFAULT_CAPACITY表示數(shù)組的初始大小，默認(rèn)是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ù)組的容器，默認(rèn)為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)無值区拳，則默認(rèn)空數(shù)組
      this.elementData=EMPTY_ELEMENTDATA
    }
  }
}

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

ArrayList無參構(gòu)造器初始化時意乓，默認(rèn)大小是空數(shù)組樱调，并不是大家常說的10,10是在第一次add的時候擴容的數(shù)組值。
指定初始數(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ù)組大小時眉撵，有給定初始值侦香，以給定的大小為準(zhǔn)落塑，不走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)該比較詳細(xì)散吵，我們需要注意的四點是：

擴容的規(guī)則并不是翻倍龙考，是原來容量大小+容量大小的一半，直白來說矾睦，擴容后的大小是原
來容量的1.5倍晦款；
ArrayList中的數(shù)組的最大值是Integer.MAX_VALUE,超過這個值，JVM就不會給數(shù)組分配
內(nèi)存空間了枚冗。
新增時缓溅，并沒有對值進行嚴(yán)格的校驗，所以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 目標(biāo)數(shù)組
*@param destPos從目標(biāo)數(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
}

我們需要注意的兩點是：

新增的時候是沒有對null進行校驗的妙真，所以刪除的時候也是允許刪除null值的缴允；
找到值在數(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;//迭代過程中，下一個元素的位置及皂，默認(rèn)從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)到末尾
}

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;
  //下一次迭代時，元素的位置庭呜，為下一次迭代做準(zhǔn)備
  cursor=i+1;
  //返回元素值
  return (E)elementData[lastRet=i];
}
  //版本號比較
final void checkForComodification(){
  if(modCount!=expectedModCount)
    throw new ConcurrentModificationException0;
}

從源碼中可以看到滑进，next方法就干了兩件事情，第一是檢驗?zāi)懿荒芾^續(xù)迭代募谎，第二是找到迭代的值扶关，并為下一次迭代做準(zhǔn)備（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)注如何使用即可捏浊。