復(fù)習(xí)范圍：
ArrayList與LinkedList區(qū)別
- 線程安全：兩個(gè)都是不同步的，即不保證線程安全
- 數(shù)據(jù)結(jié)構(gòu)：ArrayList用的是數(shù)組實(shí)現(xiàn)抒蚜，LinkedList用的是雙向鏈表掘鄙。
- 插入刪除，隨機(jī)訪問：ArrayList因?yàn)槭菙?shù)組嗡髓，所以插入刪除末尾元素的話時(shí)間復(fù)雜度只需O（1）通铲，如果是指定位置i的元素，因?yàn)橐獙?duì)i之后的元素進(jìn)行往后一位或者往前一位的操作器贩，時(shí)間復(fù)雜度為O（n-i）颅夺。LinkedList是鏈表，所以插入刪除指定位置i的元素就要一直移動(dòng)到指定位置再刪除蛹稍，時(shí)間復(fù)雜度為O（i）吧黄，但是如果在末尾刪除插入元素，時(shí)間復(fù)雜度為O（1）唆姐。ArrayList支持隨機(jī)訪問拗慨，直接通過數(shù)組下標(biāo)就可以訪問元素了。LinkedList則不支持奉芦，這也是數(shù)據(jù)結(jié)構(gòu)的區(qū)別造成的赵抢。
- 空間占用：ArrayList的結(jié)尾需要預(yù)留一定的容量空間，而LinkedList每個(gè)元素都要有直接前繼声功，直接后繼烦却，元素大小。所以每個(gè)元素消耗的空間大于ArrayList先巴。
ArrayList擴(kuò)容機(jī)制
minCapacity:所需的最小容量
當(dāng)ArrayList增加元素時(shí)其爵，minCapacity就會(huì)+1，這個(gè)時(shí)候拿他和默認(rèn)值10進(jìn)行比較伸蚯，取最大值賦給minCapacity摩渺。當(dāng)minCapacity大于當(dāng)前ArrayList的長(zhǎng)度后，就會(huì)調(diào)用grow方法來進(jìn)行擴(kuò)容剂邮。
擴(kuò)容過程：先把舊容量（當(dāng)前數(shù)組的長(zhǎng)度摇幻，不是數(shù)組元素的個(gè)數(shù)）變?yōu)橹暗?.5倍，再和minCapacity相比挥萌，如果還是小于minCapacity就會(huì)把minCapacity的值賦給新容量（newCapacity）绰姻。如果新容量大于ArrayList所定義的最大容量MAX_ARRAY_SIZE，newCapacity就為Interger.MAX_VALUE瑞眼，否則是MAX_ARRAY_SIZE龙宏。最后把原數(shù)組內(nèi)容放到新的數(shù)組里面。
HashMap
JDK1.8以前是用的數(shù)組＋鏈表的形式伤疙，银酗，先對(duì)key的hashcode進(jìn)行hash方法，得到一個(gè)hash值徒像，然后用hash & （ n - 1 ）來得到該存放在數(shù)組的哪一個(gè)位置黍特，如果這時(shí)候數(shù)組該位置已經(jīng)有一個(gè)了，那么判斷兩者的hash和key是不是相同锯蛀，相同就直接覆蓋了灭衷，不同的話就在數(shù)組的該位置生成一個(gè)鏈表，把后者加進(jìn)鏈表里面旁涤。
這樣子的話如果所有key都存放在數(shù)組的一個(gè)鏈表上面翔曲，那么查找效率就是從鏈表的第一個(gè)節(jié)點(diǎn)往下面找迫像，是個(gè)線性結(jié)構(gòu)，就會(huì)導(dǎo)致效率過低瞳遍，所以JDK1.8引入了紅黑樹來輔助查找闻妓。當(dāng)鏈表長(zhǎng)度大于指定值（一般是8），這個(gè)時(shí)候就會(huì)判斷數(shù)組長(zhǎng)度是否大于64掠械，大于的話鏈表就會(huì)轉(zhuǎn)化為紅黑樹由缆，小于的話會(huì)對(duì)數(shù)組進(jìn)行擴(kuò)容。
HashMap多線程的問題
多線程中猾蒂，HashMap擴(kuò)容后要重新計(jì)算hash值均唉，也就是rehash后，元素之間會(huì)存在一個(gè)死循環(huán)鏈表肚菠，然后就會(huì)一直在運(yùn)行舔箭，浪費(fèi)資源。jdk1.8之后解決了這個(gè)問題案糙。
HashMap和HashTable區(qū)別
- 數(shù)據(jù)結(jié)構(gòu)：HashMap用的是數(shù)組＋鏈表的形式限嫌，如果鏈表長(zhǎng)度大于8，數(shù)組長(zhǎng)度大于64时捌，鏈表就會(huì)轉(zhuǎn)成紅黑樹怒医。HashTable不會(huì)轉(zhuǎn)紅黑樹。
- 存放null ：HashMap允許存放key和value都為null的值奢讨。key只允許存放一個(gè)稚叹，value可以存放多個(gè)。HashTable不允許存放null拿诸。
- 線程安全：HashMap在多線程的時(shí)候是不安全的扒袖，HashTable是安全的，里面的方法經(jīng)過synchronized修飾過亩码。（注意：HashTable現(xiàn)在不推薦使用季率，如果要保證線程安全就要使用ConcurrentHashMap！）
- 效率：HashMap效率會(huì)高一點(diǎn)描沟，因?yàn)榫€程安全的問題飒泻。
- 初始容量：HashMap默認(rèn)值是16，如果要擴(kuò)容就會(huì)乘2吏廉，因?yàn)樗ＷC長(zhǎng)度永遠(yuǎn)是2的冪次方泞遗。如果你給了一個(gè)初始值，就會(huì)把它擴(kuò)充成2的冪次方席覆。HashTable默認(rèn)值是11史辙，每次擴(kuò)容就是原來的2n+1。給定初始值的話，HashTable會(huì)直接使用你給的值聊倔。
HashMap和HashSet區(qū)別
HashSet基于HashMap實(shí)現(xiàn)晦毙，所以都是線程不安全
- HashMap實(shí)現(xiàn)了Map接口，HashSet實(shí)現(xiàn)了set接口
- HashMap存儲(chǔ)了鍵值對(duì)耙蔑，HashSet存儲(chǔ)對(duì)象
- HashMap使用key計(jì)算hashcode结序。HashSet使用成員對(duì)象來計(jì)算hashcode，對(duì)于兩個(gè)對(duì)象可能hashcode相等纵潦，這個(gè)時(shí)候就要用equals來判斷兩個(gè)對(duì)象相不相等。
- HashMap添加時(shí)遇到重復(fù)值是覆蓋垃环，HashSet遇到重復(fù)值是把后來的放棄掉邀层，維持原來的。
HashSet檢查重復(fù)
當(dāng)你添加對(duì)象到HashSet中遂庄，HashSet計(jì)算對(duì)象的hashcode值寥院，與其他對(duì)象的hashcode進(jìn)行比較，如果有相同hashcode的對(duì)象涛目，就調(diào)用equals方法來檢查兩個(gè)對(duì)象是不是相等秸谢，相等就不把對(duì)象添加進(jìn)HashSet中。
LinkedHashMap
LinkedHashMap可以把添加的數(shù)據(jù)霹肝，按添加的順序輸出 估蹄。用的是雙向鏈表。
ConcurrentHashMap線程安全
JDK1.7:把數(shù)據(jù)分成一段一段沫换，分開上鎖臭蚁，如果一個(gè)線程對(duì)第一段數(shù)據(jù)進(jìn)行操作，那么其他線程依舊可以訪問其他段數(shù)據(jù)讯赏。由Segment數(shù)組結(jié)構(gòu)和HashEntry數(shù)組結(jié)構(gòu)組成垮兑。Segment負(fù)責(zé)鎖的角色，HashEntry負(fù)責(zé)存儲(chǔ)鍵值對(duì)漱挎。
一個(gè)ConcurrentHashMap有一個(gè)Segment數(shù)組系枪，每個(gè)Segment有一個(gè)HashEntry數(shù)組。每個(gè)Segment都會(huì)守護(hù)一個(gè)HashEntry的數(shù)據(jù)磕谅，如果要進(jìn)行操作私爷，必須獲得相對(duì)應(yīng)的Segment。
JDK1.8：放棄了Segment怜庸，才用CAS和synchronized來保證安全当犯。數(shù)據(jù)結(jié)構(gòu)和HashMap一樣，采用Node數(shù)組+鏈表/紅黑樹的結(jié)構(gòu)割疾。synchronized鎖定當(dāng)前鏈表和紅黑樹的首節(jié)點(diǎn)嚎卫，只要hash不沖突，就不會(huì)產(chǎn)生并發(fā)。
ConcurrentHashMap與HashTable
HashTable使用Synchronized來保證線程安全拓诸，效率比較低。當(dāng)一個(gè)線程進(jìn)行put操作時(shí)奠支，其他線程無法進(jìn)行put和get操作倍谜。ConcurrentHashMap采用的是數(shù)據(jù)分成一段段進(jìn)行上鎖尔崔，這樣子就不會(huì)產(chǎn)生過多的阻塞，也能保證線程安全洗搂。
根據(jù)資料：
本文主要根據(jù)JavaGuide的資料
ArrayList簡(jiǎn)介
