這周真是發(fā)生了不少事,腦袋和心里一直都很亂,周二參加了一場面試,經(jīng)歷了筆試+3輪面試,周五正式提交了離職申請。要開始新的征程了,意外的有些失落和不舍,畢竟是畢業(yè)后的第一份工作,畢竟在這認(rèn)識了一群可愛的人,畢竟在這學(xué)到了很多東西,畢竟這有8000+的aeron chair!!!。可既然已經(jīng)做了選擇就沒有退路了,勇敢往下走吧,希望接下來的三周可以把手頭上的工作做好交接善始善終,也希望以后不會后悔今天的選擇。
進(jìn)入正題,在周二面試時(shí),一面的面試官有問到 HashMap 是否是線程安全的,如何在線程安全的前提下使用 HashMap,其實(shí)也就是 HashMap
,Hashtable
,ConcurrentHashMap
和 synchronized Map
的原理和區(qū)別。當(dāng)時(shí)有些緊張只是簡單說了下HashMap不是線程安全的;Hashtable 線程安全,但效率低,因?yàn)槭?Hashtable 是使用 synchronized 的,所有線程競爭同一把鎖;而 ConcurrentHashMap 不僅線程安全而且效率高,因?yàn)樗粋€(gè) segment 數(shù)組,將數(shù)據(jù)分段存儲,給每一段數(shù)據(jù)配一把鎖,也就是所謂的鎖分段技術(shù)。當(dāng)時(shí)忘記了 synchronized Map 和解釋一下 HashMap 為什么線程不安全。面試結(jié)束后問了下面試官哪里有些不足,面試官說上面這個(gè)問題的回答算過關(guān),但可以在深入一些或者自己動手嘗試一下。so~~~雖然拿到了 offer,但還是再整理一下,不能得過且過啊。
為什么HashMap是線程不安全的
總說 HashMap 是線程不安全的,不安全的,不安全的,那么到底為什么它是線程不安全的呢?要回答這個(gè)問題就要先來簡單了解一下 HashMap 源碼中的使用的存儲結(jié)構(gòu)
(這里引用的是 Java 8 的源碼,與7是不一樣的)和它的擴(kuò)容機(jī)制
。
HashMap的內(nèi)部存儲結(jié)構(gòu)
下面是 HashMap 使用的存儲結(jié)構(gòu):
|
|
可以看到 HashMap 內(nèi)部存儲使用了一個(gè) Node 數(shù)組(默認(rèn)大小是16),而 Node 類包含一個(gè)類型為 Node 的 next 的變量,也就是相當(dāng)于一個(gè)鏈表,所有根據(jù) hash 值計(jì)算的 bucket 一樣的 key 會存儲到同一個(gè)鏈表里(即產(chǎn)生了沖突),大概就是下面圖的樣子(順便推薦個(gè)在線畫圖的網(wǎng)站Creately)。HashMap內(nèi)部存儲結(jié)果
需要注意的是,在 Java 8 中如果 hash 值相同的 key 數(shù)量大于指定值(默認(rèn)是8)時(shí)使用平衡樹來代替鏈表,這會將get()方法的性能從O(n)提高到O(logn)。具體的可以看我的另一篇博客Java 8中HashMap和LinkedHashMap如何解決沖突。
HashMap的自動擴(kuò)容機(jī)制
HashMap 內(nèi)部的 Node 數(shù)組默認(rèn)的大小是16,假設(shè)有100萬個(gè)元素,那么最好的情況下每個(gè) hash 桶里都有62500個(gè)元素??,這時(shí)get(),put(),remove()等方法效率都會降低。為了解決這個(gè)問題,HashMap 提供了自動擴(kuò)容機(jī)制,當(dāng)元素個(gè)數(shù)達(dá)到數(shù)組大小 loadFactor 后會擴(kuò)大數(shù)組的大小,在默認(rèn)情況下,數(shù)組大小為16,loadFactor 為0.75,也就是說當(dāng) HashMap 中的元素超過16\0.75=12時(shí),會把數(shù)組大小擴(kuò)展為2*16=32,并且重新計(jì)算每個(gè)元素在新數(shù)組中的位置。如下圖所示(圖片來源,權(quán)侵刪)。自動擴(kuò)容
從圖中可以看到?jīng)]擴(kuò)容前,獲取 EntryE 需要遍歷5個(gè)元素,擴(kuò)容之后只需要2次。
為什么線程不安全
個(gè)人覺得 HashMap 在并發(fā)時(shí)可能出現(xiàn)的問題主要是兩方面,首先如果多個(gè)線程同時(shí)使用put方法添加元素,而且假設(shè)正好存在兩個(gè) put 的 key 發(fā)生了碰撞(根據(jù) hash 值計(jì)算的 bucket 一樣),那么根據(jù) HashMap 的實(shí)現(xiàn),這兩個(gè) key 會添加到數(shù)組的同一個(gè)位置,這樣最終就會發(fā)生其中一個(gè)線程的 put 的數(shù)據(jù)被覆蓋。第二就是如果多個(gè)線程同時(shí)檢測到元素個(gè)數(shù)超過數(shù)組大小* loadFactor ,這樣就會發(fā)生多個(gè)線程同時(shí)對 Node 數(shù)組進(jìn)行擴(kuò)容,都在重新計(jì)算元素位置以及復(fù)制數(shù)據(jù),但是最終只有一個(gè)線程擴(kuò)容后的數(shù)組會賦給 table,也就是說其他線程的都會丟失,并且各自線程 put 的數(shù)據(jù)也丟失。
關(guān)于 HashMap 線程不安全這一點(diǎn),《Java并發(fā)編程的藝術(shù)》一書中是這樣說的:
HashMap 在并發(fā)執(zhí)行 put 操作時(shí)會引起死循環(huán),導(dǎo)致 CPU 利用率接近100%。因?yàn)槎嗑€程會導(dǎo)致 HashMap 的 Node 鏈表形成環(huán)形數(shù)據(jù)結(jié)構(gòu),一旦形成環(huán)形數(shù)據(jù)結(jié)構(gòu),Node 的 next 節(jié)點(diǎn)永遠(yuǎn)不為空,就會在獲取 Node 時(shí)產(chǎn)生死循環(huán)。
哇塞,聽上去si不si好神奇,居然會產(chǎn)生死循環(huán)。。。。 google 了一下,才知道死循環(huán)并不是發(fā)生在 put 操作時(shí),而是發(fā)生在擴(kuò)容時(shí)。詳細(xì)的解釋可以看下面幾篇博客:
如何線程安全的使用HashMap
了解了 HashMap 為什么線程不安全,那現(xiàn)在看看如何線程安全的使用 HashMap。這個(gè)無非就是以下三種方式:
- Hashtable
- ConcurrentHashMap
- Synchronized Map
例子:
|
|
依次來看看。
Hashtable
先稍微吐槽一下,為啥命名不是 HashTable 啊,看著好難受??,不管了就裝作它叫HashTable 吧。這貨已經(jīng)不常用了,就簡單說說吧。HashTable 源碼中是使用 synchronized
來保證線程安全的,比如下面的 get 方法和 put 方法:
|
|
所以當(dāng)一個(gè)線程訪問 HashTable 的同步方法時(shí),其他線程如果也要訪問同步方法,會被阻塞住。舉個(gè)例子,當(dāng)一個(gè)線程使用 put 方法時(shí),另一個(gè)線程不但不可以使用 put 方法,連 get 方法都不可以,好霸道啊!!!so~~,效率很低,現(xiàn)在基本不會選擇它了。
ConcurrentHashMap
ConcurrentHashMap (以下簡稱CHM)是 JUC 包中的一個(gè)類,Spring 的源碼中有很多使用 CHM 的地方。之前已經(jīng)翻譯過一篇關(guān)于 ConcurrentHashMap 的博客,如何在java中使用ConcurrentHashMap,里面介紹了 CHM 在 Java 中的實(shí)現(xiàn),CHM 的一些重要特性和什么情況下應(yīng)該使用 CHM。需要注意的是,上面博客是基于 Java 7 的,和8有區(qū)別,在8中 CHM 摒棄了 Segment(鎖段)的概念,而是啟用了一種全新的方式實(shí)現(xiàn),利用 CAS 算法,有時(shí)間會重新總結(jié)一下。
SynchronizedMap
看了一下源碼,SynchronizedMap 的實(shí)現(xiàn)還是很簡單的。
|
|
從源碼中可以看出調(diào)用 synchronizedMap() 方法后會返回一個(gè) SynchronizedMap 類的對象,而在 SynchronizedMap 類中使用了 synchronized 同步關(guān)鍵字來保證對 Map 的操作是線程安全的。
性能對比
這是要靠數(shù)據(jù)說話的時(shí)代,所以不能只靠嘴說 CHM 快,它就快了。寫個(gè)測試用例,實(shí)際的比較一下這三種方式的效率(源碼來源),下面的代碼分別通過三種方式創(chuàng)建 Map 對象,使用 ExecutorService
來并發(fā)運(yùn)行5個(gè)線程,每個(gè)線程添加/獲取500K個(gè)元素。
|
|
測試結(jié)果:
|
|
這個(gè)就不用廢話了,CHM 性能是明顯優(yōu)于 Hashtable 和 SynchronizedMap 的,CHM 花費(fèi)的時(shí)間比前兩個(gè)的一半還少,哈哈,以后再有人問就可以甩數(shù)據(jù)了。
歡迎指正錯(cuò)誤,歡迎一起討論。另外,針對提離職當(dāng)天發(fā)生的一個(gè)小插曲,真真是給我上了一課,不是所有人都能接受實(shí)話的,只想引用歡樂頌里安迪的一句話:常與同好爭高下,不與傻瓜論短長。