精读JDK源码之LinkedHashMap

LinkedHashMap继承自HashMap，拥有HashMap的所有特性，再此基础上，还提供两大特性：
1、按照插入顺序进行访问
2、实现访问最少最先删除，相当于LRU淘汰策略

属性

    /**
     * 继承hashmap的Node类，为每个元素增加类before和after属性
     */
    static class Entry<K,V> extends HashMap.Node<K,V> {
        Entry<K,V> before, after;
        Entry(int hash, K key, V value, Node<K,V> next) {
            super(hash, key, value, next);
        }
    }

    private static final long serialVersionUID = 3801124242820219131L;

    /**
     * 链表头
     */
    transient LinkedHashMap.Entry<K,V> head;

    /**
     * 链表尾
     */
    transient LinkedHashMap.Entry<K,V> tail;

    /**
     * 两种访问方式，默认false
     * false:按照插入顺序提供访问
     * true：按照访问顺序，把经常访问的值放到队尾
     */
    final boolean accessOrder;

总体来说，LinkedHashMap相当于HashMap和LinkedList结合体，把Map的每个节点串联起来，保证不同元素的顺序性

按照插入顺序访问

按照顺序新增

    //新建节点，并加到链表的尾部
    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;
    }
    private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
        LinkedHashMap.Entry<K,V> last = tail;
        tail = p;
        if (last == null)//链表为空
            head = p;
        else {//链表不为空
            p.before = last;
            last.after = p;
        }
    }

按照顺序访问

LinkedHashMaP只提供单向访问，可以通过迭代器进行访问。可以对key、value、entity提供迭代方法。

以LinkedHashIterator为例，其代码如下:

    abstract class LinkedHashIterator {
        LinkedHashMap.Entry<K,V> next;
        LinkedHashMap.Entry<K,V> current;
        int expectedModCount;


        LinkedHashIterator() {
            next = head;//头节点作为第一个访问的节点
            expectedModCount = modCount;
            current = null;
        }

        public final boolean hasNext() {
            return next != null;
        }

        final LinkedHashMap.Entry<K,V> nextNode() {
            LinkedHashMap.Entry<K,V> e = next;
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            if (e == null)//链表为空
                throw new NoSuchElementException();
            current = e;
            next = e.after;//找到下一个节点
            return e;//返回next节点，第一个返回的是头节点
        }

        public final void remove() {
            Node<K,V> p = current;
            if (p == null)
                throw new IllegalStateException();
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            current = null;
            K key = p.key;
            removeNode(hash(key), key, null, false, false);
            expectedModCount = modCount;
        }
    }

访问最少删除策略（LRU）

这种策略的意思就是经常访问的元素会被追加到队尾，这样不经常访问的就在对头，可以通过设置删除策略，删除不经常访问的节点

访问方法

    public V get(Object key) {
        Node<K,V> e;
        if ((e = getNode(hash(key), key)) == null)
            return null;
        if (accessOrder)//策略是LRU
            afterNodeAccess(e);//将这个节点移动到队尾
        return e.value;
    }

    void afterNodeAccess(Node<K,V> e) { // move node to last
        LinkedHashMap.Entry<K,V> last;
        if (accessOrder && (last = tail) != e) {//首先保证访问策略是LRU
            LinkedHashMap.Entry<K,V> p =
                (LinkedHashMap.Entry<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;
        }
    }

删除策略

LinkedHashMap本身没有put方法，调用的是HashMap的put方法（继承hashmap类），但LinkedHashMap实习了put方法中的调用afterNodeInsertion方法，这个方法实现了删除

    void afterNodeInsertion(boolean evict) { // possibly remove eldest
        LinkedHashMap.Entry<K,V> first;
        //removeEldestEntry()来控制删除策略
        if (evict && (first = head) != null && removeEldestEntry(first)) {
            K key = first.key;
            //删除头节点
            removeNode(hash(key), key, null, false, true);
        }
    }