在工作了一段時(shí)間之后，上課的時(shí)候基礎(chǔ)已經(jīng)忘得七七八八了爹耗，今天突然看到群里的朋友問了一些關(guān)于HashMap的面試題耙考，也想著自己整理一下對(duì)HashMap的一些理解

使用過HashMap么？他有什么用處?

只要學(xué)習(xí)過Java的同學(xué)想必都用過HashMap潭兽，HashMap對(duì)于日常的工作中可以方便的存儲(chǔ)一些我們需要存放的對(duì)象倦始，最基礎(chǔ)的便是get/put方法，對(duì)于HashMap的一些特性山卦，比如HashMap是可以儲(chǔ)存null鍵和null值得鞋邑，而與之對(duì)應(yīng)的HashTable則不行，HashMap是非線程安全的账蓉，因此它的速度會(huì)相對(duì)來說快一些枚碗，HashMap儲(chǔ)存的是鍵值對(duì)等等，到此铸本，說明在日常工作中肮雨，對(duì)HashMap的理解還是比較到位的。

你知道HashMap的工作原理嗎箱玷？

• 針對(duì)第一個(gè)問題怨规，其實(shí)HashMap最基礎(chǔ)的就是基于Hashing的原理陌宿，
• 當(dāng)我們給put方法傳遞<K,V>時(shí)，會(huì)首先調(diào)用hashCode方法對(duì)K進(jìn)行哈希值的計(jì)算椅亚，得到哈希值后限番，去bucket中尋找對(duì)應(yīng)的儲(chǔ)存地址，并且把<K,V>儲(chǔ)存進(jìn)當(dāng)前的儲(chǔ)存地址呀舔。
• 當(dāng)調(diào)用get方法的時(shí)候，同樣是尋找相對(duì)應(yīng)的hashCode對(duì)應(yīng)的bucket儲(chǔ)存地址扩灯，并取出相對(duì)應(yīng)的鍵值對(duì)媚赖。

特別要指出的是，當(dāng)K為null時(shí)珠插，HashMap默認(rèn)是儲(chǔ)存在第一個(gè)位置當(dāng)中的惧磺。

HashMap的數(shù)據(jù)結(jié)構(gòu)

HashMap是綜合了鏈表和數(shù)組的產(chǎn)物，先來了解一些鏈表和數(shù)組捻撑，這兩個(gè)相對(duì)來說是兩個(gè)極端的儲(chǔ)存方式磨隘。

• 數(shù)據(jù)是有序存放數(shù)據(jù)的，占用的內(nèi)存集中顾患，因此有插件簡單快速番捂，但是插入和刪除的代價(jià)大
• 鏈表是隨機(jī)存放的，占用的內(nèi)存隨機(jī)江解，通過節(jié)點(diǎn)標(biāo)識(shí)來形成鏈狀結(jié)構(gòu)设预，因此查詢不易，但是插入和刪除比較方便

而HashMap在處理hashCode時(shí)采用的是數(shù)組犁河，而每個(gè)數(shù)組都相當(dāng)于是鏈表的header鳖枕。因此可以想到，在一定的條件下桨螺，HashMap和數(shù)組/List一樣宾符，是需要擴(kuò)容的，會(huì)有一個(gè)reHashing的操作灭翔，然后把之前的數(shù)據(jù)全都存放到新的HashMap中魏烫。默認(rèn)的負(fù)載因子是0.75.

當(dāng)兩個(gè)對(duì)象的hashcode相同時(shí)，調(diào)用put/get會(huì)發(fā)生什么

在剛才我們提到過缠局，put時(shí)調(diào)用hashCode方法會(huì)找到bucket中的位置则奥，然后再該位置進(jìn)行存放，如果兩個(gè)對(duì)象的hashCode相同時(shí)狭园，會(huì)進(jìn)行什么樣的‘碰撞’读处？
有些同學(xué)可能會(huì)覺得就是直接覆蓋，或者因?yàn)閔ashCode相同唱矛，會(huì)拋出異常罚舱，不進(jìn)行儲(chǔ)存井辜。其實(shí)上一段說的數(shù)據(jù)結(jié)構(gòu)，在這里便產(chǎn)生了結(jié)果管闷。在bucket中的某一位置粥脚，對(duì)應(yīng)的實(shí)際是一個(gè)鏈表結(jié)構(gòu)，因此包个，put方法只是在其中又加了一節(jié)鏈表而已刷允。

• 那么問題來了，這個(gè)時(shí)候我們調(diào)用get方法碧囊，獲取到的其實(shí)是一個(gè)鏈表树灶，而不是一個(gè)對(duì)象，難道只是簡單的取最新的一個(gè)么糯而？

• 其實(shí)不是的 天通，因?yàn)樵贖ashMap中不僅是用hashCode做判斷，因?yàn)槲覀冞€會(huì)有equals方法熄驼，在鏈表中像寒，我們又會(huì)采用equals方法找值相等的，就會(huì)得到唯一的一個(gè)對(duì)象瓜贾。

在到達(dá)了負(fù)載因子的情況下诺祸，擴(kuò)容會(huì)發(fā)生什么問題？

在工作中還是比較容易想到的阐虚，就是并發(fā)問題序臂，在多線程的情況下，若兩個(gè)線程都達(dá)到了復(fù)雜因子实束，他們同時(shí)產(chǎn)生擴(kuò)容操作奥秆，便會(huì)產(chǎn)生條件競爭，在擴(kuò)容時(shí)元素的排列順序便會(huì)反序存放咸灿，在條件競爭時(shí)便會(huì)產(chǎn)生死循環(huán)构订。

• 解決方法：并不應(yīng)該局限于如何解決這個(gè)問題。因?yàn)镠ashMap本身就是非線程安全的避矢，完全可以采用并發(fā)包下的CocurrentHashMap

為什么使用String悼瘾，Integer等等wapper比較合適作為K？

因?yàn)樵谏a(chǎn)環(huán)境中审胸，這些是最常用的亥宿，并且在這些類中的hashCode和equals方法都經(jīng)過了重寫，并且是屬于final的不可變的砂沛，因此作為K值可以有效提高查詢效率烫扼。

我們可以使用CocurrentHashMap來代替Hashtable么？

這就需要看實(shí)際的業(yè)務(wù)場景了碍庵，在大多數(shù)情況下映企，我認(rèn)為是可行的悟狱。
這兩個(gè)類相較于HashMap的區(qū)別想必大家都清楚，就是這兩個(gè)類都是線程安全的堰氓，但是兩者之間挤渐，HashTable的線程安全等級(jí)更高一些，但是同樣導(dǎo)致了性能的丟失双絮。

• 具體體現(xiàn)在浴麻，當(dāng)HashTable的大小到達(dá)一定的程度時(shí)，擴(kuò)容操作就會(huì)顯得非常慢掷邦，此時(shí)該Map是被上鎖的白胀，因此導(dǎo)致它的即時(shí)性能急劇下降，同時(shí)也就意味著抚岗，即便兩個(gè)線程操作不同的數(shù)據(jù)，也會(huì)因整體上鎖而需要等待哪怔。
• 而CocurrentHashMap采用了分割的概念宣蔚，也就是分塊治理的，因此不管整體的數(shù)據(jù)量有多大认境，只需要擴(kuò)容部分?jǐn)?shù)據(jù)胚委，而其他部分則不會(huì)受到影響，同樣的叉信，可以理解不同線程操作不同的數(shù)據(jù)時(shí)亩冬，可以給不同的區(qū)塊上鎖，相當(dāng)于在一定程度下允許了同時(shí)有多線程操作硼身，有效提升了他的性能硅急。