Map映射LinkedHashSet與LinkedHashMap應(yīng)用解析
總體介紹
如果你已看過前面關(guān)于HashSet和HashMap,以及TreeSet和TreeMap的講解,一定能夠想到本文將要講解的LinkedHashSet和LinkedHashMap其實(shí)也是一回事。LinkedHashSet和LinkedHashMap在Java里也有著相同的實(shí)現(xiàn),前者僅僅是對(duì)后者做了一層包裝,也就是說LinkedHashSet里面有一個(gè)LinkedHashMap(適配器模式)。因此本文將重點(diǎn)分析LinkedHashMap。
LinkedHashMap實(shí)現(xiàn)了Map接口,即允許放入key
為null
的元素,也允許插入value
為null
的元素。從名字上可以看出該容器是linked list和HashMap的混合體,也就是說它同時(shí)滿足HashMap和linked list的某些特性??蓪inkedHashMap看作采用linked list增強(qiáng)的HashMap。
事實(shí)上LinkedHashMap是HashMap的直接子類,二者唯一的區(qū)別是LinkedHashMap在HashMap的基礎(chǔ)上,采用雙向鏈表(doubly-linked list)的形式將所有entry
連接起來,這樣是為保證元素的迭代順序跟插入順序相同。上圖給出了LinkedHashMap的結(jié)構(gòu)圖,主體部分跟HashMap完全一樣,多了header
指向雙向鏈表的頭部(是一個(gè)啞元),該雙向鏈表的迭代順序就是entry
的插入順序。
除了可以保迭代歷順序,這種結(jié)構(gòu)還有一個(gè)好處 : 迭代LinkedHashMap時(shí)不需要像HashMap那樣遍歷整個(gè)table
,而只需要直接遍歷header
指向的雙向鏈表即可,也就是說LinkedHashMap的迭代時(shí)間就只跟entry
的個(gè)數(shù)相關(guān),而跟table
的大小無關(guān)。
有兩個(gè)參數(shù)可以影響LinkedHashMap的性能: 初始容量(inital capacity)和負(fù)載系數(shù)(load factor)。初始容量指定了初始table
的大小,負(fù)載系數(shù)用來指定自動(dòng)擴(kuò)容的臨界值。當(dāng)entry
的數(shù)量超過capacity*load_factor
時(shí),容器將自動(dòng)擴(kuò)容并重新哈希。對(duì)于插入元素較多的場(chǎng)景,將初始容量設(shè)大可以減少重新哈希的次數(shù)。
將對(duì)象放入到LinkedHashMap或LinkedHashSet中時(shí),有兩個(gè)方法需要特別關(guān)心: hashCode()
和equals()
。hashCode()
方法決定了對(duì)象會(huì)被放到哪個(gè)bucket
里,當(dāng)多個(gè)對(duì)象的哈希值沖突時(shí),equals()
方法決定了這些對(duì)象是否是“同一個(gè)對(duì)象”。所以,如果要將自定義的對(duì)象放入到LinkedHashMap
或LinkedHashSet
中,需要@Override hashCode()
和equals()
方法。
通過如下方式可以得到一個(gè)跟源Map 迭代順序一樣的LinkedHashMap:
void foo(Map m) { Map copy = new LinkedHashMap(m); ... }
出于性能原因,LinkedHashMap是非同步的(not synchronized),如果需要在多線程環(huán)境使用,需要程序員手動(dòng)同步;或者通過如下方式將LinkedHashMap包裝成(wrapped)同步的:
Map m = Collections.synchronizedMap(new LinkedHashMap(...));
LinkedHashMap
get()
get(Object key)
方法根據(jù)指定的key
值返回對(duì)應(yīng)的value
。該方法跟HashMap.get()
方法的流程幾乎完全一樣
put()
put(K key, V value)
方法是將指定的key, value
對(duì)添加到map
里。
該方法首先會(huì)對(duì)map
做一次查找,看是否包含該元組,如果已經(jīng)包含則直接返回,查找過程類似于get()
方法;如果沒有找到,則會(huì)通過addEntry(int hash, K key, V value, int bucketIndex)
方法插入新的entry
。
注意,這里的插入有兩重含義:
從table
的角度看,新的entry
需要插入到對(duì)應(yīng)的bucket
里,當(dāng)有哈希沖突時(shí),采用頭插法將新的entry
插入到?jīng)_突鏈表的頭部。
從header
的角度看,新的entry
需要插入到雙向鏈表的尾部。
addEntry()
源碼如下:
// LinkedHashMap.addEntry() void addEntry(int hash, K key, V value, int bucketIndex) { if ((size >= threshold) && (null != table[bucketIndex])) { resize(2 * table.length);// 自動(dòng)擴(kuò)容,并重新哈希 hash = (null != key) ? hash(key) : 0; bucketIndex = hash & (table.length-1);// hash%table.length } // 1.在沖突鏈表頭部插入新的entry HashMap.Entry<K,V> old = table[bucketIndex]; Entry<K,V> e = new Entry<>(hash, key, value, old); table[bucketIndex] = e; // 2.在雙向鏈表的尾部插入新的entry e.addBefore(header); size++; }
上述代碼中用到了addBefore()
方法將新entry e
插入到雙向鏈表頭引用header
的前面,這樣e
就成為雙向鏈表中的最后一個(gè)元素。addBefore()
的源碼如下:
// LinkedHashMap.Entry.addBefor(),將this插入到existingEntry的前面 private void addBefore(Entry<K,V> existingEntry) { after = existingEntry; before = existingEntry.before; before.after = this; after.before = this; }
上述代碼只是簡(jiǎn)單修改相關(guān)entry
的引用而已。
remove()
remove(Object key)
的作用是刪除key
值對(duì)應(yīng)的entry
,該方法的具體邏輯是在removeEntryForKey(Object key)
里實(shí)現(xiàn)的。
removeEntryForKey()
方法會(huì)首先找到key
值對(duì)應(yīng)的entry
,然后刪除該entry
(修改鏈表的相應(yīng)引用)。查找過程跟get()
方法類似。
注意,這里的刪除也有兩重含義:
從table
的角度看,需要將該entry
從對(duì)應(yīng)的bucket
里刪除,如果對(duì)應(yīng)的沖突鏈表不空,需要修改沖突鏈表的相應(yīng)引用。
從header
的角度來看,需要將該entry
從雙向鏈表中刪除,同時(shí)修改鏈表中前面以及后面元素的相應(yīng)引用。
removeEntryForKey()
對(duì)應(yīng)的源碼如下:
// LinkedHashMap.removeEntryForKey(),刪除key值對(duì)應(yīng)的entry final Entry<K,V> removeEntryForKey(Object key) { ...... int hash = (key == null) ? 0 : hash(key); int i = indexFor(hash, table.length);// hash&(table.length-1) Entry<K,V> prev = table[i];// 得到?jīng)_突鏈表 Entry<K,V> e = prev; while (e != null) {// 遍歷沖突鏈表 Entry<K,V> next = e.next; Object k; if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {// 找到要?jiǎng)h除的entry modCount++; size--; // 1. 將e從對(duì)應(yīng)bucket的沖突鏈表中刪除 if (prev == e) table[i] = next; else prev.next = next; // 2. 將e從雙向鏈表中刪除 e.before.after = e.after; e.after.before = e.before; return e; } prev = e; e = next; } return e; }
LinkedHashSet
前面已經(jīng)說過LinkedHashSet是對(duì)LinkedHashMap的簡(jiǎn)單包裝,對(duì)LinkedHashSet的函數(shù)調(diào)用都會(huì)轉(zhuǎn)換成合適的LinkedHashMap方法,因此LinkedHashSet的實(shí)現(xiàn)非常簡(jiǎn)單,這里不再贅述。
public class LinkedHashSet<E> extends HashSet<E> implements Set<E>, Cloneable, java.io.Serializable { ...... // LinkedHashSet里面有一個(gè)LinkedHashMap public LinkedHashSet(int initialCapacity, float loadFactor) { map = new LinkedHashMap<>(initialCapacity, loadFactor); } ...... public boolean add(E e) { //簡(jiǎn)單的方法轉(zhuǎn)換 return map.put(e, PRESENT)==null; } ...... }
LinkedHashMap經(jīng)典用法
LinkedHashMap除了可以保證迭代順序外?c;還有一個(gè)非常有用的用法: 可以輕松實(shí)現(xiàn)一個(gè)采用了FIFO替換策略的緩存。具體說來,LinkedHashMap有一個(gè)子類方法
protected boolean removeEldestEntry(Map.Entry<K,V> eldest)
該方法的作用是告訴Map是否要?jiǎng)h除“最老”的Entry,所謂最老就是當(dāng)前Map中最早插入的Entry,如果該方法返回true
,最老的那個(gè)元素就會(huì)被刪除。在每次插入新元素的之后LinkedHashMap會(huì)自動(dòng)詢問removeEldestEntry()是否要?jiǎng)h除最老的元素。這樣只需要在子類中重載該方法,當(dāng)元素個(gè)數(shù)超過一定數(shù)量時(shí)讓removeEldestEntry()返回true,就能夠?qū)崿F(xiàn)一個(gè)固定大小的FIFO策略的緩存。示例代碼如下:
/** 一個(gè)固定大小的FIFO替換策略的緩存 */ class FIFOCache<K, V> extends LinkedHashMap<K, V>{ private final int cacheSize; public FIFOCache(int cacheSize){ this.cacheSize = cacheSize; } // 當(dāng)Entry個(gè)數(shù)超過cacheSize時(shí),刪除最老的Entry @Override protected boolean removeEldestEntry(Map.Entry<K,V> eldest) { return size() > cacheSize; } }
以上就是Map映射LinkedHashSet與LinkedHashMap示例解析的詳細(xì)內(nèi)容,更多關(guān)于Map映射LinkedHashSet與LinkedHashMap的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章!
相關(guān)文章
通過實(shí)例學(xué)習(xí)JAVA對(duì)象轉(zhuǎn)成XML輸出
這篇文章主要介紹了通過實(shí)例學(xué)習(xí)JAVA對(duì)象轉(zhuǎn)成XML輸出,做流程圖的項(xiàng)目時(shí),新的流程定義為xml的,需要對(duì)xml與java對(duì)象進(jìn)行互轉(zhuǎn),下面我們來深入學(xué)習(xí),需要的朋友可以參考下2019-06-06詳解Java的Struts2框架的結(jié)構(gòu)及其數(shù)據(jù)轉(zhuǎn)移方式
這篇文章主要介紹了詳解Java的Struts2框架的結(jié)構(gòu)及其數(shù)據(jù)轉(zhuǎn)移方式,Struts框架是Java的SSH三大web開發(fā)框架之一,需要的朋友可以參考下2016-01-01Spring Boot學(xué)習(xí)入門之AOP處理請(qǐng)求詳解
AOP為Aspect Oriented Programming的縮寫,意為:面向切面編程,通過預(yù)編譯方式和運(yùn)行期動(dòng)態(tài)代理實(shí)現(xiàn)程序功能的統(tǒng)一維護(hù)的一種技術(shù),下面這篇文章主要給大家介紹了關(guān)于Spring Boot學(xué)習(xí)入門之AOP處理請(qǐng)求的相關(guān)資料,需要的朋友可以參考下。2017-09-09Java 實(shí)現(xiàn)并發(fā)的幾種方式小結(jié)
這篇文章主要介紹了Java 實(shí)現(xiàn)并發(fā)的幾種方式小結(jié),具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2021-05-05如何正確控制springboot中bean的加載順序小結(jié)篇
這篇文章主要介紹了如何正確控制springboot中bean的加載順序總結(jié),本文給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2020-07-07java線程池prestartCoreThread prestartAllCoreThreads的預(yù)熱源碼解讀
這篇文章主要介紹了java線程池prestartCoreThread prestartAllCoreThreads的預(yù)熱源碼解讀,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2023-10-10