基于ArrayList常用方法的源碼全面解析

更新時(shí)間：2017年06月27日 10:26:35 投稿：jingxian

下面小編就為大家?guī)硪黄贏rrayList常用方法的源碼全面解析。小編覺得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧

我相信幾乎所有的同學(xué)在大大小小的筆試、面試過程中都會(huì)被問及ArrayList與LinkedList之間的異同點(diǎn)。稍有準(zhǔn)備的人這些問題早已爛熟于心，前者基于數(shù)組實(shí)現(xiàn)，后者基于鏈表實(shí)現(xiàn)；前者隨機(jī)方法速度快刪除和插入指定位置速度慢，后者隨機(jī)訪問速度慢刪除和插入指定位置速度快；兩者都是線程不安全的；列表與數(shù)組之間的區(qū)別等等。

列表與數(shù)組之間很大的一個(gè)區(qū)別就是：數(shù)組在其初始化就需要給它確定大小不能動(dòng)態(tài)擴(kuò)容，而列表則可以動(dòng)態(tài)擴(kuò)容。ArrayList是基于數(shù)組實(shí)現(xiàn)的，那么它是如何實(shí)現(xiàn)的動(dòng)態(tài)擴(kuò)容呢？

對(duì)于ArrayList的初始化有三種方式：

對(duì)于第一種默認(rèn)的構(gòu)造方法，ArrayList并沒有初始化容量大小，而是將列表的元素?cái)?shù)據(jù)引用指向了一個(gè)空數(shù)組。

private transient Object[] elementData;
private static final Object[] EMPTY_ELEMENTDATA = {};

//1.ArrayList默認(rèn)構(gòu)造方法
public ArrayList() {  
  super();
  this.elementData = EMPTY_ELEMENTDATA;
}

與JDK1.6不同的是，JDK1.6即時(shí)是在調(diào)用默認(rèn)的構(gòu)造方法時(shí)，也會(huì)初始化容量大小，JDK1.7當(dāng)然會(huì)帶來一定的好處，如果初始化而不使用就白白浪費(fèi)了存儲(chǔ)空間，等到添加的時(shí)候再初始化容量大小即可。

//JDK1.6 ArrayList
public ArrayList() {
  this(10);
}

對(duì)于第二種構(gòu)造方法，則直接創(chuàng)建一個(gè)指定大小的數(shù)組，將列表的元素?cái)?shù)組引用指向它。

//2.ArrayList帶有初始化大小的構(gòu)造方法
public ArrayList(int initialCapacity) {
  super();
  if (initialCapacity < 0)
    throw new IllegalArgumentException("Illegal Capacity: "+
                      initialCapacity);
  this.elementData = new Object[initialCapacity];
}

第三種構(gòu)造方法，能將一個(gè)集合作為參數(shù)傳遞，但集合中的元素必須繼承自ArrayList中的元素。

//3.可將一個(gè)集合作為ArrayList的參數(shù)構(gòu)造成ArrayList
public ArrayList(Collection<? extends E> c) {
  elementData = c.toArray();  //將集合轉(zhuǎn)換為數(shù)組
  size = elementData.length;  //集合中的元素大小
  // c.toArray might (incorrectly) not return Object[] (see 6260652) 這里是個(gè)bug，參考http://bugs.java.com/bugdatabase/view_bug.do?bug_id=6260652
  if (elementData.getClass() != Object[].class)
    elementData = Arrays.copyOf(elementData, size, Object[].class);
}

上面提到了一個(gè)bug，也就是說將一個(gè)集合轉(zhuǎn)換為數(shù)組的時(shí)候可能錯(cuò)誤地不會(huì)返回Object[]，舉例說明。

package com.algorithm.sort;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * bug編號(hào):6260652。toArray有可能不會(huì)返回Object[]
 * Created by yulinfeng on 2017/6/26.
 */
public class Test {
  public static void main(String[] args) {
    correctly();
    incorrectly();
  }
  
  /**
   * 返回Object[]
   */
  private static void correctly() {
    List<String> list = new ArrayList<String>();
    list.add("test");
    System.out.println(list.getClass());
    Object[] objArray = list.toArray();
    System.out.println(objArray.getClass());
  }
  /**
   * 不返回Object[]
   */
  private static void incorrectly() {
    List<String> list = Arrays.asList("test");
    System.out.println(list.getClass());
    Object[] objArray = list.toArray();
    System.out.println(objArray.getClass());
  }
}

運(yùn)行結(jié)果：

上面的這個(gè)例子就說明了toArray并不一定總是返回Object[]，返回的Object[]時(shí)，Object元素就不能插入，故JDK在“6260652”中修復(fù)了這個(gè)bug。

接下來看元素插入以及刪除等其它方法。

//ArrayList#add
public boolean add(E e) {
  ensureCapacityInternal(size + 1); //確保容量是否充足
  elementData[size++] = e;  //將元素添加至數(shù)組
  return true;
}

//ArrayList#ensureCapacityInternal
private void ensureCapacityInternal(int minCapacity) {
  if (elementData == EMPTY_ELEMENTDATA) {
    minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);   //如果此時(shí)還沒有初始化列表容量大小，則對(duì)其初始化，默認(rèn)容量為10
  }
  ensureExplicitCapacity(minCapacity); //檢查容量是否充足
}

//ArrayList#ensureEcplicitCapacity
private void ensureExplicitCapacity(int minCapacity) {
  modCount++;  //注意此變量
  if (minCapacity - elementData.length > 0)
    grow(minCapacity);  //容量不夠則進(jìn)行擴(kuò)容
}

在ensureEcplicitCapacity方法中有一個(gè)modCount（modify count）變量進(jìn)行了自增。

protected transient int modCount = 0;

這個(gè)變量不僅在add方法中會(huì)自增，只要是在增加或者刪除等對(duì)ArrayList結(jié)構(gòu)產(chǎn)生了變化都會(huì)記錄加1，這樣做的原因和多線程下Iterator迭代器遍歷有關(guān)。在AbstractList$Itr中也有一個(gè)變量與之對(duì)應(yīng)。

//AbstractList$Itr
int expectedModCount = modCount;

在AbstractList$Itr#next中調(diào)用了checkForComodification方法。

//AbstractList$Itr#checkForComodification
final void checkForComodification() {
  if (modCount != expectedModCount)
    throw new ConcurrentModificationException();
}

如果當(dāng)前運(yùn)行環(huán)境是單線程，不論對(duì)列表進(jìn)行何種操作何時(shí)增加、修改、刪除等，excpectedModCount總是會(huì)等于modCount，但是如果當(dāng)前運(yùn)行環(huán)境是多線程，很有可能一個(gè)線程在迭代遍歷，而另一個(gè)線程在對(duì)其進(jìn)行新增或者修改等，JDK則不允許這么做，此時(shí)則會(huì)拋出ConcurrentModificationException異常，這就是modCount變量在此起的作用。

回到ArrayList#add方法，當(dāng)列表容量不足時(shí)，此時(shí)會(huì)調(diào)用grow方法進(jìn)行擴(kuò)容。

//ArrayList#grow
private void grow(int minCapacity) {
  int oldCapacity = elementData.length;
  int newCapacity = oldCapacity + (oldCapacity >> 1);  //擴(kuò)容策略為，每次新增容量的大小為舊容量的一半。也就是說如果默認(rèn)容量為10，則第一次擴(kuò)容大小為10 / 2 = 5，第二次擴(kuò)容大小為15 / 2 = 7。
  if (newCapacity - minCapacity < 0)
    newCapacity = minCapacity;  //擴(kuò)容策略擴(kuò)得太小
  if (newCapacity - MAX_ARRAY_SIZE > 0)  //擴(kuò)容策略擴(kuò)得太大，大于最大數(shù)組大小時(shí)，最多等于Integer.MAX_VALUE
    newCapacity = hugeCapacity(minCapacity);
  
  elementData = Arrays.copyOf(elementData, newCapacity);
}

ArrayList獲取指定索引位置的元素get方法。

public E get(int index) {
  rangeCheck(index);  //檢查索引是否越界
  return elementData(index);
}

由于ArrayList是由基于數(shù)組實(shí)現(xiàn)，故此方法較為簡(jiǎn)單，判斷是否越界，沒有則根據(jù)數(shù)組下標(biāo)來索引返回元素即可。remove方法刪除指定位置的元素?！?/p>

//ArrayList#remove
public E remove(int index) {
  rangeCheck(index);  //檢查索引是否越界
  modCount++;  //記錄modCount，上面已提及
  E oldValue = elementData(index);  //取出指定索引元素
  int numMoved = size - index - 1;  //移動(dòng)的元素個(gè)數(shù)
  if (numMoved > 0)
    System.arraycopy(elementData, index+1, elementData, index, numMoved);
  elementData[--size] = null; //將最后一個(gè)數(shù)組元素置為null，方便GC

  return oldValue;
}

代碼比較簡(jiǎn)單，同樣也體現(xiàn)了基于數(shù)組實(shí)習(xí)的ArrayList在刪除指定元素時(shí)的效率問題。

以上這篇基于ArrayList常用方法的源碼全面解析就是小編分享給大家的全部?jī)?nèi)容了，希望能給大家一個(gè)參考，也希望大家多多支持腳本之家。

您可能感興趣的文章: