老猿說說-ArrayList-有解無憂

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

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

ArrayList無參構造器初始化時，默認大小是空陣列，并不是大家常說的10,10是在第一次add的時候擴容的陣列值，
指定初始資料初始化時，我們發現一個這樣子的注釋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.5倍；
ArrayList中的陣列的最大值是Integer.MAX_VALUE,超過這個值，JVM就不會給陣列分配
記憶體空間了，
新增時，并沒有對值進行嚴格的校驗，所以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
}

我們需要注意的兩點是：

新增的時候是沒有對null進行校驗的，所以洗掉的時候也是允許洗掉null值的；
找到值在陣列中的索引位置，是通過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表示實際大小，如果兩者相等，說明已經到末尾
}

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都是對陣列的操作進行封裝，讓使用者
無需感知底層實作，只需關注如何使用即可，

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/168467.html

標籤：AI

上一篇：洛谷CSP-J/S2020初賽模擬部分題解

下一篇：php 中使用JWT進行身份驗證