java中Map有哪些实现类
?Java中的map是一個很重要的集合,他是一個接口,下面繼承它實現了多個實現類,這些類各有千秋,各自有個各自的優點和缺點
?
如下圖
??map的主要特點是鍵值對的形式,一一對應,且一個key只對應1個value。其常用的map實現類主要有HashMap、HashTable、TreeMap、ConcurrentHashMap、LinkedHashMap、weakHashMap等等。
?
1、HashMap
??????使用位桶和鏈表實現(最近的jdk1.8改用紅黑樹存儲而非鏈表),它是線程不安全的Map,方法上都沒有synchronize關鍵字修飾
最常用的Map,根據鍵的hashcode值來存儲數據,根據鍵可以直接獲得他的值(因為相同的鍵hashcode值相同,在地址為hashcode值的地方存儲的就是值,所以根據鍵可以直接獲得值),具有很快的訪問速度,遍歷時,取得數據的順序完全是隨機的,HashMap最多只允許一條記錄的鍵為null,允許多條記錄的值為null,HashMap不支持線程同步,即任意時刻可以有多個線程同時寫HashMap,這樣對導致數據不一致,如果需要同步,可以使用synchronziedMap的方法使得HashMap具有同步的能力或者使用concurrentHashMap
2、HashTable
???????HashTable是線程安全的一個map實現類,它實現線程安全的方法是在各個方法上添加了synchronize關鍵字。但是現在已經不再推薦使用HashTable了,因為現在有了ConcurrentHashMap這個專門用于多線程場景下的map實現類,其大大優化了多線程下的性能。
3、ConcurrentHashMap
???????如果你經常參加面試,一定會被問到這個map實現類,這個map實現類是在jdk1.5中加入的,其在jdk1.6/1.7中的主要實現原理是segment段鎖,它不再使用和HashTable一樣的synchronize一樣的關鍵字對整個方法進行枷鎖,而是轉而利用segment段落鎖來對其進行加鎖,以保證Map的多線程安全。
?????其實可以理解為,一個ConcurrentHashMap是由多個HashTable組成,所以它允許獲取不用段鎖的線程同時持有該資源,segment有多少個,理論上就可以同時有多少個線程來持有它這個資源。
?????其默認的segment是一個數組,默認長度為16。也就是說理論商可以提高16倍的性能。
? ? ?但是要注意咯,在JAVA的jdk1.8中則對ConcurrentHashMap又再次進行了大的修改,取消了segment段鎖字段,采用了CAS+Synchronize技術來保障線程安全。底層采用數組+鏈表+紅黑樹的存儲結構,也就是和HashMap一樣。這里注意Node其實就是保存一個鍵值對的最基本的對象。其中Value和next都是使用的volatile關鍵字進行了修飾,以確保線程安全
?在插入元素時,會首先進行CAS判定,如果OK就插入其中,并將size+1,但是如果失敗了,就會通過自旋鎖自旋后再次嘗試插入,直到成功。
????所謂的CAS也就是compare And Swap,即在更改前先對內存中的變量值和你指定的那個變量值進行比較,如果相同這說明在這期間沒有被修改過,則可以進行修改,而如果不一樣了,則就要停止修改,否則就會覆蓋掉其他的參數。即內存值a,舊值b,和要修改的值c,如果這里a=b,那么就可以進行更新,就可以將內存值a修改成c。否則就要終止該更新操作。
????為什么這里會用volatile進行修飾,我在其他博客找到了答案。主要有兩個用處:
1、令這個被修飾的變量的更新具有可見性,一旦該變量遭到了修改,其他線程立馬就會知道,立馬放棄自己在自己工作內存中持有的該變量值,轉而重新去主內存中獲取到最新的該變量值。
2、產生了內存屏障,這里volatile可以保證CPU在執行代碼時保證,所有被volatile中被修飾的之前的一定在之前被執行,也就是所謂的“指令重排序”。
????同hashMap一樣,在JDK1.8中,如果鏈表中存儲的Entry超過了8個則就會自動轉換鏈表為紅黑樹,提高查詢效率。
?
4、TreeMap
?????TreeMap也是一個很常用的map實現類,因為他具有一個很大的特點就是會對Key進行排序,使用了TreeMap存儲鍵值對,再使用iterator進行輸出時,會發現其默認采用key由小到大的順序輸出鍵值對,如果想要按照其他的方式來排序,需要重寫也就是override 它的compartor接口
?
? ? 另外,TreeMap底層的存儲結構也是一顆紅黑樹。是不是發現好多都是紅黑樹,沒錯因為紅黑樹查找效率高,只有O(lgn)。它是一種自平衡的二叉查找樹。在每次插入和刪除節點時,都可以自動調節樹結構,以保證樹的高度是lgn。
?
5、LinkedHashMap
是HahsMap的一個子類,但它保持了記錄的插入順序,遍歷時先得到的肯定是先插入的,也可以在構造時帶參數,按照應用次數排序,在遍歷時會比HahsMap慢,不過有個例外,當HashMap的容量很大,實際數據少時,遍歷起來會比LinkedHashMap慢(因為它是鏈啊),因為HashMap的遍歷速度和它容量有關,LinkedHashMap遍歷速度只與數據多少有關
????LinkedHashMap它的特點主要在于linked,帶有這個字眼的就表示底層用的是鏈表來進行的存儲。相對于其他的無序的map實現類,還有像TreeMap這樣的排序類,linkedHashMap最大的特點在于有序,但是它的有序主要體現在先進先出FIFIO上。沒錯,LinkedHashMap主要依靠雙向鏈表和hash表來實現的。
?
仔細看,這里雖然在計算hashcode時還是發生了hash沖突,采用了鏈地址法解決了沖突,但是這里的Entry對象是采用雙向鏈表保存的,每個Entry都有一個after和before的屬性。當插入一個entry時,如果發生了沖突,就可以將新的Entry插入Entry鏈表中的頭部,但是按照雙向鏈表的角度來說,又會將該Entry插入到雙向鏈表的尾部。
6、weakHashMap
????首先,weakHashMap它是一個“弱鍵”,它的Key值和Value都可以是null,而且其Map中如果這個Key值指向的對象沒被使用,此時觸發了GC,該對象就會被回收掉的。其原理主要是使用的WeakReference和ReferenceQueue實現的,其key就是weakReference,而ReferenceQueue中保存了被回收的 Key-Value。
????如果當其中一個Key-Value不再使用被回收時,就將其加入ReferenceQueue隊列中。當下次再次調用該WeakHashMap時,就會去更新該map,比如ReferenceQueue中的key-value,將其中包含的key-value全部刪除掉。這就是所謂的“自動刪除”。
?
創作挑戰賽新人創作獎勵來咯,堅持創作打卡瓜分現金大獎總結
以上是生活随笔為你收集整理的java中Map有哪些实现类的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: 什么是智慧房屋租赁系统
- 下一篇: socket编程(java实现)