自己动手写写：LinkedHashMap源码浅析
此系列文章中，上一篇是关于HashMap的源码剖析，这篇文章将向大家剖析一下LinkedHashMap的源码！
?
四. LinkedHashMap
?
我们知道从API的描述中可以看出HashMap与LinkedHashMap最大的不同在于，后者维护者一个运行于所有条目的双向链表。有了这个双向链表，就可以在迭代的时候按照插入的顺序迭代出元素(当然也可以通过LRU算法迭代元素，下面会讲到)。
?
1. 类结构
public class LinkedHashMap<K, V> extends HashMap<K, V> implements Map<K, V>
?
我们可以看出LinkedHashMap继承了HashMap！
?
2. 几个重要的成员变量
/** * 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;
?
?对于父类HashMap中的成员变量这里就不讲了，可参考http://boy00fly.iteye.com/blog/1139845
?其中Entry类是LinkedHashMap的内部类定义，代码片段如下：
//继承了HashMap.Entry private static class Entry<K, V> extends HashMap.Entry<K, V>//新增的两个成员变量 Entry<K, V> before, after;
?
?可以看得出来新增的这两个变量就是双向链表实现的关键！！分别指向当前Entry的前一个、后一个Entry。
?
header就是指向双向链表的头部！
accessOrder：true则按照LRU算法迭代整个LinkedHashMap，false则按照元素的插入顺序迭代！
?
3. 几个重要的构造函数
/** * 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; }?? ?是不是很简单，也可参考http://boy00fly.iteye.com/blog/1139845这篇文章的构造函数分析。其中accessOrder就是我们上面所讲的控制迭代顺序的开关，只有此构造函数有这个参数，其他的构造函数默认就是false。
?
4. 几个重要的方法
/** * Called by superclass constructors and pseudoconstructors (clone, * readObject) before any entries are inserted into the map. Initializes * the chain. */ void init() { header = new Entry<K, V>(-1, null, null, null); header.before = header.after = header; }?此方法是在父类构造函数初始化的时候调用的，LinkedHashMap重写了init方法。代码中表达的意思也很明确了，这是双向链表的初始化状态。
?
?
?
/** * 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++; } /** * 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; } ?
?addEntry方法是父类HashMap的一个方法，被put相关的方法所调用即在新增元素的时候调用。
?我们通过形象的图来看一个基本的流程：
（从初始化到添加了3个元素过程中，各个元素before、after引用变化，画的有点丑，呵呵，不过意思能够表达清楚，代码的内容就不再累述了，大体和HashMap类似！）
?
?
?
再介绍一个get方法
?
/** * 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; } /** * This method is invoked by the superclass whenever the value * of a pre-existing entry is read by Map.get or modified by Map.set. * If the enclosing Map is access-ordered, it moves the entry * to the end of the list; otherwise, it does nothing. */ void recordAccess(HashMap<K, V> m) { LinkedHashMap<K, V> lm = (LinkedHashMap<K, V>)m; 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; } ?
?这里我们来看一下recordAccess方法！
上面我们不是讲过accessOrder这个参数值控制着LinkedHashMap的迭代顺序嘛，这里我们来看一下。
?当accessOrder为true时，remove方法就是将当前元素从双向链表中移除，
addBefore方法再将当前元素插入到链表的头部去，这样最近读到的元素，在迭代的时候是优先被迭代出来的！
这就是所谓的LRU算法（Least Recently Used）：最近最少使用算法。
当accessOrder为false时，不做任何事情，就按照插入顺序迭代出来！
?
还有些其他的方法这里也不再累述了，重点的都在上面阐述了！