ArrayList
以數(shù)組實(shí)現(xiàn)响蕴。節(jié)約空間甘磨，但數(shù)組有容量限制蝌蹂。超出限制時(shí)會(huì)增加50%容量款慨，用System.arraycopy()復(fù)制到新的數(shù)組胖烛。因此最好能給出數(shù)組大小的預(yù)估值挫以。默認(rèn)第一次插入元素時(shí)創(chuàng)建大小為10的數(shù)組者蠕。
按數(shù)組下標(biāo)訪問(wèn)元素－get(i)、set(i,e) 的性能很高掐松，這是數(shù)組的基本優(yōu)勢(shì)踱侣。
如果按下標(biāo)插入元素、刪除元素－add(i,e)大磺、 remove(i)抡句、remove(e)，則要用System.arraycopy()來(lái)復(fù)制移動(dòng)部分受影響的元素杠愧，性能就變差了待榔。
越是前面的元素，修改時(shí)要移動(dòng)的元素越多流济。直接在數(shù)組末尾加入元素－常用的add(e)锐锣，刪除最后一個(gè)元素則無(wú)影響腌闯。
LinkedList
以雙向鏈表實(shí)現(xiàn)。鏈表無(wú)容量限制雕憔，但雙向鏈表本身使用了更多空間姿骏，每插入一個(gè)元素都要構(gòu)造一個(gè)額外的Node對(duì)象，也需要額外的鏈表指針操作橘茉。
按下標(biāo)訪問(wèn)元素－get(i)工腋、set(i,e) 要悲劇的部分遍歷鏈表將指針移動(dòng)到位 (如果i>數(shù)組大小的一半，會(huì)從末尾移起)畅卓。
插入擅腰、刪除元素時(shí)修改前后節(jié)點(diǎn)的指針即可，不在需要復(fù)制移動(dòng)翁潘。但還是要部分遍歷鏈表的指針才能移動(dòng)到下標(biāo)所指的位置趁冈。
只有在鏈表兩頭的操作－add()、addFirst()拜马、removeLast()或用iterator()上的remove()倒能省掉指針的移動(dòng)渗勘。
Apache Commons 有個(gè)TreeNodeList，里面是棵二叉樹(shù)俩莽，可以快速移動(dòng)指針到位旺坠。
CopyOnWriteArrayList
并發(fā)優(yōu)化的ArrayList“绯基于不可變對(duì)象策略取刃，在修改時(shí)先復(fù)制出一個(gè)數(shù)組快照來(lái)修改，改好了出刷，再讓內(nèi)部指針指向新數(shù)組璧疗。
因?yàn)閷?duì)快照的修改對(duì)讀操作來(lái)說(shuō)不可見(jiàn)，所以讀讀之間不互斥馁龟，讀寫(xiě)之間也不互斥崩侠，只有寫(xiě)寫(xiě)之間要加鎖互斥。但復(fù)制快照的成本昂貴坷檩，典型的適合讀多寫(xiě)少的場(chǎng)景却音。
雖然增加了addIfAbsent(e)方法，會(huì)遍歷數(shù)組來(lái)檢查元素是否已存在淌喻，性能可想像的不會(huì)太好僧家。
HashMap
以Entry[]數(shù)組實(shí)現(xiàn)的哈希桶數(shù)組，用Key的哈希值取模桶數(shù)組的大小可得到數(shù)組下標(biāo)裸删。
插入元素時(shí)八拱，如果兩條Key落在同一個(gè)桶(比如哈希值1和17取模16后都屬于第一個(gè)哈希桶)，我們稱之為哈希沖突。
JDK的做法是鏈表法肌稻，Entry用一個(gè)next屬性實(shí)現(xiàn)多個(gè)Entry以單向鏈表存放清蚀。查找哈希值為17的key時(shí)，先定位到哈希桶爹谭，然后鏈表遍歷桶里所有元素枷邪，逐個(gè)比較其Hash值然后key值。
在JDK8里诺凡，新增默認(rèn)為8的閥值东揣，當(dāng)一個(gè)桶里的Entry超過(guò)閥值，就不以單向鏈表而以紅黑樹(shù)來(lái)存放以加快Key的查找速度腹泌。
當(dāng)然嘶卧，最好還是桶里只有一個(gè)元素，不用去比較凉袱。所以默認(rèn)當(dāng)Entry數(shù)量達(dá)到桶數(shù)量的75%時(shí)芥吟，哈希沖突已比較嚴(yán)重，就會(huì)成倍擴(kuò)容桶數(shù)組专甩，并重新分配所有原來(lái)的Entry钟鸵。擴(kuò)容成本不低，所以也最好有個(gè)預(yù)估值涤躲。
取模用與操作(hash & (arrayLength-1))會(huì)比較快棺耍，所以數(shù)組的大小永遠(yuǎn)是2的N次方， 你隨便給一個(gè)初始值比如17會(huì)轉(zhuǎn)為32种樱。默認(rèn)第一次放入元素時(shí)的初始值是16烈掠。
iterator()時(shí)順著哈希桶數(shù)組來(lái)遍歷，看起來(lái)是個(gè)亂序缸托。
問(wèn)題集錦
- HashMap為什么線程不安全？
沒(méi)有任何的線程同步瘾蛋，多線程環(huán)境下對(duì)共享變量的操作（數(shù)據(jù)競(jìng)爭(zhēng)）肯定就不安全了俐镐！ - 為什么當(dāng)一個(gè)桶里的Entry超過(guò)閥值8，就以紅黑樹(shù)來(lái)存放哺哼？
單向鏈表時(shí)間復(fù)雜度是O(n)佩抹，紅黑樹(shù)是O(logn)，至于為什么是8取董，不知道９髌弧！
LinkHashMap
擴(kuò)展HashMap茵汰，每個(gè)Entry增加雙向鏈表枢里，號(hào)稱是最占內(nèi)存的數(shù)據(jù)結(jié)構(gòu)。
支持iterator()時(shí)按Entry的插入順序來(lái)排序(如果設(shè)置accessOrder屬性為true，則所有讀寫(xiě)訪問(wèn)都排序)栏豺。
插入時(shí)彬碱，Entry把自己加到Header Entry的前面去。如果所有讀寫(xiě)訪問(wèn)都要排序奥洼，還要把前后Entry的before/after拼接起來(lái)以在鏈表中刪除掉自己巷疼，所以此時(shí)讀操作也是線程不安全的了。
TreeMap
以紅黑樹(shù)實(shí)現(xiàn)灵奖，紅黑樹(shù)又叫自平衡二叉樹(shù)
對(duì)于任一節(jié)點(diǎn)而言嚼沿，其到葉節(jié)點(diǎn)的每一條路徑都包含相同數(shù)目的黑結(jié)點(diǎn)。
上面的規(guī)定瓷患，使得樹(shù)的層數(shù)不會(huì)差的太遠(yuǎn)骡尽，使得所有操作的復(fù)雜度不超過(guò) O（lgn），但也使得插入尉尾，修改時(shí)要復(fù)雜的左旋右旋來(lái)保持樹(shù)的平衡爆阶。
支持iterator()時(shí)按Key值排序，可按實(shí)現(xiàn)了Comparable接口的Key的升序排序沙咏，或由傳入的Comparator控制辨图。可想象的肢藐，在樹(shù)上插入/刪除元素的代價(jià)一定比HashMap的大故河。
支持SortedMap接口，如firstKey()吆豹，lastKey()取得最大最小的key鱼的，或sub(fromKey, toKey), tailMap(fromKey)剪取Map的某一段。
EnumMap
EnumMap的原理是痘煤，在構(gòu)造函數(shù)里要傳入枚舉類凑阶，那它就構(gòu)建一個(gè)與枚舉的所有值等大的數(shù)組，按Enum. ordinal()下標(biāo)來(lái)訪問(wèn)數(shù)組衷快。性能與內(nèi)存占用俱佳宙橱。
美中不足的是，因?yàn)橐獙?shí)現(xiàn)Map接口蘸拔，而 V get(Object key)中key是Object而不是泛型K师郑，所以安全起見(jiàn)，EnumMap每次訪問(wèn)都要先對(duì)Key進(jìn)行類型判斷调窍，在JMC里錄得不低的采樣命中頻率宝冕。
ConcurrentHashMap
并發(fā)優(yōu)化的HashMap。
在JDK7里的經(jīng)典設(shè)計(jì)邓萨，默認(rèn)16把寫(xiě)鎖(可以設(shè)置更多)地梨，有效分散了阻塞的概率菊卷。數(shù)據(jù)結(jié)構(gòu)為Segment[]，每個(gè)Segment一把鎖湿刽。Segment里面才是哈希桶數(shù)組的烁。Key先算出它在哪個(gè)Segment里，再去算它在哪個(gè)哈希桶里诈闺。
也沒(méi)有讀鎖渴庆，因?yàn)閜ut/remove動(dòng)作是個(gè)原子動(dòng)作(比如put的整個(gè)過(guò)程是一個(gè)對(duì)數(shù)組元素/Entry 指針的賦值操作)，讀操作不會(huì)看到一個(gè)更新動(dòng)作的中間狀態(tài)雅镊。
但在JDK8里襟雷，Segment[]的設(shè)計(jì)被拋棄了，改為精心設(shè)計(jì)的仁烹，只在需要鎖的時(shí)候加鎖耸弄。
支持ConcurrentMap接口，如putIfAbsent(key卓缰，value)與相反的replace(key计呈，value)與以及實(shí)現(xiàn)CAS的replace(key, oldValue, newValue)。
提問(wèn)
- 所以征唬，使用concurrentHashMap就一定線程安全捌显？
Set
所有Set幾乎都是內(nèi)部用一個(gè)Map來(lái)實(shí)現(xiàn), 因?yàn)镸ap里的KeySet就是一個(gè)Set，而value是假值总寒，全部使用同一個(gè)Object即可扶歪。
Set的特征也繼承了那些內(nèi)部的Map實(shí)現(xiàn)的特征。
HashSet：內(nèi)部是HashMap摄闸。
LinkedHashSet：內(nèi)部是LinkedHashMap善镰。
TreeSet：內(nèi)部是TreeMap的SortedSet。
ConcurrentSkipListSet：內(nèi)部是ConcurrentSkipListMap的并發(fā)優(yōu)化的SortedSet年枕。
CopyOnWriteArraySet：內(nèi)部是CopyOnWriteArrayList的并發(fā)優(yōu)化的Set炫欺，利用其addIfAbsent()方法實(shí)現(xiàn)元素去重，如前所述該方法的性能很一般熏兄。
好像少了個(gè)ConcurrentHashSet竣稽，本來(lái)也該有一個(gè)內(nèi)部用ConcurrentHashMap的簡(jiǎn)單實(shí)現(xiàn)，但JDK偏偏沒(méi)提供霍弹。Jetty就自己簡(jiǎn)單封了一個(gè)，Guava則直接用java.util.Collections.newSetFromMap(new ConcurrentHashMap()) 實(shí)現(xiàn)娃弓。
參考資料
- 江南白衣-java8下的集合小抄
