ArrayList的非快速失敗機制和Vector與ArrayList的（基礎）分析

/**
* 1、copyOnWriteArrayList 如何實作（non-fastfail）非快速失敗機制？？？
* 2、Vector底層原始碼，主要看屬性，建構式、增刪改查方法、明白ArrayList與Vector之間的區別與聯系
* （底層資料結構、效率、擴容機制、是否執行緒安全）
*
*/

一、 ArrayList概述：

1、 ArrayList是基于陣列實作的，是一個動態陣列，其容量能自動增長，類似于C語言中的動態申請記憶體，動態增長記憶體，

2、 ArrayList不是執行緒安全的，只能用在單執行緒環境下，多執行緒環境下可以用Collections.synchronizedList(List l)函式回傳一個執行緒安全的ArrayList類，也可以使用concurrent并發包下的CopyOnWriteArrayList類，

3、 ArrayList實作了Serializable介面，因此它支持序列化，能夠通過序列化傳輸：該機制中，一個物件可以被表示為一個位元組序列，該位元組序列包括該物件的資料、有關物件的型別的資訊和存盤在物件中資料的型別，將序列化物件寫入檔案之后，可以從檔案中讀取出來，并且對它進行反序列化，也就是說，物件的型別資訊、物件的資料，還有物件中的資料型別可以用來在記憶體中新建物件，整個程序都是 Java 虛擬機（JVM）獨立的，也就是說，在一個平臺上序列化的物件可以在另一個完全不同的平臺上反序列化該物件，

5、實作了RandomAccess介面，支持快速隨機訪問，實際上就是通過下標序號進行快速訪問：
E elementData(int index) {
return (E) elementData[index];
}

6、實作了Cloneable介面，能被克隆：
public Object clone() {
try {
ArrayList<?> v = (ArrayList<?>) super.clone();
v.elementData = Arrays.copyOf(elementData, size);
v.modCount = 0;
return v;
} catch (CloneNotSupportedException e) {
// this shouldn't happen, since we are Cloneable
throw new InternalError(e);
}
}

7、 ArrayList是執行緒非安全的；每個ArrayList在添加大量元素前，應用程式也可以使用ensureCapacity操作來增加ArrayList實體的容量，這可以減少遞增式再分配的數量， 注意，此實作不是同步的，如果多個執行緒同時訪問一個ArrayList實體，而其中至少一個執行緒從結構上修改了串列，那么它必須保持外部同步，（涉及到快速失敗機制）

8、fast-fail機制 ArrayList的自我保護機制
*********快速失敗機制實際上依賴于modCout: 存盤結構修改次數（增加和洗掉、擴容、縮容），和expectedModCount的對照
modCount定義于AbstractList，（ArrayList繼承AbstractList）
使用迭代器或者foreach遍歷時，如果呼叫集合add/remove方法修改集合的結構 ，則會拋出 ConcurrentModificationexception，

8.1、單執行緒，在iterator遍歷的同時，插入新的引數，會導致快速失敗

public class FastFailDemo {
public static void main(String[] args) {
List<Integer> list = new ArrayList<>();
for (int i = 0; i < 10; i++) {
list.add(i);
}

for (Integer integer : list) {
list.add(integer);
System.out.println(integer);
}

}
}

8.2、單執行緒，使用randomaccess遍歷List，即使在邊讀邊寫也不會出現快速失敗

public class FastFailDemo {
public static void main(String[] args) {
List<Integer> list = new ArrayList<>();
for (int i = 0; i < 10; i++) {
list.add(i);
}
for(int i =0 ; i< list.size(); i++) {
list.add(i);
System.out.println(i);
}

}
}

8.3、多執行緒，在一個執行緒讀時，另一個執行緒寫入list，讀執行緒會快速失敗
public class FastFailDemo {
public static void main(String[] args) {
List<Integer> list = new ArrayList<>();
for (int i = 0; i < 10; i++) {
list.add(i);
}
new MyThread1(list).start();
new MyThread2(list).start();
}
}

class MyThread1 extends Thread {
private List<Integer> list;

public MyThread1( List<Integer> list) {
this.list = list;
}

@Override
public void run() {
for (Integer integer : list) {
System.out.println("MyThread1" + list.size());
try {
Thread.sleep(100);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
}

class MyThread2 extends Thread {
private List<Integer> list;

public MyThread2( List<Integer> list) {
this.list = list;
}

@Override
public void run() {

for (int i = 0; i < 10; i++) {
try {
Thread.sleep(100);
} catch (InterruptedException e) {
e.printStackTrace();
}
list.add(i);
System.out.println("MyThread2 " + list.size());
}
}
}

二、arrayLsit的非快速失敗機制和與vector底層實作的對比

1、非快速失敗機制

1）、fail-fast機制，是一種錯誤檢測機制，它只能被用來檢測錯誤，因為JDK并不保證fail-fast機制一定會發生，若在多執行緒環境下使用fail-fast機制的集合，使用“java.util.concurrent包下的類”去取代“java.util包下的類”，
將代碼：
List<Integer> list = new ArrayList<>();
替換為：
List<Integer> list = new CopyOnWriteArrayList<>();

2)、
CopyOnWriteArrayList與ArrayList不同：

(01) 和ArrayList繼承于AbstractList不同，CopyOnWriteArrayList沒有繼承于AbstractList，它僅僅只是實作了List介面，
(02) ArrayList的iterator()函式回傳的Iterator是在AbstractList中實作的；而CopyOnWriteArrayList是自己實作Iterator，
(03) ArrayList的Iterator實作類中呼叫next()時，會“呼叫checkForComodification()比較‘expectedModCount’和‘modCount’的大小”；但是，CopyOnWriteArrayList的Iterator實作類中，沒有所謂的checkForComodification()，更不會拋出ConcurrentModificationException例外！
雖然，獲取到了更新后的ArrayList的大小；但是，當前迭代的結果并不是更新后的arrayList；
public class FastFailDemo {
public static void main(String[] args) {
List<Integer> list = new CopyOnWriteArrayList<>();
for (int i = 0; i < 5; i++) {
list.add(i);
}
new MyThread1(list).start();
new MyThread2(list).start();
}
}

class MyThread1 extends Thread {
private List<Integer> list;

public MyThread1( List<Integer> list) {
this.list = list;
}

@Override
public void run() {
for (Integer integer : list) {
System.out.println("MyThread1 大小：" + list.size() + " 當前值：" + integer);
try {
Thread.sleep(100);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
}

class MyThread2 extends Thread {
private List<Integer> list;

public MyThread2( List<Integer> list) {
this.list = list;
}

@Override
public void run() {

for (int i = 5; i < 10; i++) {
try {
Thread.sleep(100);
} catch (InterruptedException e) {
e.printStackTrace();
}
list.add(i);
System.out.println("MyThread2 大小：" + list.size());
}
}
}

2、ArrayList：
1）、關鍵字解釋：transient， （序列化里用到）
Java的serialization提供了一種持久化物件實體的機制，當持久化物件時，可能有一個特殊的物件資料成員，我們不想用serialization機制來保存它，為了在一個特定物件的一個域上關閉serialization，可以在這個域前加上關鍵字transient，
public class UserInfo implements Serializable {
private static final long serialVersionUID = 996890129747019948L;
private String name;
private transient String psw;

public UserInfo(String name, String psw) {
this.name = name;
this.psw = psw;
}

public String toString() {
return "name=" + name + ", psw=" + psw;
}
}

public class TestTransient {
public static void main(String[] args) {
UserInfo userInfo = new UserInfo("張三", "123456");
System.out.println(userInfo);
try {
// 序列化，被設定為transient的屬性沒有被序列化
ObjectOutputStream o = new ObjectOutputStream(new FileOutputStream(
"UserInfo.out"));
o.writeObject(userInfo);
o.close();
} catch (Exception e) {
// TODO: handle exception
e.printStackTrace();
}
try {
// 重新讀取內容
ObjectInputStream in = new ObjectInputStream(new FileInputStream(
"UserInfo.out"));
UserInfo readUserInfo = (UserInfo) in.readObject();
//讀取后psw的內容為null
System.out.println(readUserInfo.toString());
} catch (Exception e) {
// TODO: handle exception
e.printStackTrace();
}
}
}
2）、構造方法：
ArrayList提供了三種方式的構造器，可以構造一個默認初始容量為10的空串列、構造一個指定初始容量的空串列以及構造一個包含指定collection的元素的串列，這些元素按照該collection的迭代器回傳它們的順序排列的，
// ArrayList帶容量大小的建構式，
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
// 新建一個陣列
this.elementData = new Object[initialCapacity];
}

// ArrayList無參建構式，默認容量是10，
public ArrayList() {
this(10);
}

// 創建一個包含collection的ArrayList
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
size = elementData.length;
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
}
3）、 元素存盤：

ArrayList提供了set(int index, E element)、add(E e)、add(int index, E element)、addAll(Collection<? extends E> c)、addAll(int index, Collection<? extends E> c)這些添加元素的方法，

4）、元素直接讀取
5）、元素洗掉E remove(int index); boolean remove(Object o); void fastRemove(int index);removeRange(int fromIndex,int toIndex)

2、對于ArrayList而言，它實作List介面、底層使用陣列保存所有元素，其操作基本上是對陣列的操作，其實，Vector也基本上是對陣列的操作；
1）、相似之處：
（1）、Vector和ArrayList的實作方式可以看出非常的類似（底層是陣列），增刪改查方法相似，同樣有快速失敗機制
（2）、擴充容量的方法ensureCapacityHelper，
與ArrayList相同，Vector在每次增加元素（可能是1個，也可能是一組）時，都要呼叫該方法來確保足夠的容量，當容量不足以容納當前的元素個數時，就先看構造方法中傳入的容量增長量引數CapacityIncrement是否為0，如果不為0，就設定新的容量為就容量加上容量增長量，如果為0，就設定新的容量為舊的容量的2倍，如果設定后的新容量還不夠，則直接新容量設定為傳入的引數（也就是所需的容量），而后同樣用Arrays.copyof()方法將元素拷貝到新的陣列，
（3）、同樣在查找給定元素索引值等的方法中，兩者都將該元素的值分為null和不為null兩種情況處理，Vector中也允許元素為null，

2）、關于ArrayList和Vector區別如下：
（1）、ArrayList在記憶體不夠時默認是擴展0.5倍，Vector是默認擴展1倍，
（2）、Vector提供indexOf(obj, start)介面，ArrayList沒有，
（3）、Vector屬于執行緒安全級別的，但是大多數情況下不使用Vector，因為執行緒安全需要更大的系統開銷（很多方法加了synchronized同步陳述句，來保證執行緒安全），