简述
LinkedHashMap继承了HashMap，其操作与HashMap类似，结构也差不多。与HashMap最大区别就是通过节点Entry增加了before和after属性来维护顺序使其有序。示例根据插入顺序排序:
public static void main(String[] args) { System.out.println("**********HashMap***********"); Map hashMap = new HashMap(); hashMap.put("Marvel", "漫威"); hashMap.put("Deadpool", "死侍"); hashMap.put("Hulk", "绿巨人"); hashMap.put("Thor", "雷神"); hashMap.put("Wolverine", "金刚狼"); for (Iterator it = hashMap.entrySet().iterator(); it.hasNext(); ) { Map.Entry obj = (Map.Entry)it.next(); System.out.println(obj.getKey() + "-" +obj.getValue()); } System.out.println("**********LinkedHashMap***********"); Map linkedHashMap = new LinkedHashMap(); linkedHashMap.put("Marvel", "漫威"); linkedHashMap.put("Deadpool", "死侍"); linkedHashMap.put("Hulk", "绿巨人"); linkedHashMap.put("Thor", "雷神"); linkedHashMap.put("Wolverine", "金刚狼"); for (Iterator it = linkedHashMap.entrySet().iterator(); it.hasNext(); ) { Map.Entry obj = (Map.Entry)it.next(); System.out.println(obj.getKey() + "-" +obj.getValue()); } }复制代码 输出:
**********HashMap*********** Thor-雷神 Deadpool-死侍 Wolverine-金刚狼 Marvel-漫威 Hulk-绿巨人 **********LinkedHashMap*********** Marvel-漫威 Deadpool-死侍 Hulk-绿巨人 Thor-雷神 Wolverine-金刚狼 复制代码
源码分析
LinkedHashMap字段
final boolean accessOrder; //是否按照访问顺序，true:访问顺序，false:插入顺序 transient LinkedHashMap.Entry head; //双向链表头节点 transient LinkedHashMap.Entry tail; //双向链表尾结点 /** * 节点类继承了HashMap.Node，改成双向链表 * next表示桶上连接的Entry顺序 * before、after插入前后，插入顺序(维护双向链表) */ static class Entry extends HashMap.Node { Entry before, after; } 复制代码 构造方法
前四个默认插入排序，最后一个可指定排序，accessOrder为true时访问顺序，false时插入顺序
public LinkedHashMap() { super(); accessOrder = false; } //指定初始化容量 public LinkedHashMap(int initialCapacity) { super(initialCapacity); accessOrder = false; } //指定初始化容量和负载因子 public LinkedHashMap(int initialCapacity, float loadFactor) { super(initialCapacity, loadFactor); accessOrder = false; } //利用另一个map来构建 public LinkedHashMap(Map m) { super(); accessOrder = false; putMapEntries(m, false); } //指定初始化容量、负载因子和是否按照访问顺序 public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) { super(initialCapacity, loadFactor); this.accessOrder = accessOrder; }复制代码 put方法
LinkedHashMap沿用了HashMap的put方法，不过重写了其newNode()、afterNodeAccess()、afterNodeInsertion()方法
Node newNode(int hash, K key, V value, Node e) { //调用LinkedHashMap的entry构造方法 LinkedHashMap.Entry p = new LinkedHashMap.Entry(hash, key, value, e); linkNodeLast(p); return p; } /** * 将新增节点置于链表尾部 */ private void linkNodeLast(LinkedHashMap.Entry p) { //获取当前链表尾部节点 LinkedHashMap.Entry last = tail; //将p设为尾部节点 tail = p; //若当前集合为空，p既是头节点又是尾节点 if (last == null) head = p; else { p.before = last; last.after = p; } }复制代码 从上面的源码可以看出，linkedHashMap额外维护了一个双向链表。
再来看看afterNodeAccess()方法，在put方法若当前集合存在key对象进行替换value时会调用afterNodeAccess:/** * 将当前被访问的节点移至双向链表尾部 */ void afterNodeAccess(Node e) { // move node to last LinkedHashMap.Entry last; //若accessOrder为true且原尾节点不是节点e if (accessOrder && (last = tail) != e) { //将节点e强转为双向链表节点p，获取p插入前后的节点 LinkedHashMap.Entry p = (LinkedHashMap.Entry)e, b = p.before, a = p.after; //因为需要将e置于链表尾部，所以将其after属性设为null p.after = null; //对于双向链表，若p的前驱节点为空，头节点设为p的后继 if (b == null) head = a; else //否则将p前驱节点的后继节点设为p的后继节点 b.after = a; //若p的后继节点不为null，将p的后继节点的前驱节点设为p的前驱节点 if (a != null) a.before = b; else //否则将p的前驱节点设为尾结点 last = b; //若原尾节点为空，将p设为头节点 if (last == null) head = p; else { //否则将p的前驱节点改为原尾节点，原尾节点的后继节点改为p p.before = last; last.after = p; } //尾节点改为p tail = p; ++modCount; } } 复制代码 在put方法中新增节点情况下最后会调用afterNodeInsertion()方法，源码如下:
/** * 删除双向链表头节点 */ void afterNodeInsertion(boolean evict) { // possibly remove eldest LinkedHashMap.Entry first; if (evict && (first = head) != null && removeEldestEntry(first)) { K key = first.key; removeNode(hash(key), key, null, false, true); } } //默认返回false protected boolean removeEldestEntry(Map.Entry eldest) { return false; }复制代码 void afterNodeInsertion(boolean evict)以及boolean removeEldestEntry(Map.Entry<K,V> eldest)是构建LruCache需要的回调，在LinkedHashMap里可以忽略它们
get方法
LinkedHashMap重写了其get()方法
public V get(Object key) { Node e; if ((e = getNode(hash(key), key)) == null) return null; if (accessOrder) afterNodeAccess(e); return e.value; }复制代码 相对于HashMap的get操作，linkedHashMap多了一步操作，若accessOrder为true会调用afterNodeAccess()方法。afterNodeAccess()方法上面已经提及，需要注意的是在此方法会修改modCount即当迭代LinkedHashMap,若同时查询访问数据，会导致fail-fast，因为迭代顺序变了
remove方法
LinkedHashMap沿用了HashMap的remove()方法，不过重写了其afterNodeRemoval()方法
/** * 将节点e从双向链表中删除 */ void afterNodeRemoval(Node e) { // unlink LinkedHashMap.Entry p = (LinkedHashMap.Entry)e, b = p.before, a = p.after; //待删除节点p的前驱后继节点都置空 p.before = p.after = null; //若前驱节点为空，则将p后继节点设为头节点 if (b == null) head = a; //否则将p后继节点设为p前驱节点的后继节点 else b.after = a; //若p后继节点为空，则将p的前驱节点设为尾结点 if (a == null) tail = b; //否则p前驱节点设为p后继节点的前驱节点 else a.before = b; } 复制代码 用LinkedHashMap实现缓冲机制
FIFO
FIFO(First In First Out):先入先出，和队列一样。举个生活例子，超市购物收银台结账先排队的客户先结账离开
FIFO实现:LinkedHashMap默认(accessOrder为false)就是按存储的数据排序，满足先进先出，示例如下:public class FIFOCache extends LinkedHashMap { private final int maxSize;//限制数据 public FIFOCache(int maxSize) { super();//调用父类默认构造方法，accessOrder为false this.maxSize = maxSize; } @Override protected boolean removeEldestEntry(Map.Entry eldest) { return size() > maxSize; } public static void main(String[] args) { Map fifoCache = new FIFOCache(10);//限定10个 for (int i = 0; i < 10; i++) { fifoCache.put(i, i); } System.out.println("初始情况:" + fifoCache.toString()); fifoCache.put(6, 6);//访问已存在数据 System.out.println("已存在数据被访问后:" + fifoCache.toString()); fifoCache.put(10, 10); System.out.println("新增一个数据后:" + fifoCache.toString()); }} 复制代码 输出:
初始情况:{0=0, 1=1, 2=2, 3=3, 4=4, 5=5, 6=6, 7=7, 8=8, 9=9}已存在数据被访问后:{0=0, 1=1, 2=2, 3=3, 4=4, 5=5, 6=6, 7=7, 8=8, 9=9}新增一个数据后:{1=1, 2=2, 3=3, 4=4, 5=5, 6=6, 7=7, 8=8, 9=9, 10=10} 复制代码 从输出结果中看，其满足FIFO规则，按插入顺序进行排序，若命中缓存中的任意数据也不会破坏先进先出规则。若新增了一个缓存外的数据会把最先插入的数据移除
LRU
public class LRUCache extends LinkedHashMap { private final int maxSize; public LRUCache(int maxSize){ super(maxSize, 0.75f, true); this.maxSize = maxSize; } @Override protected boolean removeEldestEntry(Map.Entry eldest) { return size() > maxSize; } public static void main(String[] args) { Map fifoCache = new LRUCache(10);//限定10个 for (int i = 0; i < 10; i++) { fifoCache.put(i, i); } System.out.println("初始情况:" + fifoCache.toString()); fifoCache.put(6, 6);//访问已存在数据 fifoCache.get(3); System.out.println("已存在数据被访问后:" + fifoCache.toString()); fifoCache.put(10, 10); System.out.println("新增一个数据后:" + fifoCache.toString()); }}复制代码 输出:
初始情况:{0=0, 1=1, 2=2, 3=3, 4=4, 5=5, 6=6, 7=7, 8=8, 9=9}已存在数据被访问后:{0=0, 1=1, 2=2, 4=4, 5=5, 7=7, 8=8, 9=9, 6=6, 3=3}新增一个数据后:{1=1, 2=2, 4=4, 5=5, 7=7, 8=8, 9=9, 6=6, 3=3, 10=10}复制代码 从输出结果中可以看出，符合LRU规则
总结
LinkedHashMap几乎与HashMap一样，其最大区别就是节点类多了before和after属性额外维护双向链表用来实现插入顺序(默认)或访问顺序排序
参考
https://blog.csdn.net/u012403290/article/details/68926201