LinkedHashMap的定义
如无特殊说明，本文以jdk7为准进行说明。
package java.util;import java.io.*;public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>{}123456123456 可以看到LinkedHashMap继承了HashMap，那么LinkedHashMap又有什么特点呢？ LinkedHashMap是Hash表和链表的实现，并且依靠着双向链表保证了迭代顺序。LinkedHashMap是非线程安全的。
LinkedHashMap如何保证迭代顺序
按照插入顺序进行迭代
Map<String,Integer> map = new LinkedHashMap<>(); map.put("s1", 1); map.put("s2", 2); map.put("s3", 3); map.put("s4", 4); map.put("s5", 5); map.put(null, 9); map.put("s6", 6); map.put("s7", 7); map.put("s8", 8); map.put(null, 11); for(Map.Entry<String,Integer> entry:map.entrySet()) { System.out.PRintln(entry.getKey()+":"+entry.getValue()); } System.out.println(map);1234567891011121314151612345678910111213141516 输出结果：
s1:1s2:2s3:3s4:4s5:5null:11s6:6s7:7s8:8{s1=1, s2=2, s3=3, s4=4, s5=5, null=11, s6=6, s7=7, s8=8}通过结果可以看到，LinkedHashMap会记录插入的顺序，允许null的键值，当key值重复时，后面的会替换前面的。LinkedHashMap的结构图
可以看到LinkedHashMap比HashMap多了一个头指针head（private权限），header指针是一个标记指针不存储任何数据。 可以看到bullet的实体Entry也比HashMap的Entry多了before和after两个指针。按照访问顺序进行迭代
LinkedHashMap还有一个私有变量accessOrder（private final boolean accessOrder；），默认为false，按照插入顺序遍历，譬如开篇的例子中；如果设置为true则按照访问顺序遍历，只能通过这个构造函数设置：
public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) { super(initialCapacity, loadFactor); this.accessOrder = accessOrder; }123456123456 接下来举个例子（和开篇的例子类似）：
Map<String,Integer> map = new LinkedHashMap<>(16,0.75f,true); map.put("s1", 1); map.put("s2", 2); map.put("s3", 3); map.put("s4", 4); map.put("s5", 5); map.put(null, 9); map.put("s6", 6); map.put("s7", 7); map.put("s8", 8); map.put(null, 11); // 此处null的key值set了第二次，也能改变数据存储的结果 map.get("s6"); // 此处是get调用，也能改变数据存储的结果 for(Map.Entry<String,Integer> entry:map.entrySet()) { System.out.println(entry.getKey()+":"+entry.getValue()); }1234567891011121314151612345678910111213141516 输出结果：
s1:1s2:2s3:3s4:4s5:5s7:7s8:8null:11s6:6 public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) { super(initialCapacity, loadFactor); this.accessOrder = accessOrder; }123456123456 接下来举个例子（和开篇的例子类似）：
Map<String,Integer> map = new LinkedHashMap<>(16,0.75f,true); map.put("s1", 1); map.put("s2", 2); map.put("s3", 3); map.put("s4", 4); map.put("s5", 5); map.put(null, 9); map.put("s6", 6); map.put("s7", 7); map.put("s8", 8); map.put(null, 11); map.get("s6"); for(Map.Entry<String,Integer> entry:map.entrySet()) { System.out.println(entry.getKey()+":"+entry.getValue()); }1234567891011121314151612345678910111213141516 输出结果：
s1:1s2:2s3:3s4:4s5:5s7:7s8:8null:11s6:6如果将上面的遍历方式改为：
for(Iterator<String> iterator = map.keySet().iterator();iterator.hasNext();) { String name = iterator.next(); System.out.println(name+"->"+map.get(name)); }1234512345运行结果出人意料：
s1->1Exception in thread "main" java.util.ConcurrentModificationException at java.util.LinkedHashMap$LinkedHashIterator.nextEntry(Unknown Source) at java.util.LinkedHashMap$KeyIterator.next(Unknown Source) at collections.map.LinkedHashMapTest.main(LinkedHashMapTest.java:33)1234512345 LinkedHashMap非但没有排序，反而程序出现了异常，这是为什么呢？
ConcurrentModificationException异常一般会在集合迭代过程中被修改事抛出。不仅仅是LinkedHashMap,所有的集合都不允许在迭代器模式中修改集合的结构。一般认为，put()、remove()方法会修改集合的结构，因此不能在迭代器中使用。但是，这段代码中并没有出现类似修改集合结构的代码，为何也会发生这样的问题？
问题就出在get()方法上。虽然一般认为get()方法是只读的，但是当前的LinkedHashMap缺工作在按照元素访问顺序排序的模式中，get()方法会修改LinkedHashMap中的链表结构，以便将最近访问的元素放置到链表的末尾，因此，这个操作便引起了这个错误。所以，当LinkedHashMap工作在这个模式时，不能再迭代器中使用get()操作。Map的遍历建议使用entrySet的方式。
LinkedHashMap的典型应用
LRU（Least recently used，最近最少使用）算法根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。实现代码如下：
import java.util.ArrayList;import java.util.Collection;import java.util.LinkedHashMap;import java.util.Map;import java.util.concurrent.locks.Lock;import java.util.concurrent.locks.ReentrantLock;public class LRULinkedHashMap<K, V> extends LinkedHashMap<K, V> { private static final long serialVersionUID = 7428629360694235373L; private final int maxCapacity; private static final float DEFAULT_LOAD_FACTOR = 0.75f; private final Lock lock = new ReentrantLock(); public LRULinkedHashMap(int maxCapacity) { super(maxCapacity, DEFAULT_LOAD_FACTOR, true); this.maxCapacity = maxCapacity; } @Override protected boolean removeEldestEntry(java.util.Map.Entry<K, V> eldest) { return size() > maxCapacity; } @Override public boolean containsKey(Object key) { try { lock.lock(); return super.containsKey(key); } finally { lock.unlock(); } } @Override public V get(Object key) { try { lock.lock(); return super.get(key); } finally { lock.unlock(); } } @Override public V put(K key, V value) { try { lock.lock(); return super.put(key, value); } finally { lock.unlock(); } } public int size() { try { lock.lock(); return super.size(); } finally { lock.unlock(); } } public void clear() { try { lock.lock(); super.clear(); } finally { lock.unlock(); } } public Collection<Map.Entry<K, V>> getAll() { try { lock.lock(); return new ArrayList<Map.Entry<K, V>>(super.entrySet()); } finally { lock.unlock(); } } public static void main(String[] args) { LRULinkedHashMap<String, String> lruMap = new LRULinkedHashMap<>(4); lruMap.put("first", "1"); lruMap.put("second", "2"); lruMap.put("third", "3"); lruMap.put("second", "two"); lruMap.get("first"); lruMap.put("fourth", "4"); lruMap.get("second"); lruMap.put("fivth", "5"); for (Map.Entry<String, String> entry : lruMap.entrySet()) { System.out.println(entry.getKey() + ":" + entry.getValue()); } }}1 输出结果：
first:1fourth:4second:twofivth:5
