LinkedHashMap繼承自HashMap，HashMap是無(wú)序的鲸拥，而LinkedHashMap則利用雙向非循環(huán)結(jié)構(gòu)保持了插入節(jié)點(diǎn)的順序(有兩種順序拐格，插入順序和訪問(wèn)順序，后面解釋)刑赶。
建議先搞明白HashMap的原理再看LinkedHashMap捏浊，Java集合源碼分析-HashMap。
LinkedHashMap類圖
和HashMap不同的地方在于它通過(guò)改造newNode方法和添加下面三個(gè)方法：
void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node<K,V> p) { }
LinkedHashMap成員變量和構(gòu)造器
LinkedHashMap繼承了HashMap的所有的非private的變量撞叨，而且還多出來(lái)三個(gè)變量：
transient LinkedHashMap.Entry<K,V> head;
transient LinkedHashMap.Entry<K,V> tail;
final boolean accessOrder;
head和tail很簡(jiǎn)單金踪，分別是頭結(jié)點(diǎn)和尾節(jié)點(diǎn)，不解釋牵敷，但是accessOrder就需要解釋下了胡岔。accessOrder，看它的字面意思是訪問(wèn)順序枷餐，那么就跟LinkedHashMap的節(jié)點(diǎn)順序有關(guān)了靶瘸，默認(rèn)accessOrder是false，表示LinkedHashMap的節(jié)點(diǎn)順序和插入順序是一樣的毛肋，如果accessOrder為true怨咪，那么在get方法中會(huì)調(diào)用afterNodeAccess方法，看下這個(gè)方法的源碼：
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;
if (accessOrder && (last = tail) != e) {
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
p.after = null;
if (b == null)
head = a;
else
b.after = a;
if (a != null)
a.before = b;
else
last = b;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
tail = p;
++modCount;
}
}
這個(gè)方法做的操作是將get訪問(wèn)的節(jié)點(diǎn)掐出來(lái)并挪到尾節(jié)點(diǎn)润匙，這就是所謂的訪問(wèn)順序诗眨，想想跟插入順序的區(qū)別。java.util包下的集合的迭代器遍歷都是fail-fast的趁桃，遍歷時(shí)候更改集合的結(jié)構(gòu)會(huì)拋出ConcurrentModificationException辽话，一般來(lái)說(shuō)get查詢不會(huì)更改集合的結(jié)構(gòu)肄鸽，但是accessOrder為true的LinkedHashMap的get查詢會(huì)更改集合的結(jié)構(gòu)卫病，可以看到上面代碼的最后一行對(duì)modCount進(jìn)行了加一操作油啤。所以，如果LinkedHashMap的accessOrder為true蟀苛，那么在迭代器遍歷的時(shí)候千萬(wàn)別使用get方法益咬。
舉個(gè)例子：
Map<String, String> linkedHashMap = new LinkedHashMap<>(16, 0.75f, true);
linkedHashMap.put("1", "callme1");
linkedHashMap.put("2", "callme2");
linkedHashMap.put("3", "callme3");
linkedHashMap.put("4", "callme4");
System.out.println("默認(rèn)插入順序：");
Set<Map.Entry<String, String>> set = linkedHashMap.entrySet();
Iterator<Map.Entry<String, String>> iterator = set.iterator();
while(iterator.hasNext()) {
Map.Entry entry = iterator.next();
String key = (String) entry.getKey();
String value = (String) entry.getValue();
System.out.println("key:" + key + ",value:" + value);
}
System.out.println("通過(guò)get方法，導(dǎo)致key為1對(duì)應(yīng)的Entry挪到尾部");
linkedHashMap.get("2");
Set<Map.Entry<String, String>> set2 = linkedHashMap.entrySet();
Iterator<Map.Entry<String, String>> iterator2 = set2.iterator();
while(iterator2.hasNext()) {
Map.Entry entry = iterator2.next();
String key = (String) entry.getKey();
String value = (String) entry.getValue();
System.out.println("key:" + key + ",value:" + value);
}
LinkedHashMap比HashMap的構(gòu)造器多了一個(gè)：
public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
可以看出這個(gè)構(gòu)造器只是來(lái)處理accessOrder 而已帜平。
LinkedHashMap節(jié)點(diǎn)類
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
可以看到LinkedHashMap節(jié)點(diǎn)類繼承自HashMap節(jié)點(diǎn)類幽告，來(lái)復(fù)習(xí)下HashMap的節(jié)點(diǎn)類：
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
}
LinkedHashMap節(jié)點(diǎn)類多了before和after兩個(gè)屬性，注意after和next兩者區(qū)別裆甩，不需要解釋了冗锁，通過(guò)before和after保持LinkedHashMap的有序性。
put
為了保持有序性嗤栓，LinkedHashMap的put操作和HashMap的put有三點(diǎn)不同：
第一點(diǎn)不同是生成新節(jié)點(diǎn)的方法newNode不同(調(diào)用這個(gè)方法表示表中不存在重復(fù)key節(jié)點(diǎn))冻河，LinkedHashMap多調(diào)用了一個(gè)方法linkNodeLast：
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
LinkedHashMap.Entry<K,V> last = tail;
tail = p;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
}
很簡(jiǎn)單，只是將新節(jié)點(diǎn)插入到順序表的尾部茉帅。
第二點(diǎn)不同是叨叙，如果表中存在和要插入節(jié)點(diǎn)的key相同的節(jié)點(diǎn)，覆蓋之后會(huì)調(diào)用afterNodeAccess方法堪澎，前面介紹過(guò)擂错，很簡(jiǎn)單。
第三點(diǎn)不同是LinkedHashMap在插入的最后一步調(diào)用了afterNodeInsertion(boolean evict)方法：
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry<K,V> first;
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
removeNode(hash(key), key, null, false, true);
}
}
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false;
}
從代碼里可以看出樱蛤，afterNodeInsertion試圖將最老的節(jié)點(diǎn)即頭結(jié)點(diǎn)刪除钮呀，但是removeEldestEntry永遠(yuǎn)返回false，所以afterNodeInsertion什么都不會(huì)干的昨凡。afterNodeInsertion有什么卵用嗎爽醋？這個(gè)removeEldestEntry方法應(yīng)該需要用戶重寫的，下面的測(cè)試代碼：
final int MAX_ENTRIES = 8;
LinkedHashMap lhm = new LinkedHashMap(MAX_ENTRIES, 0.75F, false) {
protected boolean removeEldestEntry(Map.Entry eldest) {
if (size() > MAX_ENTRIES) {
if (isImportant(eldest)) {
//Handle an important entry here, like reinserting it to the back of the list
this.remove(eldest.getKey());
this.put(eldest.getKey(), eldest.getValue());
//removeEldestEntry will be called again, now with the next entry
//so the size should not exceed the MAX_ENTRIES value
//WARNING: If every element is important, this will loop indefinetly!
} else {
return true; //Element is unimportant
}
return false; //Size not reached or eldest element was already handled otherwise
}
return false; //Size not reached or eldest element was already handled otherwise
}
};
lhm.put(1, "1");
lhm.put(2, "2");
lhm.put(3, "3");
lhm.put(4, "4");
lhm.put(5, "5");
lhm.put(6, "6");
lhm.put(7, "7");
lhm.put(8, "8");
lhm.put(9, "9");
lhm.put(10, "10");
System.out.println("" + lhm);
可以看到map中最多只有8個(gè)節(jié)點(diǎn)土匀，超出的話會(huì)把老的刪除子房。
remove
LinkedHashMap的刪除比HashMap的刪除多了一步afterNodeRemoval：
void afterNodeRemoval(Node<K,V> e) { // unlink
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
p.before = p.after = null;
if (b == null)
head = a;
else
b.after = a;
if (a == null)
tail = b;
else
a.before = b;
}
主要處理before和after，很簡(jiǎn)單就轧。
遍歷
HashMap遍歷的核心類是HashIterator证杭，而LinkedHashMap遍歷的核心類是LinkedHashIterator，很簡(jiǎn)單妒御，核心方法是nextNode：
final LinkedHashMap.Entry<K,V> nextNode() {
LinkedHashMap.Entry<K,V> e = next;
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (e == null)
throw new NoSuchElementException();
current = e;
next = e.after;
return e;
}
保持有序遍歷最關(guān)鍵的一行代碼是第八行：next = e.after;解愤。
最后附一張LinkedHashMap的底層結(jié)構(gòu)圖，雙向非循環(huán)鏈表：
