這一篇開始說ArrayList

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

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

一、基本性質(zhì)

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

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

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

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

4、對存儲的元素無限制，允許null元素。

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

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

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

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

二、構(gòu)造方法

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

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

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

jdk1.7的，相對1.6版本，引入了一個新的常量EMPTY_ELEMENTDATA，它是一個空數(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的，相對1.7版本，又引入了一個新的常量DEFAULTCAPACITY_EMPTY_ELEMENTDATA ，它也是一個空數(shù)組，因此容量也為0。至于兩個空數(shù)組有什么區(qū)別，看下面一點說的。

/** 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; 
} 

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

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

順便吐槽下：jdk這個類維護者，你能不能改下默認構(gòu)造方法上的注釋啊，默認構(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ù)組，一個小小的優(yōu)化 
 } else { 
  throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); 
 } 
} 

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

// jdk1.6，兩個構(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，這里一次性擴容了1個，后續(xù)再按照通用擴容策略執(zhí)行擴容操作 
 
  List<String> lb = new ArrayList<String>(); // lb.elementData = new Object[10], lb.elementData.length = 10 
  lb.add("111"); // lb.elementDate.length = 10，這里沒有進行擴容，后續(xù)再按照通用擴容策略執(zhí)行擴容操作 
 } 
} 
 
// jdk1.7，兩個構(gòu)造在第一次進行添加時才看得出區(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，這里一次性擴容了1個，后續(xù)再按照通用擴容策略執(zhí)行擴容操作 
 
  List<String> lb = new ArrayList<>(); // lb.elementData = EMPTY_ELEMENTDATA, lb.elementData.length = 0 
  lb.add("111"); // lb.elementDate.length = 10，這里一次性擴容了10個，后續(xù)再按照通用擴容策略執(zhí)行擴容操作 
 } 
} 
 
// 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，這里一次性擴容了1個，后續(xù)再按照通用擴容策略執(zhí)行擴容操作 
 
  List<String> lb = new ArrayList<>(); // lb.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA, lb.elementData.length = 0 
  lb.add("111"); // lb.elementDate.length = 10，這里一次性擴容了10個，后續(xù)再按照通用擴容策略執(zhí)行擴容操作 
 } 
} 

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

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

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

// 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)于中間這行注釋，可以看下這篇博文

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

三、確保容量方法（擴容方法）：ensureCapacity/ensureCapacityInternal

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

擴容方法四個位置用到：兩個add方法，兩個addAll方法，一個反序列化方法，還有就是手動擴容方法ensureCapacity（稱之為手動，是因為此方法是public的，可以外部手動調(diào)用）。在1.6版本是只有這個手動的方法，內(nèi)部自動操作也是調(diào)用這個方法，1.7開始進行了區(qū)分，并且進一步改進了擴容操作。

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

// 手動擴容方法（可以外部調(diào)用，不過大多數(shù)情況都是List<?> = new ArrayList<>()，這樣是調(diào)用不到這個方法的） 
// 這個方法只是簡單區(qū)別下list是不是通過 new ArrayList() 來創(chuàng)建的，這一點前面說了 
// 如果是，則嘗試最小擴容10個，不是則嘗試擴容指定個，具體也是通過內(nèi)部擴容方法完成容量確保 
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)部擴容相關(guān)的幾個方法的代碼 
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型溢出，直接報錯 
  throw new OutOfMemoryError(); 
 return (minCapacity > MAX_ARRAY_SIZE) ? 
  Integer.MAX_VALUE : 
  MAX_ARRAY_SIZE; 
} 

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

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的方法只是簡單進行了邏輯上的操作，沒有過多考慮int型溢出的問題，從1.7（上面貼的是1.8的）開始對這個進行了完善。

先仔細看看1.6的問題，整體來說都是int型溢出的問題。

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

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

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

所以1.7版本對上面兩個問題做了修改。

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

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

還有一個問題就是，MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8。這個是1.7開始才有的，注釋說這個是因為在一些虛擬機的數(shù)組實現(xiàn)中，會有array header這個保留部分，所以數(shù)組最大長度并不是實際的Integer.MAX_VALUE。這個在1.8自帶的HotSpot上測試（環(huán)境Win7 64位，Java HotSpot(TM) 64-Bit Server VM (build 25.111-b14, mixed mode)），準確值應該是Integer.MAX_VALUE -

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

測試下實際MAX_ARRAY_SIZE（都是64bit的）
jdk1.8 Integer,MAX_VALUE - 2，超過這個值（實際上也只有兩個數(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，使用這個值能夠成功創(chuàng)建數(shù)組（使用boolean數(shù)組）

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

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

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

四、常用方法

ArrayList提供的public方法的實現(xiàn)，基本上都有利用數(shù)組隨機訪問特性，以及System.arraycopy/Arrays.copyOf數(shù)組快速復制，進行加速。

1、來自List接口中的方法

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

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

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

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

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

// 此方法就是一個簡單的數(shù)組批量刪除方法，并且刪除后剩余的元素相對順序不變，且全部往前移動 
// 之所以使用try-fianlly是因為c.contains可能會拋出異常(c == null，或者實現(xiàn)類中不允許null），導致ArrayList沒有能更新size以及對底層數(shù)組進行整理， 
//  使用finally可以保證保證這一點，并且與父類AbstractCollection中已經(jīng)實現(xiàn)的removeAll/retainAll方法的行為的一致性 
// 通過finally中的代碼可以看出，這些沒有進行判斷的元素會全部保留。 
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)：繼承使用父類AbstractList中的方法，算法和判斷兩個數(shù)組內(nèi)容是否全等一樣，就是用的是迭代器而不是傳統(tǒng)for循環(huán)，此方法用得很少，所以沒用數(shù)組特性進一步優(yōu)化。
int hashCode()：同上，繼承使用父類AbstractList中的方法，hashCode算法也不特殊，線性結(jié)構(gòu)常用的hash = 31 * hash + e.hashCode。
Object[] toArray()：直接使用Arrays.copyOf拷貝一份elementData數(shù)組作為返回值，也就是數(shù)組不共享但是元素共享。
<T> T[] toArray(T[] a)：此方法說明下，覺得行為有些不太友好。

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

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

覺得不友好的就是給定數(shù)組大了的這種情況，因為它會多覆蓋掉一個值，注釋中說這么做的原因是“當調(diào)用者知道列表不包含任何空元素時，這在確定列表的長度時非常有用”，這是個坑啊。下面的demo簡單展示了這個坑。

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] 
 
  // 也可以使用等長數(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] 
 
  // 除非你清楚，否則不要像下面這么做，因為s20[10]被此方法設置為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] 
 } 
} 

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

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

這里不說。集合類這部分要說，也放在以后一起說

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

以上就是本文的全部內(nèi)容，希望對大家的學習有所幫助，也希望大家多多支持腳本之家。

最新評論