本文簡單分析一下JDK1.7的LinkedHashMap源碼，看一下其内部的結構以及典型方法的實作
LinkedHashMap的内部結構
檢視JDK中LinkedHashMap的源碼，我們發現LinkedHashMap實作了Map接口，并且其繼承于HashMap，源碼如下：
public class LinkedHashMap<K,V>
extends HashMap<K,V>
implements Map<K,V> 複制
我們知道，
在HashMap中，元素的疊代順序是無序的，不可控的
如
public class HashMapExample {
public static void main(String[] args) {
Map<String, Integer> map = new HashMap<>();
map.put("One", 1);
map.put("Two", 2);
map.put("Three", 3);
map.put("Four", 4);
map.put("Five", 5);
map.put("Six", 6);
map.put("Seven", 7);
map.put("Eight", 8);
map.put("Nine", 9);
map.put("Ten", 10);
for(Entry<String,Integer> entry : map.entrySet()) {
System.out.println(entry.getKey() + "=" + entry.getValue());
}
}
} 複制
輸出結果
Six=6
Nine=9
Ten=10
Seven=7
Five=5
Three=3
One=1
Eight=8
Four=4
Two=2 複制
其輸出的結構取決于table中存的内容來處理的，在HashMap中，其資料結構基于數組+連結清單~ 疊代擷取元素的時，其先周遊數組（table[]），table中的元素是連結清單，然後周遊連結清單，是以上述輸出的結果和如下debug結果圖是一緻的
因為LinkedHashMap繼承自HashMap，是以，如果想對HashMap有更好的了解，可以參考我之前寫的博文HashMap的實作原理淺析
然後，使用LinkedHashMap來完成上述示例，看看有什麼不同
public class LinkedHashMapExample {
public static void main(String[] args) {
Map<String, Integer> map = new LinkedHashMap<>();
map.put("One", 1);
map.put("Two", 2);
map.put("Three", 3);
map.put("Four", 4);
map.put("Five", 5);
map.put("Six", 6);
map.put("Seven", 7);
map.put("Eight", 8);
map.put("Nine", 9);
map.put("Ten", 10);
for(Entry<String,Integer> entry : map.entrySet()) {
System.out.println(entry.getKey() + "=" + entry.getValue());
}
}
} 複制
輸出結果
One=1
Two=2
Three=3
Four=4
Five=5
Six=6
Seven=7
Eight=8
Nine=9
Ten=10 複制
從上述結果可以看出，
輸出的結果和存放的順序是一緻的，也就是說LinkedHashMap的元素是有序的
那麼，LinkedHashMap是如何做的呢？
帶着問題，檢視LinkedHashMap的實作，我們可以看到，LinkedHashMap使用雙端隊列來存儲元素
public class LinkedHashMap<K,V>
extends HashMap<K,V>
implements Map<K,V>
{
private static final long serialVersionUID = 3801124242820219131L;
/**
* The head of the doubly linked list.
*/
private transient Entry<K,V> header; 複制
LinkedHashMap的内部類Entry
/**
* LinkedHashMap entry.
*/
private static class Entry<K,V> extends HashMap.Entry<K,V> {
// These fields comprise the doubly linked list used for iteration.
Entry<K,V> before, after;
Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {
super(hash, key, value, next);
}
複制
從上述Entry代碼可以看出，
LinkedHashMap的内部類Entry繼承自 HashMap.Entry<K,V>
也就是說其在HashMap.Entry<K,V> 的基礎上又添加了兩個屬性after和before，分别表示下一個節點和前一個節點，正是這些額外的操作，才可以讓LinkedHashMap變得有序
接下來，我們一起來看一些LinkedHashMap的實作
方法containsValue的實作
源代碼
/**
* Returns <tt>true</tt> if this map maps one or more keys to the
* specified value.
*
* @param value value whose presence in this map is to be tested
* @return <tt>true</tt> if this map maps one or more keys to the
* specified value
*/
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;
} 複制
判斷一個對象是否在LinkedHashMap中存在，查找的對象區分null和非null，兩者都是以header.after作為第一個節點，然後使用節點的after屬性依次判斷。其中，對象為null，則直接比較null值；如果不為null，則使用equals方法來判斷
方法get(Object key)的實作
源代碼
/**
* Returns the value to which the specified key is mapped,
* or {@code null} if this map contains no mapping for the key.
*
* <p>More formally, if this map contains a mapping from a key
* {@code k} to a value {@code v} such that {@code (key==null ? k==null :
* key.equals(k))}, then this method returns {@code v}; otherwise
* it returns {@code null}. (There can be at most one such mapping.)
*
* <p>A return value of {@code null} does not <i>necessarily</i>
* indicate that the map contains no mapping for the key; it's also
* possible that the map explicitly maps the key to {@code null}.
* The {@link #containsKey containsKey} operation may be used to
* distinguish these two cases.
*/
public V get(Object key) {
Entry<K,V> e = (Entry<K,V>)getEntry(key);
if (e == null)
return null;
e.recordAccess(this);
return e.value;
} 複制
LinkedHashMap的get(Object o)方法，主要調用了父類HashMap的getEntry方法
方法clear的實作
源代碼
/**
* Removes all of the mappings from this map.
* The map will be empty after this call returns.
*/
public void clear() {
super.clear();
header.before = header.after = header;
} 複制
LinkedHashMap的clear方法，也調用了父類HashMap的方法，然後将header.before和header.after都指向header
LinkedHashMap中Iterator的實作
源代碼
- LinkedHashMap定義了一個實作Iterator<T>接口的抽象類
private abstract class LinkedHashIterator<T> implements Iterator<T> {
Entry<K,V> nextEntry = header.after;
Entry<K,V> lastReturned = null;
/**
* The modCount value that the iterator believes that the backing
* List should have. If this expectation is violated, the iterator
* has detected concurrent modification.
*/
int expectedModCount = modCount;
public boolean hasNext() {
return nextEntry != header;
}
public void remove() {
if (lastReturned == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
LinkedHashMap.this.remove(lastReturned.key);
lastReturned = null;
expectedModCount = modCount;
}
Entry<K,V> nextEntry() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (nextEntry == header)
throw new NoSuchElementException();
Entry<K,V> e = lastReturned = nextEntry;
nextEntry = e.after;
return e;
}
} 複制
從上述可以看出，疊代器使用的使用會将header.after作為下一個節點nextEntry，然後hashNext()方法通過nextEntry ！= header來判斷
- LinkedHashMap定義了繼承抽象類LinkedHashIterator的三個内部類，KeyItertor, ValueIterator以及EntryIterator, 分别用于key值的疊代、value值的疊代以及Entry的疊代
private class KeyIterator extends LinkedHashIterator<K> {
public K next() { return nextEntry().getKey(); }
}
private class ValueIterator extends LinkedHashIterator<V> {
public V next() { return nextEntry().value; }
}
private class EntryIterator extends LinkedHashIterator<Map.Entry<K,V>> {
public Map.Entry<K,V> next() { return nextEntry(); }
} 複制
- 這些Iterator将重寫父類的iterator（）方法
// These Overrides alter the behavior of superclass view iterator() methods
Iterator<K> newKeyIterator() { return new KeyIterator(); }
Iterator<V> newValueIterator() { return new ValueIterator(); }
Iterator<Map.Entry<K,V>> newEntryIterator() { return new EntryIterator(); }
複制
New Entry的實作
源代碼
/**
* 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) {
super.addEntry(hash, key, value, bucketIndex);
// Remove eldest entry if instructed
Entry<K,V> eldest = header.after;
if (removeEldestEntry(eldest)) {
removeEntryForKey(eldest.key);
}
}
/**
* 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<>(hash, key, value, old);
table[bucketIndex] = e;
e.addBefore(header);
size++;
} 複制
addBefore方法如下：
/**
* Inserts this entry before the specified existing entry in the list.
*/
private void addBefore(Entry<K,V> existingEntry) {
after = existingEntry;
before = existingEntry.before;
before.after = this;
after.before = this;
} 複制
因為調用addBefore傳的參數為header，是以做了如下幾個步驟：
- 新的節點next引用指向header
- 新的節點before引用将指向目前最後一個節點，也即headerbefore
- 目前最後一個節點的next引用将不在指向header，而指向目前節點
- Header的before引用将指向新的節點
一個簡單示例
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Map.Entry;
public class LinkedHashMapExample {
public static void main(String[] args) {
Map<Integer, String> map = new LinkedHashMap<>();
map.put(1, "One");
map.put(2, "Two");
for (Entry<Integer, String> entry : map.entrySet()) {
System.out.println(entry.getKey() + "=" + entry.getValue());
}
}
} 複制
未添加元素之前，以及每次添加節點的debug截圖如下：
accessOrder的作用
源代碼
public class LinkedHashMap<K,V>
extends HashMap<K,V>
implements Map<K,V>
{
private static final long serialVersionUID = 3801124242820219131L;
/**
* The head of the doubly linked list.
*/
private transient Entry<K,V> header;
/**
* The iteration ordering method for this linked hash map: <tt>true</tt>
* for access-order, <tt>false</tt> for insertion-order.
*
* @serial
*/
private final boolean accessOrder; 複制
accessOrder的作用
從LinkedHashMap的源碼可以發現一個屬性accessOrder~ 從描述可以看出該字段用于疊代的順序，其中：
- 如果accessOrder的值為true，則使用通路順序
- 如果accessOrder的值為false，則使用插入順序
該值不指定的時候，會指派為false，也就是疊代輸出的順序為插入的順序，這個在本文開頭的示例中以有展示。如，在構造函數中指派為false
/**
* Constructs an empty insertion-ordered <tt>LinkedHashMap</tt> instance
* with the specified initial capacity and load factor.
*
* @param initialCapacity the initial capacity
* @param loadFactor the load factor
* @throws IllegalArgumentException if the initial capacity is negative
* or the load factor is nonpositive
*/
public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
accessOrder = false;
}
/**
* Constructs an empty insertion-ordered <tt>LinkedHashMap</tt> instance
* with the specified initial capacity and a default load factor (0.75).
*
* @param initialCapacity the initial capacity
* @throws IllegalArgumentException if the initial capacity is negative
*/
public LinkedHashMap(int initialCapacity) {
super(initialCapacity);
accessOrder = false;
}
/**
* Constructs an empty insertion-ordered <tt>LinkedHashMap</tt> instance
* with the default initial capacity (16) and load factor (0.75).
*/
public LinkedHashMap() {
super();
accessOrder = false;
} 複制
當然，還有一個構造函數，可以制定accessOrder的值
/**
* Constructs an empty <tt>LinkedHashMap</tt> instance with the
* specified initial capacity, load factor and ordering mode.
*
* @param initialCapacity the initial capacity
* @param loadFactor the load factor
* @param accessOrder the ordering mode - <tt>true</tt> for
* access-order, <tt>false</tt> for insertion-order
* @throws IllegalArgumentException if the initial capacity is negative
* or the load factor is nonpositive
*/
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
} 複制
接下來，我們一下來看一下accessOrder為false和為true的示例：
accessOrder為true和false的示例
public class AccessOrderExample {
public static void main(String[] args) {
Map<Integer, String> insertOrder = new LinkedHashMap<>(16, 0.75f, false);
insertOrder.put(1, "a");
insertOrder.put(3, "c");
insertOrder.put(2, "b");
System.out.println("insertOrder執行get方法之前的内容:" + insertOrder);
String v = insertOrder.get(3);
System.out.println("insertOrder執行get方法之後的内容:" + insertOrder);
System.out.println();
Map<Integer, String> accessOrder = new LinkedHashMap<>(16, 0.75f, true);
accessOrder.put(1, "a");
accessOrder.put(3, "c");
accessOrder.put(2, "b");
System.out.println("accessOrder執行get方法之前的内容:" + accessOrder);
v = accessOrder.get(3);
System.out.println("accessOrder執行get方法之後的内容:" + accessOrder);
}
} 複制
- 輸出結果
insertOrder執行get方法之前的内容:{1=a, 3=c, 2=b}
insertOrder執行get方法之後的内容:{1=a, 3=c, 2=b}
accessOrder執行get方法之前的内容:{1=a, 3=c, 2=b}
accessOrder執行get方法之後的内容:{1=a, 2=b, 3=c} 複制
從上述結果可以看出，如果accessOrder為true，則其使用基于通路順序來操作，上述執行個體中，執行
v = accessOrder.get(3);操作之後，這個元素被加到最後，是以get操作之前和之後的連結清單内容發生了變化，這裡使用了使用了LRU（ 最近最少被使用的排程算法)。
LinkedHashMap有序 VS. TreeMap排序
從上面的分析，我們看到LinkedHashMap通過雙端連結清單能夠保證元素的有序性，但是，有序不是排序，如果要使Map中的元素排序，則需要使用TreeMap【使用紅黑樹實作】
示例代碼
public static void main(String[] args) {
Map<String, Integer> linkedHashMap = new LinkedHashMap<>();
linkedHashMap.put("One", 1);
linkedHashMap.put("One", 1);
linkedHashMap.put("Two", 2);
linkedHashMap.put("Three", 3);
linkedHashMap.put("Four", 4);
linkedHashMap.put("Five", 5);
linkedHashMap.put("Six", 6);
linkedHashMap.put("Seven", 7);
linkedHashMap.put("Eight", 8);
linkedHashMap.put("Nine", 9);
linkedHashMap.put("Ten", 10);
System.out.println("linkedHashMap内容:");
for(Entry<String,Integer> entry : linkedHashMap.entrySet()) {
System.out.println(entry);
}
System.out.println();
Map<String, Integer> treeMap = new TreeMap<>();
treeMap.put("One", 1);
treeMap.put("One", 1);
treeMap.put("Two", 2);
treeMap.put("Three", 3);
treeMap.put("Four", 4);
treeMap.put("Five", 5);
treeMap.put("Six", 6);
treeMap.put("Seven", 7);
treeMap.put("Eight", 8);
treeMap.put("Nine", 9);
treeMap.put("Ten", 10);
System.out.println("treeMap内容:");
for(Entry<String,Integer> entry : treeMap.entrySet()) {
System.out.println(entry);
}
} 複制
輸出結果：
linkedHashMap内容:
One=1
Two=2
Three=3
Four=4
Five=5
Six=6
Seven=7
Eight=8
Nine=9
Ten=10
treeMap内容:
Eight=8
Five=5
Four=4
Nine=9
One=1
Seven=7
Six=6
Ten=10
Three=3
Two=2 複制
從結果可以看出：
LinkedHashMap輸出結果和插入結果一緻，保持了有序性；
TreeMap輸出結果是按照key值排序輸出的~
上述是一個簡單的LinkedHashMap的TreeMap的示例比較，TreeMap的實作細節将在後續做分析~這裡就不再說明了。
夜深了，本次，源碼閱讀就到這裡了