摘要:與中的類似,也是一個數組加鏈表,不過這個線程安全。線程安全,但是它的線程安全是依賴將所有修改的代碼塊都用修飾。這是中實現線程安全的思路,由個組成,每個就相當于一個數組鏈表。線程安全,但性能差,不推薦使用。
問題描述 翻翻別人的面試經歷
這里在知乎上看到的,分享出了自己面試阿里Java崗的面試題。
看了一下,除了Spring之外的其他很多題都不會,但是不能拿學校沒講Java作為借口,因為可能講了也不會。
但是第九個問題,我覺得應該立刻話時間研究研究了,因為之前在緩存中用到了這個。
當時也不明白具體HashMap和ConcurrentHashMap究竟有什么區別。
只是記得之前看過有關大數據的場景下利用緩存減輕數據庫壓力的文章,文中說常用ConcurrentHashMap,所以這里緩存就用這個了,其實并不懂原理,下面,讓我們一起來研究一下。
MapMap大家都熟悉了,Java中也有,JavaScript中也有。
Map是一種鍵值對類型的數據結構,根據鍵映射到值。
不分析源碼了,就把思想給大家講一下,以下主要以圖為主。
HashMap Java7HashMap的本質是一個可變長度的數組,在數組中每個位置保存的是一個Entry節點,該節點存儲有hash、key、value、next等信息。
Java7中的HashMap實現與我們在數據結構中學習的類似,對key進行hash,如果沖突了,則添加到鏈表中。
然后查詢的時候就先根據hash找到相應的位置,然后根據鏈表逐一比較,返回相應的value。時間復雜度取決于鏈表的長度,時間復雜度為O(N)。
Java8Java8中對HashMap進行了優化,如果鏈表中元素超過8個時,就將鏈表轉化為紅黑樹,以減少查詢的復雜度,將時間復雜度降低為O(logN)。
HashMap沒有對多線程的場景下做任何的處理,不用說別的,就兩個線程同時put,然后沖突了,兩者需要操作一個鏈表/紅黑樹,這肯定就會有錯誤發生,所以HashMap是線程不安全的。
HashTableHashTable與Java7中的HashMap類似,也是一個數組加鏈表,不過這個線程安全。
HashTable線程安全,但是它的線程安全是依賴將所有修改HashTable的代碼塊都用synchronized修飾。
synchronized關鍵字我們之前在單例模式中用到過,它修飾的代碼塊,同一時刻只允許一個線程訪問,其他線程會被阻塞,等待該線程執行完再執行。
所以,在HashTable中,一個線程在put,其余的線程在get的時候就會被阻塞,無法并行。所以不推薦使用HashTable,雖然它線程安全。
ConcurrentHashMapHashMap線程不安全,HashTable性能又不好,當然需要設計一個新類去解決這些問題,這就是ConcurrentHashMap。
Java7這是Java7中實現線程安全的思路,ConcurrentHashMap由16個segment組成,每個segment就相當于一個HashMap(數組+鏈表)。
segment最多16個,想要擴容,就是擴充每個segment中數組的長度。
然后只要實現每個segment是線程安全的,就讓這個Map線程安全了。每個segment是加鎖的,對修改segment的操作加鎖,不影響其他segment的使用,所以理想情況下,最多支持16個線程并發修改segment,這16個線程分別訪問不同的segment。
同時,在segment加鎖時,所有讀線程是不會受到阻塞的。
這樣設計,put與get的基本操作就是先找segment,再找segment中的數組位置,再查鏈表。
Java8后來人們發現Java7這樣設計太復雜了,回歸本質。
HashMap線程不安全的問題完全都是出在對鏈表/紅黑樹的操作上,為什么非要建一個segment加鎖呢?直接對鏈表/紅黑樹加鎖不就好了?
所以Java8的ConcurrentHashMap完全就是HashMap進行加鎖,實現線程安全。
這里總結的很簡單,其實源碼中對這個的實現特別復雜,有興趣的可以去看看,反正我是看著頭大。
總結HashMap線程不安全。
HashTable線程安全,但性能差,不推薦使用。
ConcurrentHashMap線程安全。
ConcurrentHashMap在Java7中使用segment實現,對每個segment加鎖。
ConcurrentHashMap在Java8中是直接在HashMap的基礎上進行加鎖。
參考文獻:
Java7/8 中的 HashMap 和 ConcurrentHashMap 全解析
ConcurrentHashMap、HashTable、HashMap三兄弟
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/76851.html
摘要:若遇到哈希沖突,則將沖突的值加到鏈表中即可。之后相比于之前的版本,之后在解決哈希沖突時有了較大的變化,當鏈表長度大于閾值默認為時,將鏈表轉化為紅黑樹,以減少搜索時間。有序,唯一紅黑樹自平衡的排序二叉樹。 本文是最最最常見Java面試題總結系列第三周的文章。主要內容: Arraylist 與 LinkedList 異同 ArrayList 與 Vector 區別 HashMap的底層...
摘要:中的使用及在中的沖突方案引言簡稱是在作為的替代選擇新引入的,是包的重要成員。為了解決在頻繁沖突時性能降低的問題,中使用平衡樹來替代鏈表存儲沖突的元素。目前,只有和會在頻繁沖突的情況下使用平衡樹。 java中ConcurrentHashMap的使用及在Java 8中的沖突方案 1、引言 ConcurrentHashMap(簡稱CHM)是在Java 1.5作為Hashtable的替代選擇新...
摘要:如下代碼省略相關代碼省略相關代碼可以看到在里面,是直接采用數組鏈表紅黑樹來實現,時間復雜度在和之間,如果鏈表轉化為紅黑樹了,那么就是到。 在JDK1.8里面,ConcurrentHashMap在put方法里面已經將分段鎖移除了,轉而是CAS鎖和synchronized ConcurrentHashMap是Java里面同時兼顧性能和線程安全的一個鍵值對集合,同屬于鍵值對的集合還有Hash...
摘要:我們都接觸這些集合類,這些在包的集合類就都是快速失敗的而包下的類都是安全失敗,比如。安全失敗明白了什么是快速失敗之后,安全失敗也是非常好理解的。最后說明一下,快速失敗和安全失敗是對迭代器而言的。 什么是快速失?。╢ail-fast)和安全失敗(fail-safe)?它們又和什么內容有關系。以上兩點就是這篇文章的內容,廢話不多話,正文請慢用。 我們都接觸 HashMap、ArrayLis...
摘要:和的區別和的區別是,在操作的方法上加入關鍵字,使得線程安全。使用進行比較,或者傳入的比較器?;?,它自己的任務主要是維護保持順序的雙向鏈表。和的區別提供了一個高效的線程安全的訪問和更新的方式。在中的過程和類似。 HashTable和HashMap的區別 HashTable和HashMap的區別是,HashTable在操作table的方法上加入synchronized關鍵字,使得線程安全...
閱讀 2060·2021-11-23 09:51
閱讀 3353·2021-09-28 09:36
閱讀 1120·2021-09-08 09:35
閱讀 1758·2021-07-23 10:23
閱讀 3258·2019-08-30 15:54
閱讀 2998·2019-08-29 17:05
閱讀 438·2019-08-29 13:23
閱讀 1294·2019-08-28 17:51