????????
1. LinkedHashMap概述：
LinkedHashMap是HashMap的一個子類，它保留插入的順序，如果需要輸出的順序和輸入時的相同，那么就選用LinkedHashMap。
?? LinkedHashMap是Map接口的哈希表和鏈接列表實現，具有可預知的迭代順序。此實現提供所有可選的映射操作，并允許使用null值和null鍵。此類不保證映射的順序，特別是它不保證該順序恒久不變。
?? LinkedHashMap實現與HashMap的不同之處在于，后者維護著一個運行于所有條目的雙重鏈接列表。此鏈接列表定義了迭代順序，該迭代順序可以是插入順序或者是訪問順序。
?? 注意，此實現不是同步的。如果多個線程同時訪問鏈接的哈希映射，而其中至少一個線程從結構上修改了該映射，則它必須保持外部同步。
?
根據鏈表中元素的順序可以分為：按插入順序的鏈表，和按訪問順序(調用get方法)的鏈表。??
默認是按插入順序排序，如果指定按訪問順序排序，那么調用get方法后，會將這次訪問的元素移至鏈表尾部，不斷訪問可以形成按訪問順序排序的鏈表。 ?可以重寫removeEldestEntry方法返回true值指定插入元素時移除最老的元素。?
?
2. LinkedHashMap的實現：
?? 對于LinkedHashMap而言，它繼承與HashMap、底層使用哈希表與雙向鏈表來保存所有元素。其基本操作與父類HashMap相似，它通過重寫父類相關的方法，來實現自己的鏈接列表特性。下面我們來分析LinkedHashMap的源代碼：
類結構：
public?class?LinkedHashMap<K,?V>?extends?HashMap<K,?V>?implements?Map<K,?V>????
?
?1) 成員變量：
?? LinkedHashMap采用的hash算法和HashMap相同，但是它重新定義了數組中保存的元素Entry，該Entry除了保存當前對象的引用外，還保存了其上一個元素before和下一個元素after的引用，從而在哈希表的基礎上又構成了雙向鏈接列表。看源代碼：
?
//true表示按照訪問順序迭代，false時表示按照插入順序??
?private?final?boolean?accessOrder;??
/**?
?*?雙向鏈表的表頭元素。?
?*/??
private?transient?Entry<K,V>?header;??
??
/**?
?*?LinkedHashMap的Entry元素。?
?*?繼承HashMap的Entry元素，又保存了其上一個元素before和下一個元素after的引用。?
?*/??
private?static?class?Entry<K,V>?extends?HashMap.Entry<K,V>?{??
????Entry<K,V>?before,?after;??
????……??
}??
HashMap.Entry:
static?class?Entry<K,V>?implements?Map.Entry<K,V>?{??
????????final?K?key;??
????????V?value;??
????????Entry<K,V>?next;??
????????final?int?hash;??
??
????????Entry(int?h,?K?k,?V?v,?Entry<K,V>?n)?{??
????????????value?=?v;??
????????????next?=?n;??
????????????key?=?k;??
????????????hash?=?h;??
????????}??
}??
??
????2) 初始化：
?? 通過源代碼可以看出，在LinkedHashMap的構造方法中，實際調用了父類HashMap的相關構造方法來構造一個底層存放的table數組。如：
public?LinkedHashMap(int?initialCapacity,?float?loadFactor)?{??
????super(initialCapacity,?loadFactor);??
????accessOrder?=?false;??
}??
??? HashMap中的相關構造方法：
public?HashMap(int?initialCapacity,?float?loadFactor)?{??
????if?(initialCapacity?<?0)??
????????throw?new?IllegalArgumentException("Illegal?initial?capacity:?"?+??
???????????????????????????????????????????initialCapacity);??
????if?(initialCapacity?>?MAXIMUM_CAPACITY)??
????????initialCapacity?=?MAXIMUM_CAPACITY;??
????if?(loadFactor?<=?0?||?Float.isNaN(loadFactor))??
????????throw?new?IllegalArgumentException("Illegal?load?factor:?"?+??
???????????????????????????????????????????loadFactor);??
??
????//?Find?a?power?of?2?>=?initialCapacity??
????int?capacity?=?1;??
????while?(capacity?<?initialCapacity)??
????????capacity?<<=?1;??
??
????this.loadFactor?=?loadFactor;??
????threshold?=?(int)(capacity?*?loadFactor);??
????table?=?new?Entry[capacity];??
????init();??
}??
??? 我們已經知道LinkedHashMap的Entry元素繼承HashMap的Entry，提供了雙向鏈表的功能。在上述HashMap的構造器中，最后會調用init()方法，進行相關的初始化，這個方法在HashMap的實現中并無意義，只是提供給子類實現相關的初始化調用。
?? LinkedHashMap重寫了init()方法，在調用父類的構造方法完成構造后，進一步實現了對其元素Entry的初始化操作。
void?init()?{??
????header?=?new?Entry<K,V>(-1,?null,?null,?null);??
????header.before?=?header.after?=?header;??
}??
????3) 存儲：
???LinkedHashMap并未重寫父類HashMap的put方法，而是重寫了父類HashMap的put方法調用的子方法void recordAccess(HashMap m)?? ，void addEntry(int hash, K key, V value, int bucketIndex) 和void createEntry(int hash, K key, V value, int bucketIndex)，提供了自己特有的雙向鏈接列表的實現。
HashMap.put:
?
public?V?put(K?key,?V?value)?{??
????????if?(key?==?null)??
????????????return?putForNullKey(value);??
????????int?hash?=?hash(key.hashCode());??
????????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;??
????}??
?重寫方法：
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)?{??
????//?調用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;??
????//?調用元素的addBrefore方法，將元素加入到哈希、雙向鏈接列表。??
????e.addBefore(header);??
????size++;??
}??
private?void?addBefore(Entry<K,V>?existingEntry)?{??
????after??=?existingEntry;??
????before?=?existingEntry.before;??
????before.after?=?this;??
????after.before?=?this;??
}??
???
4) 讀取：
?? LinkedHashMap重寫了父類HashMap的get方法，實際在調用父類getEntry()方法取得查找的元素后，再判斷當排序模式accessOrder為true時，記錄訪問順序，將最新訪問的元素添加到雙向鏈表的表頭，并從原來的位置刪除。由于的鏈表的增加、刪除操作是常量級的，故并不會帶來性能的損失。
HashMap.containsValue:
public?boolean?containsValue(Object?value)?{??
????if?(value?==?null)??
????????????return?containsNullValue();??
??
????Entry[]?tab?=?table;??
????????for?(int?i?=?0;?i?<?tab.length?;?i++)??
????????????for?(Entry?e?=?tab[i]?;?e?!=?null?;?e?=?e.next)??
????????????????if?(value.equals(e.value))??
????????????????????return?true;??
????return?false;??
????}??
?
?/*查找Map中是否包含給定的value，還是考慮到，LinkedHashMap擁有的雙鏈表，在這里Override是為了提高迭代的效率。?
?*/??
public?boolean?containsValue(Object?value)?{??
????????//?Overridden?to?take?advantage?of?faster?iterator??
????????if?(value==null)?{??
????????????for?(Entry?e?=?header.after;?e?!=?header;?e?=?e.after)??
????????????????if?(e.value==null)??
????????????????????return?true;??
????????}?else?{??
????????????for?(Entry?e?=?header.after;?e?!=?header;?e?=?e.after)??
????????????????if?(value.equals(e.value))??
????????????????????return?true;??
????????}??
????????return?false;??
????}??
?
?
/*該transfer()是HashMap中的實現：遍歷整個表的各個桶位，然后對桶進行遍歷得到每一個Entry，重新hash到newTable中，?
?//放在這里是為了和下面LinkedHashMap重寫該法的比較，?
?void?transfer(Entry[]?newTable)?{?
????????Entry[]?src?=?table;?
????????int?newCapacity?=?newTable.length;?
????????for?(int?j?=?0;?j?<?src.length;?j++)?{?
????????????Entry<K,V>?e?=?src[j];?
????????????if?(e?!=?null)?{?
????????????????src[j]?=?null;?
????????????????do?{?
????????????????????Entry<K,V>?next?=?e.next;?
????????????????????int?i?=?indexFor(e.hash,?newCapacity);?
????????????????????e.next?=?newTable[i];?
????????????????????newTable[i]?=?e;?
????????????????????e?=?next;?
????????????????}?while?(e?!=?null);?
????????????}?
????????}?
????}?
?*/??
??
?/**?
?*transfer()方法是其父類HashMap調用resize()的時候調用的方法，它的作用是表擴容后，把舊表中的key重新hash到新的表中。?
?*這里從寫了父類HashMap中的該方法，是因為考慮到，LinkedHashMap擁有的雙鏈表，在這里Override是為了提高迭代的效率。?
?*/??
?void?transfer(HashMap.Entry[]?newTable)?{??
???int?newCapacity?=?newTable.length;??
???for?(Entry<K,?V>?e?=?header.after;?e?!=?header;?e?=?e.after)?{??
?????int?index?=?indexFor(e.hash,?newCapacity);??
?????e.next?=?newTable[index];??
?????newTable[index]?=?e;??
???}??
?}??
?
public?V?get(Object?key)?{??
????//?調用父類HashMap的getEntry()方法，取得要查找的元素。??
????Entry<K,V>?e?=?(Entry<K,V>)getEntry(key);??
????if?(e?==?null)??
????????return?null;??
????//?記錄訪問順序。??
????e.recordAccess(this);??
????return?e.value;??
}??
void?recordAccess(HashMap<K,V>?m)?{??
????LinkedHashMap<K,V>?lm?=?(LinkedHashMap<K,V>)m;??
????//?如果定義了LinkedHashMap的迭代順序為訪問順序，??
????//?則刪除以前位置上的元素，并將最新訪問的元素添加到鏈表表頭。??
????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鏈表，設置header為初始狀態*/??
public?void?clear()?{??
?super.clear();??
?header.before?=?header.after?=?header;??
}??
?
?
????5) 排序模式：
?? LinkedHashMap定義了排序模式accessOrder，該屬性為boolean型變量，對于訪問順序，為true；對于插入順序，則為false。
private?final?boolean?accessOrder;??
?一般情況下，不必指定排序模式，其迭代順序即為默認為插入順序。看LinkedHashMap的構造方法，如：
public?LinkedHashMap(int?initialCapacity,?float?loadFactor)?{??
????super(initialCapacity,?loadFactor);??
????accessOrder?=?false;??
}??
??? 這些構造方法都會默認指定排序模式為插入順序。如果你想構造一個LinkedHashMap，并打算按從近期訪問最少到近期訪問最多的順序（即訪問順序）來保存元素，那么請使用下面的構造方法構造LinkedHashMap：
public?LinkedHashMap(int?initialCapacity,??
?????????float?loadFactor,??
?????????????????????boolean?accessOrder)?{??
????super(initialCapacity,?loadFactor);??
????this.accessOrder?=?accessOrder;??
}??
??? 該哈希映射的迭代順序就是最后訪問其條目的順序，這種映射很適合構建LRU緩存。LinkedHashMap提供了removeEldestEntry(Map.Entry<K,V> eldest)方法。該方法可以提供在每次添加新條目時移除最舊條目的實現程序，默認返回false，這樣，此映射的行為將類似于正常映射，即永遠不能移除最舊的元素。
?
當有新元素加入Map的時候會調用Entry的addEntry方法，會調用removeEldestEntry方法，這里就是實現LRU元素過期機制的地方，默認的情況下removeEldestEntry方法只返回false表示元素永遠不過期。
??/**?
????*?This?override?alters?behavior?of?superclass?put?method.?It?causes?newly?
????*?allocated?entry?to?get?inserted?at?the?end?of?the?linked?list?and?
????*?removes?the?eldest?entry?if?appropriate.?
????*/??
???void?addEntry(int?hash,?K?key,?V?value,?int?bucketIndex)?{??
???????createEntry(hash,?key,?value,?bucketIndex);??
??
???????//?Remove?eldest?entry?if?instructed,?else?grow?capacity?if?appropriate??
???????Entry<K,V>?eldest?=?header.after;??
???????if?(removeEldestEntry(eldest))?{??
???????????removeEntryForKey(eldest.key);??
???????}?else?{??
???????????if?(size?>=?threshold)???
???????????????resize(2?*?table.length);??
???????}??
???}??
??
???/**?
????*?This?override?differs?from?addEntry?in?that?it?doesn't?resize?the?
????*?table?or?remove?the?eldest?entry.?
????*/??
???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;??
???????e.addBefore(header);??
???????size++;??
???}??
??
???protected?boolean?removeEldestEntry(Map.Entry<K,V>?eldest)?{??
???????return?false;??
???}??
此方法通常不以任何方式修改映射，相反允許映射在其返回值的指引下進行自我修改。如果用此映射構建LRU緩存，則非常方便，它允許映射通過刪除舊條目來減少內存損耗。
?? 例如：重寫此方法，維持此映射只保存100個條目的穩定狀態，在每次添加新條目時刪除最舊的條目。
private?static?final?int?MAX_ENTRIES?=?100;??
protected?boolean?removeEldestEntry(Map.Entry?eldest)?{??
????return?size()?>?MAX_ENTRIES;??
}??
?
其實LinkedHashMap幾乎和HashMap一樣，不同的是它定義了一個Entry<K,V> header，這個header不是放在Table里，它是額外獨立出來的。LinkedHashMap通過繼承hashMap中的Entry<K,V>,并添加兩個屬性Entry<K,V> ?before,after,和header結合起來組成一個雙向鏈表，來實現按插入順序或訪問順序排序。
????
轉載于:https://blog.51cto.com/12879490/1921848
![全新升級的AOP框架Dora.Interception[2]: 基于約定的攔截器定義方式](http://pic.xiahunao.cn/全新升級的AOP框架Dora.Interception[2]: 基于約定的攔截器定義方式)
![[cf797c]Minimal string（貪心+模擬）](http://pic.xiahunao.cn/[cf797c]Minimal string（貪心+模擬）)
