LinkedHashMap 简介

LinkedHashMap 继承了 HashMap，但是相对于 HashMap，它又保证了元素的有序性。

它内部维护了一个双向链表，并且有两种排序方式：

访问排序

举个例子

    LinkedHashMap<Object, Object> linkedHashMap = new LinkedHashMap<>(16, 0.75f, true);
    linkedHashMap.put("1","1");
    linkedHashMap.put("2","2");
    linkedHashMap.put("3","3");
    linkedHashMap.put("4","3");
    linkedHashMap.get("1");
    linkedHashMap.get("2");
    for (Map.Entry<Object, Object> objectObjectEntry : linkedHashMap.entrySet()) {
        Map.Entry entry = (Map.Entry) objectObjectEntry;
        System.out.println(entry.getKey() + "，" + entry.getValue());
    }

输出是

2,2
1,1
4,4
3,3

将最近访问的优先输出，Android 的 LruCache 也是基于这个实现的 LRU 算法。

插入排序

    LinkedHashMap<Object, Object> linkedHashMap = new LinkedHashMap<>();
    linkedHashMap.put("1","1");
    linkedHashMap.put("2","2");
    linkedHashMap.put("3","3");
    linkedHashMap.put("4","3");
    linkedHashMap.get("1");
    linkedHashMap.get("2");
    for (Map.Entry<Object, Object> objectObjectEntry : linkedHashMap.entrySet()) {
        Map.Entry entry = (Map.Entry) objectObjectEntry;
        System.out.println(entry.getKey() + "，" + entry.getValue());
    }

输出是

1,1
2,2
3,3
4,4

按照插入先后顺序输出。

分析

对于 LinkedHashMap，其核心地方在于，它是如何实现一个双向链表，并且如何实现访问和插入顺序的排列。

按照之前看集合的逻辑，先从 put 方法下手，点进去后可以发现 LinkedHashMap 并未重新实现 put 方法，而其中调用的 putVal 方法中可以发现调用了两个空方法，直接点进去看，可以看到 HashMap 提供了三个方法供 LinkedHashMap 实现（具体源码就不贴了）。

    // Callbacks to allow LinkedHashMap post-actions
    //这个方法用来实现访问后的操作
    void afterNodeAccess(Node<K,V> p) { }
    //这个方法用来实现插入后的操作
    void afterNodeInsertion(boolean evict) { }
    //这个方法用来实现移除后的操作
    void afterNodeRemoval(Node<K,V> p) { }

可想而知，LinkedHashMap 排序的核心实现就是这三个方法，我们也将从这三个方法开始分析：

afterNodeAccess 方法

    void afterNodeAccess(Node<K,V> e) { // move node to last
        LinkedHashMapEntry<K,V> last;
        //如果开启了访问排序模式，并且当前访问的节点不是队列的尾部的节点
        if (accessOrder && (last = tail) != e) {
            //接下来的操作便是将访问的节点移动到队列的尾部。
            LinkedHashMapEntry<K,V> p =
                (LinkedHashMapEntry<K,V>)e, b = p.before, a = p.after;
            p.after = null;
            if (b == null)
                head = a;
            else
                b.after = a;
            if (a != null)
                a.before = b;
            else
                last = b;
            if (last == null)
                head = p;
            else {
                p.before = last;
                last.after = p;
            }
            tail = p;
            ++modCount;
        }
    }

如果开启访问模式，那么 get 方法中会使用这个方法，逻辑简单，就不贴源码了。

afterNodeInsertion 方法

    //根据注释来看， 这个方法可能会移除队列头部的对象，主要是解决溢出问题
    void afterNodeInsertion(boolean evict) { // possibly remove eldest
        LinkedHashMapEntry<K,V> first;
        if (evict && (first = head) != null && removeEldestEntry(first)) {
            K key = first.key;
            removeNode(hash(key), key, null, false, true);
        }
    }
    
    protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
        //这个方法默认返回 false， 说明上述方法基本与我们的操作无关，除非重写这个方法自定义队列的规则。
        return false;
    }

afterNodeRemoval 方法

    //将节点从双向链表中删除
    void afterNodeRemoval(Node<K,V> e) { // unlink
        LinkedHashMapEntry<K,V> p =
            (LinkedHashMapEntry<K,V>)e, b = p.before, a = p.after;
        p.before = p.after = null;
        if (b == null)
            head = a;
        else
            b.after = a;
        if (a == null)
            tail = b;
        else
            a.before = b;
    }

这里 LinkedHashMap 依然沿用了 remove 方法。

创建及插入队列

以上三个方法都是维护队列，但是并没有如何生成双向队列的逻辑，其实 LinkedHashMap 重写了 newNode 和 newTreeNode 这两个方法，当 HashMap 加入新值时，它会将这个值放入自己维护的队列。

    Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
        LinkedHashMapEntry<K,V> p =
            new LinkedHashMapEntry<K,V>(hash, key, value, e);
        linkNodeLast(p);
        return p;
    }
    
    TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) {
        TreeNode<K,V> p = new TreeNode<K,V>(hash, key, value, next);
        linkNodeLast(p);
        return p;
    }

同样，替换节点时的方法也被重写，这里以插入为例。

它们都实现了 linkNodeLast 方法：

    // link at the end of list
    private void linkNodeLast(LinkedHashMapEntry<K,V> p) {
        //将新的插入的节点放到队列尾部。
        LinkedHashMapEntry<K,V> last = tail;
        tail = p;
        if (last == null)
            head = p;
        else {
            p.before = last;
            last.after = p;
        }
    }

小结

从这三个方法可以看出，LinkedHashMap 在基于 HashMap 的基础上，额外维护了一个双向链表来实现排序，自身实现或者重写的方法，也都是以维护这个队列为目的。

Java集合 —— LinkedHashMap源码笔记