本文简单分析一下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的实现细节将在后续做分析~这里就不再说明了。
夜深了，本次，源码阅读就到这里了