理論：第一章：HashMap底層實現(xiàn)原理，紅黑樹，B+樹，B樹的結(jié)構(gòu)原理，volatile關(guān)鍵字，CAS（比較與交換）實現(xiàn)原理

首先HashMap是Map的一個實現(xiàn)類，而Map存儲形式是鍵值對(key,value)的?？梢钥闯墒且粋€一個的Entry。Entry所存放的位置是由key來決定的。

Map中的key是無序的且不可重復(fù)的，所有的key可以看成是一個set集合，如果出現(xiàn)Map中的key如果是自定義類的對象，則必須重寫hashCode和equals方法，因為如果不重寫，使用的是Object類中的hashCode和equals方法，比較的是內(nèi)存地址值不是比內(nèi)容。

Map中的value是無序的可重復(fù)的，所有的value可以看成是Collection集合，Map中的value如果是自定義類的對象必須重寫equals方法。

至于要重寫hashCode和equals分別做什么用，拿hashMap底層原理來說：

當(dāng)我們向HashMap中存放一個元素(k1,v1)，先根據(jù)k1的hashCode方法來決定在數(shù)組中存放的位置。

如果這個位置沒有其它元素，將(k1,v1)直接放入Node類型的數(shù)組中，這個數(shù)組初始化容量是16，默認(rèn)的加載因子是0.75，也就是當(dāng)元素加到12的時候，底層會進(jìn)行擴(kuò)容，擴(kuò)容為原來的2倍。如果該位置已經(jīng)有其它元素(k2,v2)，那就調(diào)用k1的equals方法和k2進(jìn)行比較二個元素是否相同，如果結(jié)果為true，說明二個元素是一樣的，用v1替換v2，如果返回值為false，二個元素不一樣，就用鏈表的形式將(k1,v1)存放。

不過當(dāng)鏈表中的數(shù)據(jù)較多時，查詢的效率會下降，所以在JDK1.8版本后做了一個升級，hashmap就是當(dāng)鏈表中的元素達(dá)到8并且元素數(shù)量大于64時，會將鏈表替換成紅黑樹才會樹化時，會將鏈表替換成紅黑樹，來提高查找效率。因為對于搜索，插入，刪除操作多的情況下，使用紅黑樹的效率要高一些。

原因是因為紅黑樹是一種特殊的二叉查找樹，二叉查找樹所有節(jié)點的左子樹都小于該節(jié)點，所有節(jié)點的右子樹都大于該節(jié)點，就可以通過大小比較關(guān)系來進(jìn)行快速的檢索。

在紅黑樹上插入或者刪除一個節(jié)點之后，紅黑樹就發(fā)生了變化，可能不滿足紅黑樹的5條性質(zhì)，也就不再是一顆紅黑樹了，而是一顆普通的樹，可以通過左旋和右旋，使這顆樹重新成為紅黑樹。怕大家搞混，我把二個樹之間的區(qū)別給上（紅黑樹與平衡二叉樹的區(qū)別？https://blog.csdn.net/qfc8930858/article/details/89856274）

 

 

而且像這種二叉樹結(jié)構(gòu)比較常見的使用場景是Mysql二種引擎的索引.

首先B樹它的每個節(jié)點都是Key.value的二元組，它的key都是從左到右遞增的排序，value中存儲數(shù)據(jù)。這種模式在讀取數(shù)據(jù)方面的性能很高，因為有單獨的索引文件，Myisam 的存儲文件有三個.frm是表的結(jié)構(gòu)文件，.MYD是數(shù)據(jù)文件，.MYI是索引文件。不過Myisam 也有些缺點它只支持表級鎖，不支持行級鎖也不支持事務(wù)，外鍵等，所以一般用于大數(shù)據(jù)存儲。

 

然后是InnoDB，它的存儲文件相比Myisam少一個索引文件，它是以 ID 為索引的數(shù)據(jù)存儲，數(shù)據(jù)現(xiàn)在都被存在了葉子結(jié)點，索引在非葉結(jié)點上。而這些節(jié)點分散在索引頁上。在InnoDB里，每個頁默認(rèn)16KB，假設(shè)索引的是8B的long型數(shù)據(jù)，每個key后有個頁號4B，還有6B的其他數(shù)據(jù)，那么每個頁的扇出系數(shù)為16KB/(8B+4B+6B)≈1000，即每個頁可以索引1000個key。在高度h=3時，s=1000^3=10億?。∫簿褪钦f，InnoDB通過三次索引頁的I/O，即可索引10億的key，而非葉節(jié)點這一行存儲的索引，數(shù)量就多了，I/O的次數(shù)就少了。而Myisam在每個節(jié)點都存儲數(shù)據(jù)和索引，這樣就減少了每頁存儲的索引數(shù)量。而且InnoDB它還支持行級，表級鎖，也支持事務(wù)，外鍵.

 

 

 另外對于HashMap實際使用過程中還是會出現(xiàn)一些線程安全問題：

HashMap是線程不安全的，在多線程環(huán)境下，使用Hashmap進(jìn)行put操作會引起死循環(huán)，導(dǎo)致CPU利用率接近100%，而且會拋出并發(fā)修改異常，導(dǎo)致原因是并發(fā)爭取線程資源，修改數(shù)據(jù)導(dǎo)致的，一個線程正在寫，一個線程過來爭搶，導(dǎo)致線程寫的過程被其他線程打斷，導(dǎo)致數(shù)據(jù)不一致。

HashTable是線程安全的，只不過實現(xiàn)代價卻太大了，簡單粗暴，get/put所有相關(guān)操作都是synchronized的，這相當(dāng)于給整個哈希表加了一把大鎖。多線程訪問時候，只要有一個線程訪問或操作該對象，那其他線程只能阻塞，相當(dāng)于將所有的操作串行化，在競爭激烈的并發(fā)場景中性能就會非常差。

為了應(yīng)對hashmap在并發(fā)環(huán)境下不安全問題可以使用，ConcurrentHashMap大量的利用了volatile，CAS等技術(shù)來減少鎖競爭對于性能的影響。

在JDK1.7版本中ConcurrentHashMap避免了對全局加鎖，改成了局部加鎖（分段鎖），分段鎖技術(shù)，將數(shù)據(jù)分成一段一段的存儲，然后給每一段數(shù)據(jù)配一把鎖，當(dāng)一個線程占用鎖訪問其中一個段數(shù)據(jù)的時候，其他段的數(shù)據(jù)也能被其他線程訪問，能夠?qū)崿F(xiàn)真正的并發(fā)訪問。不過這種結(jié)構(gòu)的帶來的副作用是Hash的過程要比普通的HashMap要長。

所以在JDK1.8版本中CurrentHashMap內(nèi)部中的value使用volatile修飾，保證并發(fā)的可見性以及禁止指令重排，只不過volatile不保證原子性，使用為了確保原子性，采用CAS（比較交換）這種樂觀鎖來解決。

CAS 操作包含三個操作數(shù) —— 內(nèi)存位置（V）、預(yù)期原值（A）和新值(B)。

如果內(nèi)存地址里面的值和A的值是一樣的，那么就將內(nèi)存里面的值更新成B。CAS是通過無限循環(huán)來獲取數(shù)據(jù)的，若果在第一輪循環(huán)中，a線程獲取地址里面的值被b線程修改了，那么a線程需要自旋，到下次循環(huán)才有可能機(jī)會執(zhí)行。

volatile有三個特性：可見性，不保證原子性，禁止指令重排。

可見性：線程1從主內(nèi)存中拿數(shù)據(jù)1到自己的線程工作空間進(jìn)行操作（假設(shè)是加1）這個時候數(shù)據(jù)1已經(jīng)改為數(shù)據(jù)2了，將數(shù)據(jù)2寫回主內(nèi)存時通知其他線程（線程2，線程3），主內(nèi)存中的數(shù)據(jù)1已改為數(shù)據(jù)2了，讓其他線程重新拿新的數(shù)據(jù)（數(shù)據(jù)2）。

不保證原子性：線程1從主內(nèi)存中拿了一個值為1的數(shù)據(jù)到自己的工作空間里面進(jìn)行加1的操作，值變?yōu)?，寫回主內(nèi)存，然后還沒有來得及通知其他線程，線程1就被線程2搶占了，CPU分配，線程1被掛起，線程2還是拿著原來主內(nèi)存中的數(shù)據(jù)值為1進(jìn)行加1，值變成2，寫回主內(nèi)存，將主內(nèi)存值為2的替換成2，這時線程1的通知到了，線程2重新去主內(nèi)存拿值為2的數(shù)據(jù)。

禁止指令重排：首先指令重排是程序執(zhí)行的時候不總是從上往下執(zhí)行的，就像高考答題，可以先做容易的題目再做難的，這時做題的順序就不是從上往下了。禁止指令重排就杜絕了這種情況。

（一般面試官開始問你會從java基礎(chǔ)問起，一問大多數(shù)會問到集合這一塊，而集合問的較多的是HashMap，這個時候你就可以往這些方向帶著面試官問你，而且擴(kuò)展的深度也夠，所以上面的干貨夠你說個十來分鐘吧，第一個問題拿下后，面試官心里至少簡單你的基礎(chǔ)夠扎實，第一印象分就留下了）