1. ArrayList LinkedList
2. ArrayList 擴(kuò)容機(jī)制
3. HashSet
4. HashMap 和 HashTable 區(qū)別
線程是否安全
效率
初始容量 和 每次擴(kuò)容的大小
底層數(shù)據(jù)結(jié)構(gòu)
5. HashMap 底層實(shí)現(xiàn)
5.1
1.8 之前 數(shù)組+鏈表
1.8 數(shù)組+鏈表+紅黑樹
相比于之前的版本， JDK1.8 之后在解決哈希沖突時(shí)有了較大的變化，當(dāng)鏈表長(zhǎng)度大于閾值（默認(rèn)為 8）（將鏈表轉(zhuǎn)換成紅黑樹前會(huì)判斷猫十，如果當(dāng)前數(shù)組的長(zhǎng)度小于 64挖垛，那么會(huì)選擇先進(jìn)行數(shù)組擴(kuò)容警检，而不是轉(zhuǎn)換為紅黑樹）時(shí)，將鏈表轉(zhuǎn)化為紅黑樹误墓，以減少搜索時(shí)間唁影。
TreeMap、TreeSet 以及 JDK1.8 之后的 HashMap 底層都用到了紅黑樹遇伞。紅黑樹就是為了解決二叉查找樹的缺陷辙喂，因?yàn)槎娌檎覙湓谀承┣闆r下會(huì)退化成一個(gè)線性結(jié)構(gòu)。
5.2HashMap 的長(zhǎng)度為什么是2的冪次方
為了能讓 HashMap 存取高效，盡量較少碰撞加派，也就是要盡量把數(shù)據(jù)分配均勻叫确。我們上面也講到了過(guò)了，Hash 值的范圍值-2147483648到2147483647芍锦，前后加起來(lái)大概40億的映射空間竹勉，只要哈希函數(shù)映射得比較均勻松散，一般應(yīng)用是很難出現(xiàn)碰撞的娄琉。但問題是一個(gè)40億長(zhǎng)度的數(shù)組次乓，內(nèi)存是放不下的。所以這個(gè)散列值是不能直接拿來(lái)用的孽水。用之前還要先做對(duì)數(shù)組的長(zhǎng)度取模運(yùn)算票腰，得到的余數(shù)才能用來(lái)要存放的位置也就是對(duì)應(yīng)的數(shù)組下標(biāo)。這個(gè)數(shù)組下標(biāo)的計(jì)算方法是“ (n - 1) & hash”女气。（n代表數(shù)組長(zhǎng)度）杏慰。這也就解釋了 HashMap 的長(zhǎng)度為什么是2的冪次方。
5.3 HashMap 多線程操作導(dǎo)致死循環(huán)問題
主要原因在于 并發(fā)下的Rehash 會(huì)造成元素之間會(huì)形成一個(gè)循環(huán)鏈表炼鞠。不過(guò)缘滥，jdk 1.8 后解決了這個(gè)問題，但是還是不建議在多線程下使用 HashMap,因?yàn)槎嗑€程下使用 HashMap 還是會(huì)存在其他問題比如數(shù)據(jù)丟失谒主。并發(fā)環(huán)境下推薦使用 ConcurrentHashMap 朝扼。
5.4 ConcurrentHashMap 和 Hashtable 的區(qū)別
ConcurrentHashMap 和 Hashtable 的區(qū)別主要體現(xiàn)在實(shí)現(xiàn)線程安全的方式上不同。
- 底層數(shù)據(jù)結(jié)構(gòu)： JDK1.7 的 ConcurrentHashMap 底層采用 分段的數(shù)組+鏈表 實(shí)現(xiàn)霎肯，JDK1.8 采用的數(shù)據(jù)結(jié)構(gòu)跟 HashMap1.8 的結(jié)構(gòu)一樣擎颖，數(shù)組+鏈表/紅黑二叉樹。Hashtable 和 JDK1.8 之前的 HashMap 的底層數(shù)據(jù)結(jié)構(gòu)類似都是采用 數(shù)組+鏈表 的形式观游，數(shù)組是 HashMap 的主體搂捧，鏈表則是主要為了解決哈希沖突而存在的；
- 實(shí)現(xiàn)線程安全的方式（重要）： ① 在 JDK1.7 的時(shí)候备典，ConcurrentHashMap（分段鎖） 對(duì)整個(gè)桶數(shù)組進(jìn)行了分割分段(Segment)异旧，每一把鎖只鎖容器其中一部分?jǐn)?shù)據(jù)，多線程訪問容器里不同數(shù)據(jù)段的數(shù)據(jù)提佣，就不會(huì)存在鎖競(jìng)爭(zhēng)吮蛹，提高并發(fā)訪問率。 到了 JDK1.8 的時(shí)候已經(jīng)摒棄了 Segment 的概念拌屏，而是直接用 Node 數(shù)組+鏈表+紅黑樹的數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)潮针，并發(fā)控制使用 synchronized 和 CAS 來(lái)操作。（JDK1.6 以后 對(duì) synchronized 鎖做了很多優(yōu)化） 整個(gè)看起來(lái)就像是優(yōu)化過(guò)且線程安全的 HashMap倚喂，雖然在 JDK1.8 中還能看到 Segment 的數(shù)據(jù)結(jié)構(gòu)每篷，但是已經(jīng)簡(jiǎn)化了屬性瓣戚，只是為了兼容舊版本；② Hashtable(同一把鎖) :使用 synchronized 來(lái)保證線程安全焦读，效率非常低下子库。當(dāng)一個(gè)線程訪問同步方法時(shí)，其他線程也訪問同步方法矗晃，可能會(huì)進(jìn)入阻塞或輪詢狀態(tài)仑嗅，如使用 put 添加元素，另一個(gè)線程不能使用 put 添加元素张症，也不能使用 get仓技，競(jìng)爭(zhēng)會(huì)越來(lái)越激烈效率越低。
6. ConcurrentHashMap線程安全的具體實(shí)現(xiàn)方式/底層具體實(shí)現(xiàn)
6.1 JDK1.7時(shí)
首先將數(shù)據(jù)分為一段一段的存儲(chǔ)俗他，然后給每一段數(shù)據(jù)配一把鎖脖捻，當(dāng)一個(gè)線程占用鎖訪問其中一個(gè)段數(shù)據(jù)時(shí)，其他段的數(shù)據(jù)也能被其他線程訪問兆衅。
ConcurrentHashMap 是由 Segment 數(shù)組結(jié)構(gòu)和 HashEntry 數(shù)組結(jié)構(gòu)組成地沮。
Segment 實(shí)現(xiàn)了 ReentrantLock,所以 Segment 是一種可重入鎖，扮演鎖的角色涯保。HashEntry 用于存儲(chǔ)鍵值對(duì)數(shù)據(jù)诉濒。
一個(gè) ConcurrentHashMap 里包含一個(gè) Segment 數(shù)組周伦。Segment 的結(jié)構(gòu)和 HashMap 類似夕春，是一種數(shù)組和鏈表結(jié)構(gòu)，一個(gè) Segment 包含一個(gè) HashEntry 數(shù)組专挪，每個(gè) HashEntry 是一個(gè)鏈表結(jié)構(gòu)的元素及志，每個(gè) Segment 守護(hù)著一個(gè) HashEntry 數(shù)組里的元素，當(dāng)對(duì) HashEntry 數(shù)組的數(shù)據(jù)進(jìn)行修改時(shí)寨腔，必須首先獲得對(duì)應(yīng)的 Segment 的鎖速侈。
6.2 JDK1.8時(shí)
ConcurrentHashMap 取消了 Segment 分段鎖，采用 CAS 和 synchronized 來(lái)保證并發(fā)安全迫卢。數(shù)據(jù)結(jié)構(gòu)跟 HashMap1.8 的結(jié)構(gòu)類似倚搬，數(shù)組+鏈表/紅黑二叉樹。Java 8 在鏈表長(zhǎng)度超過(guò)一定閾值（8）時(shí)將鏈表（尋址時(shí)間復(fù)雜度為 O(N)）轉(zhuǎn)換為紅黑樹（尋址時(shí)間復(fù)雜度為 O(log(N))）
synchronized 只鎖定當(dāng)前鏈表或紅黑二叉樹的首節(jié)點(diǎn)乾蛤，這樣只要 hash 不沖突每界，就不會(huì)產(chǎn)生并發(fā)，效率又提升 N 倍家卖。
7. CAS（Compare-and-Swap）
即比較并替換眨层，是一種實(shí)現(xiàn)并發(fā)算法時(shí)常用到的技術(shù)，Java并發(fā)包中的很多類都使用了CAS技術(shù)上荡。
Java 中的各種鎖和 CAS + 面試題
從 Atomic 到 CAS
