ArrayList:底層是數(shù)組邓深，初始容量是10未桥，若存入數(shù)量達(dá)到11即觸發(fā)擴(kuò)容方法，容量擴(kuò)容百分之50芥备。?

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

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

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

LinkedList：底層是繼承AbstractSequentialList的雙向循環(huán)鏈表亦镶。它也可以被當(dāng)作堆棧、隊(duì)列或雙端隊(duì)列進(jìn)行操作袱瓮，每次調(diào)用add方法都是添加至尾部缤骨，無(wú)論LInkedList大小，每次添加所需時(shí)間都是固定的（只需開辟最后一個(gè)節(jié)點(diǎn)的空間尺借，塞值）绊起，

在刪除可插入對(duì)象的動(dòng)作時(shí)，為什么ArrayList的效率會(huì)比較低呢?

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

Vector:底層是對(duì)象數(shù)組栅表，初始容量是10笋鄙，擴(kuò)容百分之百。

int newCapacity

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

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

Vector擴(kuò)展：Vector所有方法都上鎖铐尚，單個(gè)方法被調(diào)用是都是線程安全的，但是對(duì)它的復(fù)合操作無(wú)法保證其線程安全哆姻。

例如定義該方法：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方法中，多線程操作可能會(huì)拋??????????? 出異常矛缨。AB線程同時(shí)進(jìn)入????????????? deleteLast方法內(nèi)爹脾，A方法執(zhí)行到了remove，B方法執(zhí)行到????????????? size箕昭，A先刪除灵妨，B就拋異常。

CopyOnWriteArrayList:實(shí)現(xiàn)了List落竹、RandomAccess接口泌霍，底層使用ReentrantLock支持并發(fā)操作，調(diào)用add?????? 方法時(shí)述召，上鎖后朱转，獲得當(dāng)前數(shù)組蟹地，數(shù)組擴(kuò)容+1，新數(shù)組插入數(shù)據(jù)后將數(shù)組引用指向新數(shù)???????? 組藤为，釋放鎖怪与。另一個(gè)add(index,value)方法，在插入值時(shí)缅疟，先判斷該Index是否有效且位????? 置上沒(méi)存值分别，若沒(méi)存則重復(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實(shí)現(xiàn)了RandomAccess接口纫雁，LinkedList沒(méi)有實(shí)現(xiàn)。

實(shí)現(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的實(shí)現(xiàn)，則盡量用for(int i = 0; i < size; i++) 來(lái)遍歷而不要用Iterator迭代器來(lái)遍歷羞海。

反過(guò)來(lái)忌愚，如果List是Sequence List，則最好用迭代器來(lái)進(jìn)行迭代却邓。

JDK中說(shuō)的很清楚硕糊，在對(duì)List特別是Huge size的List的遍歷算法中，要盡量來(lái)判斷是屬于RandomAccess(如ArrayList)還是Sequence List (如LinkedList）腊徙，因?yàn)檫m合RandomAccess List的遍歷算法简十，用在Sequence List上就差別很大

Vector和ArrayList的區(qū)別

實(shí)現(xiàn)原理都是通過(guò)數(shù)組實(shí)現(xiàn)，查詢速度快撬腾，增加螟蝙、刪除、修改速度慢民傻，區(qū)別在于vector是線程安全的胰默，ArrayList是線程不安全的，但是效率高漓踢。

ArrayList 和 LinkedList區(qū)別

1.? ? ? 隨機(jī)訪問(wèn)get和set牵署，ArrayList速度優(yōu)于LinkedList，因?yàn)長(zhǎng)inkedList需要移動(dòng)指針?????

2.????? 對(duì)于add 和 remove操作喧半，LinkedList速度優(yōu)于ArrayList奴迅，因?yàn)锳rrayList需要移動(dòng)數(shù)據(jù)

CopyOnWriteArrayList和 ArrayList的區(qū)別：

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

2.? ? ? ? CopyOnWriteArrayList代碼底層有重入鎖半沽，可以支持并發(fā)爽柒，它每次改動(dòng)都會(huì)拷貝一個(gè)副本數(shù)組，在副本數(shù)組操作后者填，改變引用指向副本數(shù)組浩村。

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

假如多個(gè)線程一起操作CopyOnWriteArrayList，一個(gè)線程修改榨乎，一個(gè)線程讀取怎燥，則讀取到舊數(shù)據(jù)，所以CopyOnWriteArrayList只能保證最終的一致性蜜暑，不能保證實(shí)時(shí)一致性铐姚。它適用于讀操作遠(yuǎn)多于寫操作的處理，例如緩存肛捍。

HashMap和HashTable的區(qū)別：

1.HashMap不是線程安全的 HastMap是一個(gè)接口 是map接口的子接口隐绵，是將鍵映射到值的對(duì)象，其中鍵和值都是對(duì)象拙毫，并且不能包含重復(fù)鍵依许，但可以包含重復(fù)值。HashMap允許null key和null value缀蹄，而hashtable不允許峭跳。

2.HashTable是線程安全的一個(gè)Collection。

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

HashMap允許將null作為一個(gè)entry的key或者value滞欠，而Hashtable不允許。

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

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

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

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