ArrayList:底層是數(shù)組，初始容量是10，若存入數(shù)量達到11即觸發(fā)擴容方法，容量擴容百分之50。?

??? int newCapacity =oldCapacity + (oldCapacity >> 1);

????elementData = Arrays.copyOf(elementData, newCapacity);

每次調(diào)用add或remove方法，modCount都會加一，這個值會在checkForComodification方法中作為判斷條件決定是否拋出異常。

LinkedList：底層是繼承AbstractSequentialList的雙向循環(huán)鏈表。它也可以被當作堆棧、隊列或雙端隊列進行操作，每次調(diào)用add方法都是添加至尾部，無論LInkedList大小，每次添加所需時間都是固定的（只需開辟最后一個節(jié)點的空間，塞值），

在刪除可插入對象的動作時，為什么ArrayList的效率會比較低呢?

解析:因為ArrayList是使用數(shù)組實現(xiàn)的,若要從數(shù)組中刪除或插入某一個對象，需要移動后段的數(shù)組元素，從而會重新調(diào)整索引順序,調(diào)整索引順序會消耗一定的時間，所以速度上就會比LinkedList要慢許多. 相反,LinkedList是使用鏈表實現(xiàn)的,若要從鏈表中刪除或插入某一個對象,只需要改變前后對象的引用即可!

Vector:底層是對象數(shù)組，初始容量是10，擴容百分之百。

int newCapacity

= oldCapacity + ((capacityIncrement > 0) ?capacityIncrement : oldCapacity);

底層方法都用synchronized方法保證并發(fā)安全。所以效率低。且調(diào)用remove方法時，??? 不會調(diào)節(jié)底層數(shù)組大小。

Vector擴展：Vector所有方法都上鎖，單個方法被調(diào)用是都是線程安全的，但是對它的復(fù)合操作無法保證其線程安全。

例如定義該方法：public Object deleteLast(Vector v){

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?int lastIndex?= v.size()-1;

??????????????????????????????????????????????????????? v.remove(lastIndex);

????????????????????????????????}

Remove源碼：public synchronized E remove(int index) {

??????????????????????????????????????????????????????? ?modCount++;

??????????????????????????????????????????????????????? ?if (index >= elementCount)

????????????????????????????????????????? ?? throw newArrayIndexOutOfBoundsException(index);

??????????????????????????????????????????????????????? ?E oldValue = elementData(index);

??????????????????????????????????????????????????????? ?int numMoved = elementCount - index - 1;

??????????????????????????????????????????????????????? ?if (numMoved > 0)

????????????????????????????????????????? ?? System.arraycopy(elementData, index+1, elementData,index,? numMoved);

??????????????????????????????????????????????????????? ?elementData[--elementCount] = null; // Let gcdo its work

??????????????????????????????????????????????????????? ?return oldValue;

}

Size和remove方法都是線程安全的，但在該deleteLast方法中，多線程操作可能會拋??????????? 出異常。AB線程同時進入????????????? deleteLast方法內(nèi)，A方法執(zhí)行到了remove，B方法執(zhí)行到????????????? size，A先刪除，B就拋異常。

CopyOnWriteArrayList:實現(xiàn)了List、RandomAccess接口，底層使用ReentrantLock支持并發(fā)操作，調(diào)用add?????? 方法時，上鎖后，獲得當前數(shù)組，數(shù)組擴容+1，新數(shù)組插入數(shù)據(jù)后將數(shù)組引用指向新數(shù)???????? 組，釋放鎖。另一個add(index,value)方法，在插入值時，先判斷該Index是否有效且位????? 置上沒存值，若沒存則重復(fù)上述劃線操作；若有值，則

? ? ? ? ? ? ? ?newElements = new Object[len + 1];

??????????????? System.arraycopy(elements, 0,newElements, 0, index);

??????????????? System.arraycopy(elements,index, newElements, index + 1,numMoved);

刪除方法與上述斜體字操作類似，若index位置在末尾則直接縮減數(shù)組大小，否則

? ? ? ? ? ? ? Object[] newElements = new Object[len - 1];

??????????????? System.arraycopy(elements, 0,newElements, 0, index);

??????????????? System.arraycopy(elements,index + 1, newElements, index,numMoved);

??????????????? setArray(newElements);

LinkedList以及ArrayList的迭代效率比較

ArrayList實現(xiàn)了RandomAccess接口，LinkedList沒有實現(xiàn)。

實現(xiàn)RandomAccess接口的意思：http://www.jb51.net/article/92127.htm

結(jié)論：ArrayList使用最普通的for循環(huán)遍歷最快，LinkedList使用foreach循環(huán)較為??? 快（*LinkedList使用foreach遍歷巨慢，foreach底層調(diào)用Iterator遍歷*）

如果集合類是RandomAccess的實現(xiàn)，則盡量用for(int i = 0; i < size; i++) 來遍歷而不要用Iterator迭代器來遍歷。

反過來，如果List是Sequence List，則最好用迭代器來進行迭代。

JDK中說的很清楚，在對List特別是Huge size的List的遍歷算法中，要盡量來判斷是屬于RandomAccess(如ArrayList)還是Sequence List (如LinkedList），因為適合RandomAccess List的遍歷算法，用在Sequence List上就差別很大

Vector和ArrayList的區(qū)別

實現(xiàn)原理都是通過數(shù)組實現(xiàn)，查詢速度快，增加、刪除、修改速度慢，區(qū)別在于vector是線程安全的，ArrayList是線程不安全的，但是效率高。

ArrayList 和 LinkedList區(qū)別

1.? ? ? 隨機訪問get和set，ArrayList速度優(yōu)于LinkedList，因為LinkedList需要移動指針?????

2.????? 對于add 和 remove操作，LinkedList速度優(yōu)于ArrayList，因為ArrayList需要移動數(shù)據(jù)

CopyOnWriteArrayList和 ArrayList的區(qū)別：

1.? ? ? ? 每次調(diào)用remove 和 add方法都會對modCount加1，這個值會在checkForComodification方法中作為判斷條件決定是否拋出異常。

2.? ? ? ? CopyOnWriteArrayList代碼底層有重入鎖，可以支持并發(fā)，它每次改動都會拷貝一個副本數(shù)組，在副本數(shù)組操作后，改變引用指向副本數(shù)組。

3.? ? ? ? CopyOnWriteArrayList的缺點就是每個線程操作它都需要拷貝一個副本數(shù)組，?? 如果副本數(shù)組比較大則會占用大內(nèi)存，造成多次垃圾回收。

假如多個線程一起操作CopyOnWriteArrayList，一個線程修改，一個線程讀取，則讀取到舊數(shù)據(jù)，所以CopyOnWriteArrayList只能保證最終的一致性，不能保證實時一致性。它適用于讀操作遠多于寫操作的處理，例如緩存。

HashMap和HashTable的區(qū)別：

1.HashMap不是線程安全的 HastMap是一個接口 是map接口的子接口，是將鍵映射到值的對象，其中鍵和值都是對象，并且不能包含重復(fù)鍵，但可以包含重復(fù)值。HashMap允許null key和null value，而hashtable不允許。

2.HashTable是線程安全的一個Collection。

3.HashMap是Hashtable的輕量級實現(xiàn)（非線程安全的實現(xiàn)），他們都完成了Map接口，主要區(qū)別在于HashMap允許空（null）鍵值（key）,由于非線程安全，效率上可能高于Hashtable。

HashMap允許將null作為一個entry的key或者value，而Hashtable不允許。

HashMap把Hashtable的contains方法去掉了，改成containsvalue和containsKey。

a)? ? ?HashMap底層是由數(shù)組+鏈表+紅黑樹構(gòu)成。默認容量是16，加載因子是0.75，鏈表轉(zhuǎn)紅黑樹的閾值是8。初始化HashMap有三種方法（無參，帶初始容量，帶初始容量及加載因子），其中后兩種運用了門面模式（其實是一個方法），put值的時候先判斷是否需要調(diào)用resize方法擴容.若resize后需要rehash重新計算Key對應(yīng)的值（位置）再進行插入。HashMap的時間復(fù)雜度是O(n).允許存null

b)????? HashTable底層數(shù)組+鏈表。默認容量11，加載因子是0.75.初始化HashTable有三種方法（無參，帶初始容量，帶初始容量及加載因子），后兩種也運用了門面模式，put值得時候先計算key的hash對應(yīng)的Index，然后遍歷該節(jié)點位置的值，若key相同則替換舊值，否則新開辟一個Entry存放key value.HashTable所有方法都帶有synchronized,不支持存null.

c)????? ConcurrentHashMap底層是數(shù)組+鏈表+紅黑樹。默認容量16，加載因子0.75，鏈表轉(zhuǎn)紅黑樹的閾值是8,。初始化ConcurrentHashMap有四種方法（無參，帶初始容量，帶初始容量及加載因子，帶Map）。ConcurrentHashMap不支持存null,put值得時候先判斷table是否為空，否則初始化table,然后計算key的hash后的Index，若該位置為空則直接新加節(jié)點存且過程不上鎖。若該位置有值則上分段鎖保證并發(fā)安全。（HashTable縮小版）