HashMap 是無(wú)序的,HashMap 在 put 的時(shí)候是根據(jù) key 的 hashcode 進(jìn)行 hash 然后放入對(duì)應(yīng)的地方。所以在按照一定順序 put 進(jìn) HashMap 中,然后遍歷出 HashMap 的順序跟 put 的順序不同(除非在 put 的時(shí)候 key 已經(jīng)按照 hashcode 排序號(hào)了,這種幾率非常?。?/p>
JAVA 在 JDK1.4 以后提供了 LinkedHashMap 來(lái)幫助我們實(shí)現(xiàn)了有序的 HashMap!
LinkedHashMap 是 HashMap 的一個(gè)子類(lèi),它保留插入的順序,如果需要輸出的順序和輸入時(shí)的相同,那么就選用 LinkedHashMap。
LinkedHashMap 是 Map 接口的哈希表和鏈接列表實(shí)現(xiàn),具有可預(yù)知的迭代順序。此實(shí)現(xiàn)提供所有可選的映射操作,并允許使用 null 值和 null 鍵。此類(lèi)不保證映射的順序,特別是它不保證該順序恒久不變。
LinkedHashMap 實(shí)現(xiàn)與 HashMap 的不同之處在于,LinkedHashMap 維護(hù)著一個(gè)運(yùn)行于所有條目的雙重鏈接列表。此鏈接列表定義了迭代順序,該迭代順序可以是插入順序或者是訪問(wèn)順序。
注意,此實(shí)現(xiàn)不是同步的。如果多個(gè)線程同時(shí)訪問(wèn)鏈接的哈希映射,而其中至少一個(gè)線程從結(jié)構(gòu)上修改了該映射,則它必須保持外部同步。
根據(jù)鏈表中元素的順序可以分為:按插入順序的鏈表,和按訪問(wèn)順序(調(diào)用 get 方法)的鏈表。默認(rèn)是按插入順序排序,如果指定按訪問(wèn)順序排序,那么調(diào)用get方法后,會(huì)將這次訪問(wèn)的元素移至鏈表尾部,不斷訪問(wèn)可以形成按訪問(wèn)順序排序的鏈表。
我在最開(kāi)始學(xué)習(xí) LinkedHashMap 的時(shí)候,看到訪問(wèn)順序、插入順序等等,有點(diǎn)暈了,隨著后續(xù)的學(xué)習(xí)才慢慢懂得其中原理,所以我會(huì)先在進(jìn)行做幾個(gè) demo 來(lái)演示一下 LinkedHashMap 的使用。看懂了其效果,然后再來(lái)研究其原理。
看下面這個(gè)代碼:
public static void main(String[] args) {
Map<String, String> map = new HashMap<String, String>();
map.put("apple", "蘋(píng)果");
map.put("watermelon", "西瓜");
map.put("banana", "香蕉");
map.put("peach", "桃子");
Iterator iter = map.entrySet().iterator();
while (iter.hasNext()) {
Map.Entry entry = (Map.Entry) iter.next();
System.out.println(entry.getKey() + "=" + entry.getValue());
}
}
一個(gè)比較簡(jiǎn)單的測(cè)試 HashMap 的代碼,通過(guò)控制臺(tái)的輸出,我們可以看到 HashMap 是沒(méi)有順序的。
banana=香蕉
apple=蘋(píng)果
peach=桃子
watermelon=西瓜
我們現(xiàn)在將 map 的實(shí)現(xiàn)換成 LinkedHashMap,其他代碼不變:Map<String, String> map = new LinkedHashMap<String, String>();
看一下控制臺(tái)的輸出:
apple=蘋(píng)果
watermelon=西瓜
banana=香蕉
peach=桃子
我們可以看到,其輸出順序是完成按照插入順序的!也就是我們上面所說(shuō)的保留了插入的順序。我們不是在上面還提到過(guò)其可以按照訪問(wèn)順序進(jìn)行排序么?好的,我們還是通過(guò)一個(gè)例子來(lái)驗(yàn)證一下:
public static void main(String[] args) {
Map<String, String> map = new LinkedHashMap<String, String>(16,0.75f,true);
map.put("apple", "蘋(píng)果");
map.put("watermelon", "西瓜");
map.put("banana", "香蕉");
map.put("peach", "桃子");
map.get("banana");
map.get("apple");
Iterator iter = map.entrySet().iterator();
while (iter.hasNext()) {
Map.Entry entry = (Map.Entry) iter.next();
System.out.println(entry.getKey() + "=" + entry.getValue());
}
}
代碼與之前的都差不多,但我們多了兩行代碼,并且初始化 LinkedHashMap 的時(shí)候,用的構(gòu)造函數(shù)也不相同,看一下控制臺(tái)的輸出結(jié)果:
watermelon=西瓜
peach=桃子
banana=香蕉
apple=蘋(píng)果
這也就是我們之前提到過(guò)的,LinkedHashMap 可以選擇按照訪問(wèn)順序進(jìn)行排序。
對(duì)于 LinkedHashMap 而言,它繼承與 HashMap(public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>
)、底層使用哈希表與雙向鏈表來(lái)保存所有元素。其基本操作與父類(lèi) HashMap 相似,它通過(guò)重寫(xiě)父類(lèi)相關(guān)的方法,來(lái)實(shí)現(xiàn)自己的鏈接列表特性。下面我們來(lái)分析 LinkedHashMap 的源代碼:
LinkedHashMap 采用的 hash 算法和 HashMap 相同,但是它重新定義了數(shù)組中保存的元素 Entry,該 Entry 除了保存當(dāng)前對(duì)象的引用外,還保存了其上一個(gè)元素 before 和下一個(gè)元素 after 的引用,從而在哈希表的基礎(chǔ)上又構(gòu)成了雙向鏈接列表??丛创a:
/**
* The iteration ordering method for this linked hash map: <tt>true</tt>
* for access-order, <tt>false</tt> for insertion-order.
* 如果為true,則按照訪問(wèn)順序;如果為false,則按照插入順序。
*/
private final boolean accessOrder;
/**
* 雙向鏈表的表頭元素。
*/
private transient Entry<K,V> header;
/**
* LinkedHashMap的Entry元素。
* 繼承HashMap的Entry元素,又保存了其上一個(gè)元素before和下一個(gè)元素after的引用。
*/
private static class Entry<K,V> extends HashMap.Entry<K,V> {
Entry<K,V> before, after;
……
}
LinkedHashMap 中的 Entry 集成與 HashMap 的 Entry,但是其增加了 before 和 after 的引用,指的是上一個(gè)元素和下一個(gè)元素的引用。
通過(guò)源代碼可以看出,在 LinkedHashMap 的構(gòu)造方法中,實(shí)際調(diào)用了父類(lèi) HashMap 的相關(guān)構(gòu)造方法來(lái)構(gòu)造一個(gè)底層存放的 table 數(shù)組,但額外可以增加 accessOrder 這個(gè)參數(shù),如果不設(shè)置,默認(rèn)為 false,代表按照插入順序進(jìn)行迭代;當(dāng)然可以顯式設(shè)置為 true,代表以訪問(wèn)順序進(jìn)行迭代。如:
public LinkedHashMap(int initialCapacity, float loadFactor,boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
我們已經(jīng)知道 LinkedHashMap 的 Entry 元素繼承 HashMap 的 Entry,提供了雙向鏈表的功能。在上述 HashMap 的構(gòu)造器中,最后會(huì)調(diào)用 init() 方法,進(jìn)行相關(guān)的初始化,這個(gè)方法在 HashMap 的實(shí)現(xiàn)中并無(wú)意義,只是提供給子類(lèi)實(shí)現(xiàn)相關(guān)的初始化調(diào)用。
但在 LinkedHashMap 重寫(xiě)了 init() 方法,在調(diào)用父類(lèi)的構(gòu)造方法完成構(gòu)造后,進(jìn)一步實(shí)現(xiàn)了對(duì)其元素 Entry 的初始化操作。
/**
* Called by superclass constructors and pseudoconstructors (clone,
* readObject) before any entries are inserted into the map. Initializes
* the chain.
*/
@Override
void init() {
header = new Entry<>(-1, null, null, null);
header.before = header.after = header;
}
LinkedHashMap 并未重寫(xiě)父類(lèi) HashMap 的 put 方法,而是重寫(xiě)了父類(lèi) HashMap 的 put 方法調(diào)用的子方法void recordAccess(HashMap m) ,void addEntry(int hash, K key, V value, int bucketIndex) 和void createEntry(int hash, K key, V value, int bucketIndex),提供了自己特有的雙向鏈接列表的實(shí)現(xiàn)。我們?cè)谥暗奈恼轮幸呀?jīng)講解了HashMap的put方法,我們?cè)谶@里重新貼一下 HashMap 的 put 方法的源代碼:
HashMap.put:
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key);
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
重寫(xiě)方法:
void recordAccess(HashMap<K,V> m) {
LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
if (lm.accessOrder) {
lm.modCount++;
remove();
addBefore(lm.header);
}
}
void addEntry(int hash, K key, V value, int bucketIndex) {
// 調(diào)用create方法,將新元素以雙向鏈表的的形式加入到映射中。
createEntry(hash, key, value, bucketIndex);
// 刪除最近最少使用元素的策略定義
Entry<K,V> eldest = header.after;
if (removeEldestEntry(eldest)) {
removeEntryForKey(eldest.key);
} else {
if (size >= threshold)
resize(2 * table.length);
}
}
void createEntry(int hash, K key, V value, int bucketIndex) {
HashMap.Entry<K,V> old = table[bucketIndex];
Entry<K,V> e = new Entry<K,V>(hash, key, value, old);
table[bucketIndex] = e;
// 調(diào)用元素的addBrefore方法,將元素加入到哈希、雙向鏈接列表。
e.addBefore(header);
size++;
}
private void addBefore(Entry<K,V> existingEntry) {
after = existingEntry;
before = existingEntry.before;
before.after = this;
after.before = this;
}
LinkedHashMap 重寫(xiě)了父類(lèi) HashMap 的 get 方法,實(shí)際在調(diào)用父類(lèi) getEntry() 方法取得查找的元素后,再判斷當(dāng)排序模式 accessOrder 為 true 時(shí),記錄訪問(wèn)順序,將最新訪問(wèn)的元素添加到雙向鏈表的表頭,并從原來(lái)的位置刪除。由于的鏈表的增加、刪除操作是常量級(jí)的,故并不會(huì)帶來(lái)性能的損失。
public V get(Object key) {
// 調(diào)用父類(lèi)HashMap的getEntry()方法,取得要查找的元素。
Entry<K,V> e = (Entry<K,V>)getEntry(key);
if (e == null)
return null;
// 記錄訪問(wèn)順序。
e.recordAccess(this);
return e.value;
}
void recordAccess(HashMap<K,V> m) {
LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
// 如果定義了LinkedHashMap的迭代順序?yàn)樵L問(wèn)順序,
// 則刪除以前位置上的元素,并將最新訪問(wèn)的元素添加到鏈表表頭。
if (lm.accessOrder) {
lm.modCount++;
remove();
addBefore(lm.header);
}
}
/**
* Removes this entry from the linked list.
*/
private void remove() {
before.after = after;
after.before = before;
}
/**clear鏈表,設(shè)置header為初始狀態(tài)*/
public void clear() {
super.clear();
header.before = header.after = header;
}
LinkedHashMap 定義了排序模式 accessOrder,該屬性為 boolean 型變量,對(duì)于訪問(wèn)順序,為 true;對(duì)于插入順序,則為 false。一般情況下,不必指定排序模式,其迭代順序即為默認(rèn)為插入順序。
這些構(gòu)造方法都會(huì)默認(rèn)指定排序模式為插入順序。如果你想構(gòu)造一個(gè) LinkedHashMap,并打算按從近期訪問(wèn)最少到近期訪問(wèn)最多的順序(即訪問(wèn)順序)來(lái)保存元素,那么請(qǐng)使用下面的構(gòu)造方法構(gòu)造 LinkedHashMap:public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)
該哈希映射的迭代順序就是最后訪問(wèn)其條目的順序,這種映射很適合構(gòu)建 LRU 緩存。LinkedHashMap 提供了 removeEldestEntry(Map.Entry<K,V> eldest) 方法。該方法可以提供在每次添加新條目時(shí)移除最舊條目的實(shí)現(xiàn)程序,默認(rèn)返回 false,這樣,此映射的行為將類(lèi)似于正常映射,即永遠(yuǎn)不能移除最舊的元素。
我們會(huì)在后面的文章中詳細(xì)介紹關(guān)于如何用 LinkedHashMap 構(gòu)建 LRU 緩存。
其實(shí) LinkedHashMap 幾乎和 HashMap 一樣:從技術(shù)上來(lái)說(shuō),不同的是它定義了一個(gè) Entry<K,V> header,這個(gè) header 不是放在 Table 里,它是額外獨(dú)立出來(lái)的。LinkedHashMap 通過(guò)繼承 hashMap 中的 Entry<K,V>,并添加兩個(gè)屬性 Entry<K,V> before,after,和 header 結(jié)合起來(lái)組成一個(gè)雙向鏈表,來(lái)實(shí)現(xiàn)按插入順序或訪問(wèn)順序排序。
在寫(xiě)關(guān)于 LinkedHashMap 的過(guò)程中,記起來(lái)之前面試的過(guò)程中遇到的一個(gè)問(wèn)題,也是問(wèn)我 Map 的哪種實(shí)現(xiàn)可以做到按照插入順序進(jìn)行迭代?當(dāng)時(shí)腦子是突然短路的,但現(xiàn)在想想,也只能怪自己對(duì)這個(gè)知識(shí)點(diǎn)還是掌握的不夠扎實(shí),所以又從頭認(rèn)真的把代碼看了一遍。
不過(guò),我的建議是,大家首先首先需要記住的是:LinkedHashMap 能夠做到按照插入順序或者訪問(wèn)順序進(jìn)行迭代,這樣在我們以后的開(kāi)發(fā)中遇到相似的問(wèn)題,才能想到用 LinkedHashMap 來(lái)解決,否則就算對(duì)其內(nèi)部結(jié)構(gòu)非常了解,不去使用也是沒(méi)有什么用的。
我們學(xué)習(xí)的目的是為了更好的應(yīng)用。