程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> JAVA編程 >> JAVA綜合教程 >> Java集合深入學習總結-LinkedHashMap

Java集合深入學習總結-LinkedHashMap

編輯:JAVA綜合教程

Java集合深入學習總結-LinkedHashMap


1. LinkedHashMap概述:

LinkedHashMap是Map接口的哈希表和鏈接列表實現,具有可預知的迭代順序。此實現提供所有可選的映射操作,並允許使用null值和null鍵。此類不保證映射的順序,特別是它不保證該順序恆久不變。
LinkedHashMap實現與HashMap的不同之處在於,後者維護著一個運行於所有條目的雙重鏈接列表。此鏈接列表定義了迭代順序,該迭代順序可以是插入順序或者是訪問順序。
注意,此實現不是同步的。如果多個線程同時訪問鏈接的哈希映射,而其中至少一個線程從結構上修改了該映射,則它必須保持外部同步。

2. LinkedHashMap的實現:

對於LinkedHashMap而言,它繼承與HashMap、底層使用哈希表與雙向鏈表來保存所有元素。其基本操作與父類HashMap相似,它通過重寫父類相關的方法,來實現自己的鏈接列表特性。下面我們來分析LinkedHashMap的源代碼:

1) Entry元素:

LinkedHashMap采用的hash算法和HashMap相同,但是它重新定義了數組中保存的元素Entry,該Entry除了保存當前對象的引用外,還保存了其上一個元素before和下一個元素after的引用,從而在哈希表的基礎上又構成了雙向鏈接列表。看源代碼:

/** *雙向鏈表的表頭元素。 */ privatetransientEntryheader;   /** *LinkedHashMap的Entry元素。 *繼承HashMap的Entry元素,又保存了其上一個元素before和下一個元素after的引用。 */ privatestaticclassEntryextendsHashMap.Entry{ Entrybefore,after; …… }

2) 初始化:

通過源代碼可以看出,在LinkedHashMap的構造方法中,實際調用了父類HashMap的相關構造方法來構造一個底層存放的table數組。如:

publicLinkedHashMap(intinitialCapacity,floatloadFactor){ super(initialCapacity,loadFactor); accessOrder=false; }

HashMap中的相關構造方法:

publicHashMap(intinitialCapacity,floatloadFactor){ if(initialCapacity<0) thrownewIllegalArgumentException("Illegalinitialcapacity:"+ initialCapacity); if(initialCapacity>MAXIMUM_CAPACITY) initialCapacity=MAXIMUM_CAPACITY; if(loadFactor<=0||Float.isNaN(loadFactor)) thrownewIllegalArgumentException("Illegalloadfactor:"+ loadFactor);   //Findapowerof2>=initialCapacity intcapacity=1; while(capacity我們已經知道LinkedHashMap的Entry元素繼承HashMap的Entry,提供了雙向鏈表的功能。在上述HashMap的構造器
中,最後會調用init()方法,進行相關的初始化,這個方法在HashMap的實現中並無意義,只是提供給子類實現相關的初始化調用。
LinkedHashMap重寫了init()方法,在調用父類的構造方法完成構造後,進一步實現了對其元素Entry的初始化操作。
voidinit(){ header=newEntry(-1,null,null,null); header.before=header.after=header; }

3) 存儲:

LinkedHashMap並未重寫父類HashMap的put方法,而是重寫了父類HashMap的put方法調用的子方法void addEntry(int hash, K key, V value, int bucketIndex) 和void createEntry(int hash, K key, V value, int bucketIndex),提供了自己特有的雙向鏈接列表的實現。

voidaddEntry(inthash,Kkey,Vvalue,intbucketIndex){ //調用create方法,將新元素以雙向鏈表的的形式加入到映射中。 createEntry(hash,key,value,bucketIndex);   //刪除最近最少使用元素的策略定義 Entryeldest=header.after; if(removeEldestEntry(eldest)){ removeEntryForKey(eldest.key); }else{ if(size>=threshold) resize(2*table.length); } } voidcreateEntry(inthash,Kkey,Vvalue,intbucketIndex){ HashMap.Entryold=table[bucketIndex]; Entrye=newEntry(hash,key,value,old); table[bucketIndex]=e; //調用元素的addBrefore方法,將元素加入到哈希、雙向鏈接列表。 e.addBefore(header); size++; } privatevoidaddBefore(EntryexistingEntry){ after=existingEntry; before=existingEntry.before; before.after=this; after.before=this; }

4) 讀取:

LinkedHashMap重寫了父類HashMap的get方法,實際在調用父類getEntry()方法取得查找的元素後,再判斷當排序模式accessOrder為true時,記錄訪問順序,將最新訪問的元素添加到雙向鏈表的表頭,並從原來的位置刪除。由於的鏈表的增加、刪除操作是常量級的,故並不會帶來性能的損失。

publicVget(Objectkey){ //調用父類HashMap的getEntry()方法,取得要查找的元素。 Entrye=(Entry)getEntry(key); if(e==null) returnnull; //記錄訪問順序。 e.recordAccess(this); returne.value; } Java代碼收藏代碼 voidrecordAccess(HashMapm){ LinkedHashMaplm=(LinkedHashMap)m; //如果定義了LinkedHashMap的迭代順序為訪問順序, //則刪除以前位置上的元素,並將最新訪問的元素添加到鏈表表頭。 if(lm.accessOrder){ lm.modCount++; remove(); addBefore(lm.header); } }

5) 排序模式:

LinkedHashMap定義了排序模式accessOrder,該屬性為boolean型變量,對於訪問順序,為true;對於插入順序,則為false。

privatefinalbooleanaccessOrder;

一般情況下,不必指定排序模式,其迭代順序即為默認為插入順序。看LinkedHashMap的構造方法,如:

publicLinkedHashMap(intinitialCapacity,floatloadFactor){ super(initialCapacity,loadFactor); accessOrder=false; }

這些構造方法都會默認指定排序模式為插入順序。如果你想構造一個LinkedHashMap,並打算按從近期訪問最少到近期訪問最多的順序(即訪問順序)來保存元素,那麼請使用下面的構造方法構造LinkedHashMap:

publicLinkedHashMap(intinitialCapacity, floatloadFactor, booleanaccessOrder){ super(initialCapacity,loadFactor); this.accessOrder=accessOrder; }

該哈希映射的迭代順序就是最後訪問其條目的順序,這種映射很適合構建LRU緩存。LinkedHashMap提供了removeEldestEntry(Map.Entry eldest)方法,在將新條目插入到映射後,put和 putAll將調用此方法。該方法可以提供在每次添加新條目時移除最舊條目的實現程序,默認返回false,這樣,此映射的行為將類似於正常映射,即永遠不能移除最舊的元素。

protectedbooleanremoveEldestEntry(Map.Entryeldest){ returnfalse; }

此方法通常不以任何方式修改映射,相反允許映射在其返回值的指引下進行自我修改。如果用此映射構建LRU緩存,則非常方便,它允許映射通過刪除舊條目來減少內存損耗。
例如:重寫此方法,維持此映射只保存100個條目的穩定狀態,在每次添加新條目時刪除最舊的條目。

privatestaticfinalintMAX_ENTRIES=100; protectedbooleanremoveEldestEntry(Map.Entryeldest){ returnsize()>MAX_ENTRIES; }

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved