這一篇開(kāi)始說(shuō)ArrayList

參考代碼為jdk1.6_45 jdk1.7_80 jdk1.8_111中的源碼，對(duì)比閱讀，發(fā)現(xiàn)修改的問(wèn)題以及改進(jìn)點(diǎn)。

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable

一、基本性質(zhì)

1、底層使用原生數(shù)組實(shí)現(xiàn)，實(shí)現(xiàn)RandomAccess接口，可以隨機(jī)訪問(wèn)，隨機(jī)訪問(wèn)指的是下標(biāo)索引操作index(i)的時(shí)間復(fù)雜度是O(1)。

size、isEmpty、get、set、iterator和listIterator操作在O(1)內(nèi)完成，add(e)操作平均在O(1)內(nèi)完成，即添加n個(gè)元素需要O(n)時(shí)間（這個(gè)是Collection.add，是在尾部添加注意區(qū)分下List.add(index, e)）。其他操作基本都是O(n)內(nèi)完成。ArrayList與LinkedList實(shí)現(xiàn)相比，O(n)的各個(gè)方法的時(shí)間復(fù)雜度的常數(shù)因子更小。

2、因?yàn)榈讓訑?shù)組 elementData 的容量是不能改變的，所以容量不夠時(shí)，需要把 elementData 換成一個(gè)更大的數(shù)組，這個(gè)過(guò)程叫作擴(kuò)容。實(shí)際的元素的數(shù)量size，總是不會(huì)超過(guò)底層數(shù)組的容量 elementData.length，因?yàn)閿U(kuò)容需要申請(qǐng)更大的內(nèi)存，并且需要原來(lái)數(shù)組的進(jìn)行一次復(fù)制，所以擴(kuò)容是個(gè)耗時(shí)的操作。在添加大量元素之前，使用者最好是預(yù)估一個(gè)大致的數(shù)量，手動(dòng)調(diào)用ensureCapacity進(jìn)行一次擴(kuò)容操作，避免一個(gè)個(gè)添加導(dǎo)致頻繁擴(kuò)容影響性能。

3、ArrayList是未同步的，多線程并發(fā)讀寫(xiě)時(shí)需要外部同步，如果不外部同步，那么可以使用Collections.synchronizedList方法對(duì)ArrayList的實(shí)例進(jìn)行一次封裝，或者使用Vector。

4、對(duì)存儲(chǔ)的元素?zé)o限制，允許null元素。

5、ArrayList的iterator和listIterator方法返回的迭代器是快速失敗的，也就是如果在創(chuàng)建迭代器之后的任何時(shí)間被結(jié)構(gòu)性修改，除了通過(guò)迭代器自己的remove或add方法之外，迭代器將直接拋出一個(gè)ConcurrentModificationException，從而達(dá)到快速失敗fail-fast的目的，盡量避免不確定的行為。

ArrayList的迭代器的快速失敗行為不能被嚴(yán)格保證，并發(fā)修改時(shí)它會(huì)盡量但不100%保證拋出ConcurrentModificationException。因此，依賴于此異常的代碼的正確性是沒(méi)有保障的，迭代器的快速失敗行為應(yīng)該僅用于檢測(cè)bug。

6、實(shí)現(xiàn)clone接口，可以調(diào)用其clone方法（雖然clone()是Object中的方法，但是它是protected，使用子類(lèi)的clone()必須在子類(lèi)中覆蓋此方法）。clone方法復(fù)制一個(gè)ArrayList，底層數(shù)組elementData不共享，但是實(shí)際的元素還是共享的。
不過(guò)clone是ArrayList中覆蓋的，不屬于List中的方法，因此常見(jiàn)的聲明形式
     List<String> strs = new ArrayList<>()；
聲明出來(lái)的變量不能直接使用clone方法，本身也用得極少。

7、實(shí)現(xiàn)Serializable接口，可以被序列化。ArrayList"實(shí)現(xiàn)"了自定義序列化方法，這么做主要是為了節(jié)省空間 。對(duì)于占用空間的大頭——元素list，僅僅序列化實(shí)際size大小的元素，同時(shí)不序列化對(duì)于新對(duì)象無(wú)用屬性的——來(lái)自父類(lèi)AbstractList的modCount。ArrayList的實(shí)際size不會(huì)超過(guò)底層數(shù)組的length，大多數(shù)情況下比底層數(shù)組length小，使用默認(rèn)序列化的話，會(huì)直接序列化整個(gè)底層數(shù)組，序列化后字節(jié)流會(huì)變大，浪費(fèi)空間。

二、構(gòu)造方法

1、默認(rèn)構(gòu)造方法，ArrayList()

關(guān)于默認(rèn)構(gòu)造方法，你可能在別的地方看見(jiàn)過(guò)這種話：無(wú)參構(gòu)造方法（默認(rèn)構(gòu)造方法）構(gòu)造的ArrayList的底層數(shù)組elementData大?。ㄈ萘浚┠J(rèn)為10。這里告訴你，這不一定是對(duì)的。這句話在1.6版本中是對(duì)的（更之前的版本我沒(méi)看），從1.7開(kāi)始這句話就有問(wèn)題了。下面我貼出了三個(gè)版本的代碼：
jdk1.6的，初始化成10個(gè)容量。

// jdk1.6的 
/** Constructs an empty list with an initial capacity of ten. */ 
 public ArrayList() { 
 this(10); 
} 

jdk1.7的，相對(duì)1.6版本，引入了一個(gè)新的常量EMPTY_ELEMENTDATA，它是一個(gè)空數(shù)組，因此容量為0。

// jdk1.7的 
/** Shared empty array instance used for empty instances. */ 
private static final Object[] EMPTY_ELEMENTDATA = {}; 
 
... 
 
/** Constructs an empty list with an initial capacity of ten. */ 
public ArrayList() { 
 super(); 
 this.elementData = EMPTY_ELEMENTDATA; 
} 

jdk1.8的，相對(duì)1.7版本，又引入了一個(gè)新的常量DEFAULTCAPACITY_EMPTY_ELEMENTDATA ，它也是一個(gè)空數(shù)組，因此容量也為0。至于兩個(gè)空數(shù)組有什么區(qū)別，看下面一點(diǎn)說(shuō)的。

/** Shared empty array instance used for empty instances. */ 
private static final Object[] EMPTY_ELEMENTDATA = {}; 
 
/** 
 * Shared empty array instance used for default sized empty instances. We 
 * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when 
 * first element is added. 
 */ 
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; 
 
... 
 
/** Constructs an empty list with an initial capacity of ten. */ 
public ArrayList() { 
 this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; 
} 

對(duì)比下可以看出：jdk1.6的無(wú)參構(gòu)造方法（默認(rèn)構(gòu)造方法）構(gòu)造的ArrayList的底層數(shù)組elementData大?。ㄈ萘浚┠J(rèn)為10；從1.7開(kāi)始，無(wú)參構(gòu)造方法構(gòu)造的ArrayList的底層數(shù)組elementData大小默認(rèn)為0。
java集合類(lèi)在jdk1.7版本基本上都有一種改動(dòng)：懶初始化。懶初始化指的是默認(rèn)構(gòu)造方法構(gòu)造的集合類(lèi)，占據(jù)盡可能少的內(nèi)存空間（對(duì)于ArrayList來(lái)說(shuō)，使用空數(shù)組來(lái)占據(jù)盡量少的空間，不使用null是為了避免null判斷），在第一次進(jìn)行包含有添加語(yǔ)義的操作時(shí)，才進(jìn)行真正的初始化工作。

1.7開(kāi)始的ArrayList，默認(rèn)構(gòu)造方法構(gòu)造的實(shí)例，底層數(shù)組是空數(shù)組，容量為0，在進(jìn)行第一次add/addAll等操作時(shí)才會(huì)真正給底層數(shù)組賦非empty的值。如果add/addAll添加的元素小于10，則把elementData數(shù)組擴(kuò)容為10個(gè)元素大小，否則使用剛好合適的大?。ɡ?，第一次addAll添加6個(gè)，那么擴(kuò)容為10個(gè)，第一次添加大于10個(gè)的，比如24個(gè)，擴(kuò)容為24個(gè)，剛好合適）；1.8版本，默認(rèn)構(gòu)造的實(shí)例這個(gè)行為沒(méi)有改變，只是用的數(shù)組名字變了。

順便吐槽下：jdk這個(gè)類(lèi)維護(hù)者，你能不能改下默認(rèn)構(gòu)造方法上的注釋啊，默認(rèn)構(gòu)造方法的行為都改變了，你注釋還是用之前的?。?！

2、帶初始容量的構(gòu)造方法，public ArrayList(int initialCapacity)

// 1.6 
public ArrayList(int initialCapacity) { 
 super(); 
 if (initialCapacity < 0) 
  throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); 
 this.elementData = new Object[initialCapacity]; 
} 
 
// 1.7 跟1.6的一樣 
public ArrayList(int initialCapacity) { 
 super(); 
 if (initialCapacity < 0) 
  throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); 
 this.elementData = new Object[initialCapacity]; 
} 
 
// 1.8 
public ArrayList(int initialCapacity) { 
 if (initialCapacity > 0) { 
  this.elementData = new Object[initialCapacity]; 
 } else if (initialCapacity == 0) { 
  this.elementData = EMPTY_ELEMENTDATA; // 重用空數(shù)組，一個(gè)小小的優(yōu)化 
 } else { 
  throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); 
 } 
} 

678三個(gè)版本的這個(gè)構(gòu)造方法的實(shí)際行為基本一致：如果initialCapacity >= 0，把底層數(shù)組elementData賦值為一個(gè)大小為initialCapacity的數(shù)組，數(shù)組的所有元素都是默認(rèn)值null。1.8稍微進(jìn)行了一點(diǎn)優(yōu)化，也是賦值為空數(shù)組，但是重用了常量對(duì)象。
下面寫(xiě)個(gè)簡(jiǎn)單的例子看一個(gè)細(xì)微的區(qū)別。

// jdk1.6，兩個(gè)構(gòu)造的區(qū)別很明顯 
public class TestArrayList { 
 public static void main(String[] args) { 
  List<String> la = new ArrayList<String>(0); // la.elementData = new Object[0], la.elementData.length = 0 
  la.add("111"); // la.elementDate.length = 1，這里一次性擴(kuò)容了1個(gè)，后續(xù)再按照通用擴(kuò)容策略執(zhí)行擴(kuò)容操作 
 
  List<String> lb = new ArrayList<String>(); // lb.elementData = new Object[10], lb.elementData.length = 10 
  lb.add("111"); // lb.elementDate.length = 10，這里沒(méi)有進(jìn)行擴(kuò)容，后續(xù)再按照通用擴(kuò)容策略執(zhí)行擴(kuò)容操作 
 } 
} 
 
// jdk1.7，兩個(gè)構(gòu)造在第一次進(jìn)行添加時(shí)才看得出區(qū)別 
public class TestArrayList { 
 public static void main(String[] args) { 
  List<String> la = new ArrayList<>(0); // la.elementData = new Object[0], la.elementData.length = 0 
  la.add("111"); // la.elementDate.length = 1，這里一次性擴(kuò)容了1個(gè)，后續(xù)再按照通用擴(kuò)容策略執(zhí)行擴(kuò)容操作 
 
  List<String> lb = new ArrayList<>(); // lb.elementData = EMPTY_ELEMENTDATA, lb.elementData.length = 0 
  lb.add("111"); // lb.elementDate.length = 10，這里一次性擴(kuò)容了10個(gè)，后續(xù)再按照通用擴(kuò)容策略執(zhí)行擴(kuò)容操作 
 } 
} 
 
// jdk1.8，同1.7 
public class TestArrayList { 
 public static void main(String[] args) { 
  List<String> la = new ArrayList<>(0); // la.elementData = EMPTY_ELEMENTDATA, la.elementData.length = 0 
  la.add("111"); // la.elementDate.length = 1，這里一次性擴(kuò)容了1個(gè)，后續(xù)再按照通用擴(kuò)容策略執(zhí)行擴(kuò)容操作 
 
  List<String> lb = new ArrayList<>(); // lb.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA, lb.elementData.length = 0 
  lb.add("111"); // lb.elementDate.length = 10，這里一次性擴(kuò)容了10個(gè)，后續(xù)再按照通用擴(kuò)容策略執(zhí)行擴(kuò)容操作 
 } 
} 

jdk1.6中new ArrayList<?>()跟new ArrayList<?>(10)的行為是一模一樣的，所以跟new ArrayList<?>(0)有很明顯區(qū)別，這個(gè)好理解 。從1.7版本開(kāi)始，new ArrayList<>()和new ArrayList<>(0)，雖然創(chuàng)建后底層內(nèi)容和容量都一樣，但是實(shí)際的行為有些細(xì)小的差別，那就是這兩個(gè)在第一次自動(dòng)擴(kuò)容時(shí)策略不一樣。不過(guò)這一點(diǎn)影響比較小，基本不影響使用。
1.8中使用兩個(gè)空數(shù)組，正如注釋所說(shuō)的，是在優(yōu)化（避免創(chuàng)建無(wú)用的空數(shù)組）的同時(shí)，保留其擴(kuò)容初始策略區(qū)別。只用一個(gè)空數(shù)組就不能再優(yōu)化的同時(shí)，繼續(xù)保持這個(gè)小區(qū)別了。

3、Collection拷貝構(gòu)造方法，public ArrayList(Collection<? extends E> c)

678三個(gè)版本的關(guān)系和第2點(diǎn)一樣。

// jdk 1.6 
public ArrayList(Collection<? extends E> c) { 
 elementData = c.toArray(); 
 size = elementData.length; 
 // c.toArray might (incorrectly) not return Object[] (see 6260652) 
 if (elementData.getClass() != Object[].class) 
  elementData = Arrays.copyOf(elementData, size, Object[].class); 
} 
 
// jdk 1.7 
public ArrayList(Collection<? extends E> c) { 
 elementData = c.toArray(); 
 size = elementData.length; 
 // c.toArray might (incorrectly) not return Object[] (see 6260652) 
 if (elementData.getClass() != Object[].class) 
  elementData = Arrays.copyOf(elementData, size, Object[].class); 
} 
 
// jdk 1.8 
public ArrayList(Collection<? extends E> c) { 
 elementData = c.toArray(); 
 if ((size = elementData.length) != 0) { 
  // c.toArray might (incorrectly) not return Object[] (see 6260652) 
  if (elementData.getClass() != Object[].class) 
   elementData = Arrays.copyOf(elementData, size, Object[].class); 
 } else { 
  // replace with empty array. 
  this.elementData = EMPTY_ELEMENTDATA; 
 } 
} 

關(guān)于中間這行注釋?zhuān)梢钥聪逻@篇博文

此構(gòu)造方法會(huì)有和Array.copyOf/System.arraycopy一樣的問(wèn)題，那就是它只是新建一個(gè)elementData數(shù)組，數(shù)組的內(nèi)容對(duì)應(yīng)相等，但是不拷貝實(shí)際的元素，實(shí)際的元素占據(jù)的內(nèi)存空間還是共享的。

三、確保容量方法（擴(kuò)容方法）：ensureCapacity/ensureCapacityInternal

提前聲明下：這兩個(gè)方法只是確保容量，不一定會(huì)擴(kuò)容，但是為了好理解，下面的文字中所說(shuō)的"擴(kuò)容"指的就是這兩個(gè)方法。
因?yàn)樵臄?shù)組的容量不能改變，要改變數(shù)組的容量，只能是新建一個(gè)數(shù)組，并把原來(lái)數(shù)組的內(nèi)容復(fù)制到新數(shù)組對(duì)應(yīng)位置上去。數(shù)組拷貝使用的是Arrays.copyOf，底層用的是System.arraycopy，比循環(huán)賦值效率高。擴(kuò)容示意圖如下。

擴(kuò)容方法四個(gè)位置用到：兩個(gè)add方法，兩個(gè)addAll方法，一個(gè)反序列化方法，還有就是手動(dòng)擴(kuò)容方法ensureCapacity（稱之為手動(dòng)，是因?yàn)榇朔椒ㄊ莗ublic的，可以外部手動(dòng)調(diào)用）。在1.6版本是只有這個(gè)手動(dòng)的方法，內(nèi)部自動(dòng)操作也是調(diào)用這個(gè)方法，1.7開(kāi)始進(jìn)行了區(qū)分，并且進(jìn)一步改進(jìn)了擴(kuò)容操作。

下面的是jdk1.8的代碼，1.7的和1.8的基本相同，唯一的一點(diǎn)區(qū)別就是1.8用兩個(gè)空數(shù)組，導(dǎo)致這里的空數(shù)組的名字不一樣，兩個(gè)版本的代碼可以看作是一樣的。

// 手動(dòng)擴(kuò)容方法（可以外部調(diào)用，不過(guò)大多數(shù)情況都是List<?> = new ArrayList<>()，這樣是調(diào)用不到這個(gè)方法的） 
// 這個(gè)方法只是簡(jiǎn)單區(qū)別下list是不是通過(guò) new ArrayList() 來(lái)創(chuàng)建的，這一點(diǎn)前面說(shuō)了 
// 如果是，則嘗試最小擴(kuò)容10個(gè)，不是則嘗試擴(kuò)容指定個(gè)，具體也是通過(guò)內(nèi)部擴(kuò)容方法完成容量確保 
public void ensureCapacity(int minCapacity) { 
 int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) 
  // any size if not default element table 
  ? 0 
  // larger than default for default empty table. It's already 
  // supposed to be at default size. 
  : DEFAULT_CAPACITY; 
 
 if (minCapacity > minExpand) { 
  ensureExplicitCapacity(minCapacity); 
 } 
} 
 
// 下面是內(nèi)部擴(kuò)容相關(guān)的幾個(gè)方法的代碼 
private void ensureCapacityInternal(int minCapacity) { 
 if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { 
  minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); 
 } 
 
 ensureExplicitCapacity(minCapacity); 
} 
 
private void ensureExplicitCapacity(int minCapacity) { 
 modCount++; 
 
 // overflow-conscious code 考慮int型溢出 
 if (minCapacity - elementData.length > 0) 
  grow(minCapacity); 
} 
 
private void grow(int minCapacity) { 
 // overflow-conscious code 考慮int型溢出 
 int oldCapacity = elementData.length; 
 int newCapacity = oldCapacity + (oldCapacity >> 1); 
 if (newCapacity - minCapacity < 0) 
  newCapacity = minCapacity; 
 if (newCapacity - MAX_ARRAY_SIZE > 0) 
  newCapacity = hugeCapacity(minCapacity); 
 // minCapacity is usually close to size, so this is a win: 
 elementData = Arrays.copyOf(elementData, newCapacity); 
} 
 
private static int hugeCapacity(int minCapacity) { 
 if (minCapacity < 0) // overflow int型溢出，直接報(bào)錯(cuò) 
  throw new OutOfMemoryError(); 
 return (minCapacity > MAX_ARRAY_SIZE) ? 
  Integer.MAX_VALUE : 
  MAX_ARRAY_SIZE; 
} 

下面這是1.6的相關(guān)代碼，可以對(duì)比看下：

public void ensureCapacity(int minCapacity) { 
 modCount++; 
 int oldCapacity = elementData.length; 
 if (minCapacity > oldCapacity) { 
  Object oldData[] = elementData; 
  int newCapacity = (oldCapacity * 3)/2 + 1; 
  if (newCapacity < minCapacity) 
   newCapacity = minCapacity; 
  // minCapacity is usually close to size, so this is a win: 
  elementData = Arrays.copyOf(elementData, newCapacity); 
 } 
} 

區(qū)別就是：1.6的方法只是簡(jiǎn)單進(jìn)行了邏輯上的操作，沒(méi)有過(guò)多考慮int型溢出的問(wèn)題，從1.7（上面貼的是1.8的）開(kāi)始對(duì)這個(gè)進(jìn)行了完善。

先仔細(xì)看看1.6的問(wèn)題，整體來(lái)說(shuō)都是int型溢出的問(wèn)題。

1、沒(méi)考慮入?yún)inCapacity可能因?yàn)閕nt溢出變?yōu)樨?fù)數(shù)。這個(gè)方法可以外部手動(dòng)調(diào)用，手動(dòng)擴(kuò)容傳入負(fù)數(shù)這個(gè)肯定是應(yīng)該攔截掉的。但是自動(dòng)擴(kuò)容會(huì)因?yàn)閕nt溢出產(chǎn)生負(fù)數(shù)，碰到這種情況時(shí)應(yīng)該特殊處理，而不是什么都不做，等著后面拋出一個(gè)ArrayIndexOutOfBoundsException。

2、就是這句代碼不太好，過(guò)早溢出
     int newCapacity = (oldCapacity * 3)/2 + 1;
雖然上面這行代碼和1.7開(kāi)始的oldCapacity + (oldCapacity >> 1) 看上去一樣，都是相當(dāng)于1.5倍，但實(shí)際上是有區(qū)別的。兩個(gè)區(qū)別，第一個(gè)小區(qū)別是jdk1.6的那種乘除運(yùn)算的數(shù)學(xué)結(jié)果比后面一個(gè)大1比如oldCapacity=10，1.6的算法得到16，1.7開(kāi)始的算法得到15，這個(gè)影響不大；第二個(gè)區(qū)別就是兩者在數(shù)字比較大是運(yùn)算結(jié)果不一樣，比如oldCapacity=10^9，這個(gè)數(shù)和Integer.MAX_VALUE位數(shù)一樣，用1.6的算法得到的會(huì)是錯(cuò)誤的-647483647，用1.7的則是正確的1500000000，這時(shí)候明明可以1.5倍擴(kuò)容，但是jdk1.6卻用的是按需擴(kuò)容。

在計(jì)算機(jī)里面對(duì)于int型的兩個(gè)不同的數(shù)a和b，有
     a-b>0 不等價(jià)于 a>b
因?yàn)?，a-b>0會(huì)被int溢出影響，a>b不會(huì)受int溢出影響。無(wú)符號(hào)的int型中a-b>0是一定成立的；有符號(hào)的int型，負(fù)數(shù)可以看成是正數(shù)的溢出，假設(shè)a = Integer.MAX_VALUE + 10，b = Integer.MAX_VALUE - 10，很明顯a是負(fù)數(shù)，b是正數(shù)，運(yùn)行一遍a>b得到false，再運(yùn)行一遍a-b得到的是20，a-b>0得到true。因此對(duì)于int型，a>b和a-b>0在if判斷中有不同的功能，前者是純粹比較大小，正數(shù)一定大于負(fù)數(shù)；后者可以判斷溢出，正數(shù)不一定大于負(fù)數(shù)。

所以1.7版本對(duì)上面兩個(gè)問(wèn)題做了修改。

1、從1.7開(kāi)始將內(nèi)部擴(kuò)容和外部可以調(diào)用的擴(kuò)容方法分開(kāi)了，通過(guò)源碼（上面貼的是1.8的代碼，可以看出是一樣的）可以看出：外部調(diào)用的手動(dòng)擴(kuò)容方法ensureCapacity要多一個(gè)判斷條件 minCapacity > minExpand，這個(gè)判斷條件攔截掉負(fù)數(shù)的minCapacity，這樣調(diào)用內(nèi)部擴(kuò)容ensureCapacityInternal方法時(shí)，minCapacity一定是正數(shù)；內(nèi)部擴(kuò)容方法直接就用minCapacity - elementData.length > 0判斷，此條件可以檢測(cè)出int型溢出，碰到溢出最后會(huì)拋出一個(gè)OOM錯(cuò)誤。jdk1.7用OOM，這比jdk1.6用ArrayIndexOutOfBoundsException更好，因?yàn)榇藭r(shí)數(shù)組大小超出了虛擬機(jī)對(duì)數(shù)組的限制，虛擬機(jī)無(wú)法處理這種情況了，拋出一個(gè)ERROR是合理的。

2、使用這行代碼
     newCapacity = oldCapacity + (oldCapacity >> 1);
這行不僅僅是是用位運(yùn)算加快執(zhí)行速度，上面說(shuō)了，這種做法才是對(duì)的，是真正的1.5倍。不僅僅因?yàn)槟且粋€(gè)大小的差別，更重要的是避免過(guò)早出現(xiàn)int溢出的情況，保證了內(nèi)部自動(dòng)擴(kuò)容會(huì)盡量按規(guī)定的策略執(zhí)行。同時(shí)整個(gè)擴(kuò)容處理流程中多增加了幾處if判斷，對(duì)各種情況處理更加完善。

還有一個(gè)問(wèn)題就是，MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8。這個(gè)是1.7開(kāi)始才有的，注釋說(shuō)這個(gè)是因?yàn)樵谝恍┨摂M機(jī)的數(shù)組實(shí)現(xiàn)中，會(huì)有array header這個(gè)保留部分，所以數(shù)組最大長(zhǎng)度并不是實(shí)際的Integer.MAX_VALUE。這個(gè)在1.8自帶的HotSpot上測(cè)試（環(huán)境Win7 64位，Java HotSpot(TM) 64-Bit Server VM (build 25.111-b14, mixed mode)），準(zhǔn)確值應(yīng)該是Integer.MAX_VALUE -

2.比這個(gè)值大就會(huì)出現(xiàn)OutOfMemoryError: Requested array size exceeds VM limit。此Error和hugeCapacity中拋出的OOM基本上差不多，這兩個(gè)跟一般的OOM還是有區(qū)別的。拋出這個(gè)異常時(shí)，一般是程序有問(wèn)題，此時(shí)虛擬機(jī)看看數(shù)組大小，就知道了它是不能完成這樣的內(nèi)存分配的，跟剩余的內(nèi)存空間大小沒(méi)關(guān)系。

測(cè)試下實(shí)際MAX_ARRAY_SIZE（都是64bit的）
jdk1.8 Integer,MAX_VALUE - 2，超過(guò)這個(gè)值（實(shí)際上也只有兩個(gè)數(shù)可選，Integer.MAX_VALUE和Integer.MAX_VALUE - 1）就拋出OutOfMemoryError: Requested array size exceeds VM limit
jdk1.7 Integer.MAX_VALUE - 2
jdk1.6 Integer.MAX_VALUE，使用這個(gè)值能夠成功創(chuàng)建數(shù)組（使用boolean數(shù)組）

在帶初始容量的構(gòu)造方法 public ArrayList(int initialCapacity) 中，并沒(méi)有判斷初始容量是否大于MAX_ARRAY_SIZE。個(gè)人覺(jué)得還是判斷下好，不判斷可能在擴(kuò)容時(shí)會(huì)有點(diǎn)問(wèn)題。下面給一組變量值大家試下，看下是不是真有問(wèn)題。

初始數(shù)組長(zhǎng)度 elementData.length = Integer.MAX_VALUE - 5 = 2147483642；
還要繼續(xù)添加的長(zhǎng)度 expand = Integer.MAX_VALUE - 2 = 2147483645；
最小容量 minCapacity = expand + elementData.length = -9；
ensureExplicitCapacity方法中 minCapacity - elementData.length = 2147483645 > 0，會(huì)繼續(xù)執(zhí)行g(shù)row方法；
grow方法中 newCapacity = elementData.length + (elementData.length >> 1) = -1073741833；
grow方法中的第一個(gè)if，newCapacity - minCapacity = -1073741824 < 0，執(zhí)行第一個(gè)if中的 newCapacity = minCapacity，newCapacity = -9；
grow方法中的第二個(gè)if，newCapacity - MAX_ARRAY_SIZE = -2147483648 < 0，不執(zhí)行第二個(gè)if中的語(yǔ)句；
執(zhí)行最后的Arrays.copyOf，因?yàn)閚ewCapacity = -9 < 0，會(huì)拋出異常NegativeArraySizeException。

grow方法中第二個(gè)if，如果newCapacity是負(fù)數(shù)，只有是-9到-1這幾個(gè)負(fù)數(shù)，才會(huì)不執(zhí)行hugeCapacity方法而是直接執(zhí)行Arrays.copyOf拋出異常。如果構(gòu)造方法中攔截判斷下是否大于MAX_ARRAY_SIZE，一開(kāi)始的數(shù)組長(zhǎng)度就限制在Integer.MAX_VALUE - 8，應(yīng)該是無(wú)法通過(guò)一個(gè)正數(shù)的expand，使得minCapacity在[-9,-1]內(nèi)。嚴(yán)格證明暫時(shí)給不出，實(shí)際運(yùn)行中由于內(nèi)存限制無(wú)法演示。

四、常用方法

ArrayList提供的public方法的實(shí)現(xiàn)，基本上都有利用數(shù)組隨機(jī)訪問(wèn)特性，以及System.arraycopy/Arrays.copyOf數(shù)組快速?gòu)?fù)制，進(jìn)行加速。

1、來(lái)自List接口中的方法

E get(int index)：這個(gè)沒(méi)啥說(shuō)的。
E set(int index, E element)：這個(gè)沒(méi)啥說(shuō)的。
void add(int index, E element)：這個(gè)內(nèi)部會(huì)進(jìn)行數(shù)組復(fù)制，復(fù)制原來(lái)index開(kāi)始的數(shù)組到 index+1 開(kāi)始的位置，因此在ArrayList中間add元素是比較慢的，平均下來(lái)是O(n)的時(shí)間。沒(méi)必要時(shí)盡量不使用這個(gè)方法，而是直接使用 add(e) 添加到尾部，add(e) 平均下來(lái)只會(huì)耗費(fèi)O(1)的時(shí)間，效率高很多。
簡(jiǎn)單畫(huà)了個(gè)圖，可以看下。

E remove(int index)：基本同上，會(huì)進(jìn)行數(shù)組復(fù)制，這是數(shù)組實(shí)現(xiàn)的list避免不了的問(wèn)題。注意下實(shí)現(xiàn)中的elementData[--size] = null; // clear to let GC do its work，這句讓list不引用元素，讓元素可以被回收（當(dāng)然，還得其他地方都不引用元素），避免集合類(lèi)“假刪除”造成內(nèi)存泄漏。
remove示意圖如下。

int indexOf(Object o)：此方法和下面的lastIndexOf方法會(huì)進(jìn)行null判斷，o == null則在遍歷時(shí)使用 == 進(jìn)行比較，o != null則在遍歷時(shí)使用equals方法進(jìn)行比較，所以使用時(shí)請(qǐng)注意下元素的equals方法。
int lastIndexOf(Object o)：同上。
boolean addAll(int index, Collection<? extends E> c)：elementData數(shù)組中插入c.toArray()數(shù)組，使用的System.arraycopy復(fù)制進(jìn)去。
ListIterator<E> listIterator(int index)：返回一個(gè)基于數(shù)組操作的ListIterator，ListIterator是Iterator的增強(qiáng)實(shí)現(xiàn)。傳統(tǒng)的Iterator只能往一個(gè)方向迭代，并且只能在迭代中進(jìn)行remove這一個(gè)寫(xiě)操作；ListIterator能夠雙向迭代，支持迭代時(shí)獲取下標(biāo)，并且能夠在迭代中進(jìn)行add和set操作。不過(guò)List這一系的迭代器弄得比較亂，抽象類(lèi)AbstractList中有一套，幾個(gè)主要實(shí)現(xiàn)類(lèi)ArrayList、LinkedList、Vector、CopyOnWriteArrayList中又各自有一套。父類(lèi)中那一套是通用的，各個(gè)具體的類(lèi)中的那一套，一般都是優(yōu)化過(guò)的，效率會(huì)提升一些，所以不用管父類(lèi)的迭代器了，那些雖然通用，但是效率不高，差不多過(guò)時(shí)了。jdk1.6的ArrayList是直接使用父類(lèi)Abstract中的通用的那一套，效率稍微低些。
ListIterator<E> listIterator()：就是new ListItr(0);
List<E> subList(int fromIndex, int toIndex)：返回此List的某一段的視圖，具體返回類(lèi)型是java.util.ArrayList$SubList這個(gè)內(nèi)部類(lèi)，ArrayList.subList是復(fù)用原ArrayList的elementdata數(shù)組，操作原數(shù)組也會(huì)對(duì)subList有影響。jdk1.6中是用父類(lèi)的這個(gè)方法，返回一個(gè)通用的java.util.SubLlist，1.7開(kāi)始使用的是java.util.ArrayList.SubList，直接操作ArrayList的數(shù)組，效率更高。雖然重寫(xiě)了一份功能幾乎一樣的代碼，但是作為一個(gè)基層的類(lèi)，效率還是很重要的。

2、來(lái)自Collection(Iteratable)接口的方法

Iterator<E> iterator()：返回一個(gè)內(nèi)部的實(shí)現(xiàn)類(lèi)，從jdk1.7開(kāi)始該實(shí)現(xiàn)類(lèi)使用數(shù)組的特性優(yōu)化實(shí)現(xiàn)Iterator的幾個(gè)方法，1.6返回的是父類(lèi)AbstractList中定義的一個(gè)List接口通用的迭代器。
int size()：直接返回屬性size
boolean isEmpty()：size == 0
boolean contains(Object o)：使用的是indexOf
boolean add(E e)：尾部添加，只用考慮是否擴(kuò)容，不擴(kuò)容時(shí)的插入不用考慮數(shù)組元素移動(dòng)的問(wèn)題，平均下來(lái)是O(1)的時(shí)間。這里可以簡(jiǎn)單證明下：初始a個(gè)容量，每次擴(kuò)容后是1.5倍，設(shè)為c；那么擴(kuò)容次數(shù)為x = O(logc(n))（c為底數(shù)）；擴(kuò)容移動(dòng)的元素個(gè)數(shù)，等比數(shù)列求和，為O(c^x) = O(n)；不擴(kuò)容時(shí)每個(gè)元素為O(1)，不擴(kuò)容總共消耗小于O(n)；總共耗時(shí)O(n)，平均耗時(shí)O(1)。
boolean remove(Object o)：移除所有“相等”的元素，此處相等和indexOf中的一樣，null使用 ==，非null使用equals。移除時(shí)使用的fastRemove(int index)跟remove(int index)行為一樣，因?yàn)槭莾?nèi)部使用，所以不用檢查邊界，而且返回void。
boolean containsAll(Collection<?> c)：繼承使用AbstractCollection中的方法，使用for-each挨個(gè)檢驗(yàn)contains。對(duì)于Iterable的實(shí)現(xiàn)類(lèi)，for-each是用Iterator實(shí)現(xiàn)的。在ArrayList這種基于數(shù)組的實(shí)現(xiàn)中，傳統(tǒng)for循環(huán)比Iterator要快，Iterator比直接數(shù)組下標(biāo)取值要多不少步驟，在N次簡(jiǎn)單循環(huán)這種狂飆cpu的操作中，每個(gè)步驟都是花時(shí)間的，所以Iterator（for-each循環(huán)）要慢。不夠估計(jì)是此方法用的不多，在ArrayList中沒(méi)有用數(shù)組的特性進(jìn)一步優(yōu)化此方法。1.7以后ArrayList中其余幾個(gè)All方法都重寫(xiě)了，就這個(gè)All方法還是用的父類(lèi)的。
boolean addAll(Collection<? extends E> c)：c.toArray，數(shù)組尾部追加數(shù)組，先確保容量，然后復(fù)制要add的數(shù)組就行。
boolean removeAll(Collection<?> c)：可以理解為差集操作，這個(gè)和下面的retainAll一起講，都是利用batchRemove方法，只是判斷是否刪除一個(gè)元素時(shí)行為相反。1.8在調(diào)用batchRemove進(jìn)行了null判斷，c == null會(huì)提前拋出NPE，1.6的是重用父類(lèi)AbstractCollection中的實(shí)現(xiàn)。

// 此方法就是一個(gè)簡(jiǎn)單的數(shù)組批量刪除方法，并且刪除后剩余的元素相對(duì)順序不變，且全部往前移動(dòng) 
// 之所以使用try-fianlly是因?yàn)閏.contains可能會(huì)拋出異常(c == null，或者實(shí)現(xiàn)類(lèi)中不允許null），導(dǎo)致ArrayList沒(méi)有能更新size以及對(duì)底層數(shù)組進(jìn)行整理， 
//  使用finally可以保證保證這一點(diǎn)，并且與父類(lèi)AbstractCollection中已經(jīng)實(shí)現(xiàn)的removeAll/retainAll方法的行為的一致性 
// 通過(guò)finally中的代碼可以看出，這些沒(méi)有進(jìn)行判斷的元素會(huì)全部保留。 
private boolean batchRemove(Collection<?> c, boolean complement) { 
 final Object[] elementData = this.elementData; 
 int r = 0, w = 0; 
 boolean modified = false; 
 try { 
  for (; r < size; r++) 
   if (c.contains(elementData[r]) == complement) 
    elementData[w++] = elementData[r]; 
 } finally { 
  // Preserve behavioral compatibility with AbstractCollection, 
  // even if c.contains() throws. 
  if (r != size) { 
   System.arraycopy(elementData, r, elementData, w, size - r); 
   w += size - r; 
  } 
  if (w != size) { 
   // clear to let GC do its work 
   for (int i = w; i < size; i++) 
    elementData[i] = null; 
   modCount += size - w; 
   size = w; 
   modified = true; 
  } 
 } 
 return modified; 
} 

boolean retainAll(Collection<?> c)：交集操作，上面removeAll已經(jīng)講了。
void clear()：for循環(huán)清空elementData數(shù)組，并把size置為0，不改變?nèi)萘俊?br /> boolean equals(Object o)：繼承使用父類(lèi)AbstractList中的方法，算法和判斷兩個(gè)數(shù)組內(nèi)容是否全等一樣，就是用的是迭代器而不是傳統(tǒng)for循環(huán)，此方法用得很少，所以沒(méi)用數(shù)組特性進(jìn)一步優(yōu)化。
int hashCode()：同上，繼承使用父類(lèi)AbstractList中的方法，hashCode算法也不特殊，線性結(jié)構(gòu)常用的hash = 31 * hash + e.hashCode。
Object[] toArray()：直接使用Arrays.copyOf拷貝一份elementData數(shù)組作為返回值，也就是數(shù)組不共享但是元素共享。
<T> T[] toArray(T[] a)：此方法說(shuō)明下，覺(jué)得行為有些不太友好。

public <T> T[] toArray(T[] a) { 
 if (a.length < size) 
  // Make a new array of a's runtime type, but my contents: 
  return (T[]) Arrays.copyOf(elementData, size, a.getClass()); 
 System.arraycopy(elementData, 0, a, 0, size); 
 if (a.length > size) 
  a[size] = null; 
 return a; 
} 

此方法很簡(jiǎn)單，分3種情況處理：給定數(shù)組空間小了，新建一樣大小數(shù)組并拷貝過(guò)去（新建操作是在Arrays.copyOf里面完成的）；剛好相等，直接拷貝就過(guò)去完事；給定數(shù)組大了，拷貝過(guò)去后，由于只覆蓋了原數(shù)組的前面一部分，再把接下來(lái)的一個(gè)元素變?yōu)閚ull。

覺(jué)得不友好的就是給定數(shù)組大了的這種情況，因?yàn)樗鼤?huì)多覆蓋掉一個(gè)值，注釋中說(shuō)這么做的原因是“當(dāng)調(diào)用者知道列表不包含任何空元素時(shí)，這在確定列表的長(zhǎng)度時(shí)非常有用”，這是個(gè)坑啊。下面的demo簡(jiǎn)單展示了這個(gè)坑。

public class TestArrayList { 
 public static void main(String[] args) { 
  List<String> sList = Arrays.asList("0", "1", "2", "3", "4", "5", "6", "7", "8", "9"); 
  // 推薦使用空數(shù)組 
  String[] s0 = {}; 
  System.err.println("s0 = " + Arrays.toString(sList.toArray(s0))); 
  // s0 = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] 
 
  // 也可以使用等長(zhǎng)數(shù)組 
  String[] s10 = new String[sList.size()]; 
  System.err.println("s10 = " + Arrays.toString(sList.toArray(s10))); 
  // s10 = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] 
 
  // 除非你清楚，否則不要像下面這么做，因?yàn)閟20[10]被此方法設(shè)置為null 
  String[] s20 = new String[20]; 
  s20[10] = "10"; 
  s20[11] = "11"; 
  s20[12] = "12"; 
  System.err.println("s20 = " + Arrays.toString(sList.toArray(s20))); 
  // s20 = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, null, 11, 12, null, null, null, null, null, null, null] 
 } 
} 

五、獨(dú)有的兩個(gè)方法
public void ensureCapacity(int minCapacity)：可以外部調(diào)用的手動(dòng)擴(kuò)容方法，在要添加大量元素之前，預(yù)估下容量，調(diào)用這個(gè)方法手動(dòng)擴(kuò)容，避免頻繁自動(dòng)擴(kuò)容降低性能。
public void trimToSize()：節(jié)省空間，使得elementData剛好容納下所有元素。

六、幾個(gè)jdk1.8新增的函數(shù)式、stream有關(guān)的方法

這里不說(shuō)。集合類(lèi)這部分要說(shuō)，也放在以后一起說(shuō)

簡(jiǎn)單總結(jié)下，jdk1.7版本對(duì)比1.6版本，三個(gè)改動(dòng)：
1、懶初始化，因此默認(rèn)構(gòu)造方法創(chuàng)建的是空數(shù)組，不再是10個(gè)大小的數(shù)組；
2、擴(kuò)容相關(guān)的完善；
3、一些方法不再直接使用父類(lèi)的通用實(shí)現(xiàn)，改為利用數(shù)組特性的更有效率的實(shí)現(xiàn)。
對(duì)比著看更容易發(fā)現(xiàn)問(wèn)題，也跟有收獲。

以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

最新評(píng)論