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)，所以讀讀之間不互斥，讀寫之間也不互斥，只有寫寫之間要加鎖互斥。但復(fù)制快照的成本昂貴，典型的適合讀多寫少的場(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，不知道?。?/li>
LinkHashMap
擴(kuò)展HashMap，每個(gè)Entry增加雙向鏈表，號(hào)稱是最占內(nèi)存的數(shù)據(jù)結(jié)構(gòu)。
支持iterator()時(shí)按Entry的插入順序來(lái)排序(如果設(shè)置accessOrder屬性為true，則所有讀寫訪問(wèn)都排序)。
插入時(shí)，Entry把自己加到Header Entry的前面去。如果所有讀寫訪問(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把寫鎖(可以設(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下的集合小抄
