LinkedHashMap原理分析

一.前言

首先HashMap中因为插入的随机hash，所以读取hash表的时候，是无顺序的，无法按照插入的顺序取出数据，LinkedHashMap 继承自HashMap，它内部维护了一个双向链表，链表的维护就是按照元素的插入（或访问）的顺序来的，所以LinkedHashMap可以保证 map集合的读取顺序。

public class LinkedHashMap<K,V>
    extends HashMap<K,V>
    implements Map<K,V>

    /**
     * The head (eldest) of the doubly linked list.
     */
     //双向链的头节点，存放最早插入的数据
    transient LinkedHashMap.Entry<K,V> head;

    /**
     * The tail (youngest) of the doubly linked list.
     */
     //双向链的头节点，存放最新插入的数据
    transient LinkedHashMap.Entry<K,V> tail;

    /**
     * The iteration ordering method for this linked hash map: <tt>true</tt>
     * for access-order, <tt>false</tt> for insertion-order.
     * 这个开关表示是否开启按照元素访问顺序排序，我前面介绍内存页淘汰算法时有写过使用LinkedHashMap实现LRU就是这个支持    
     * @serial
     */
    final boolean accessOrder;

二.构造方法

默认无参情况下，不开启按访问顺序排序

    public LinkedHashMap() {
        super();
        accessOrder = false;
    }

但是你可以指定开启按访问顺序排序

    public LinkedHashMap(int initialCapacity,
                         float loadFactor,
                         boolean accessOrder) {
        super(initialCapacity, loadFactor);
        this.accessOrder = accessOrder;
    }

三.操作

LinkedHashMap没有重写HashMap的put方法，所以它和hashmap的put操作一样，但是重写了下面三个方法

    // Callbacks to allow LinkedHashMap post-actions
    //元素节点被访问后执行
    void afterNodeAccess(Node<K,V> p) { }
    //元素节点被插入后执行
    void afterNodeInsertion(boolean evict) { }
    //元素节点被删除后执行
    void afterNodeRemoval(Node<K,V> p) { }

上面的三个方法是HashMap中的实现，可以发现没有做任何事，但是LinkedHashMap中重写了上述三个方法，具体的功能下面一一介绍。

元素插入后执行方法分析（对外提供实现LRU的关键入口）& 插入元素的链表维护操作

首先来看下HashMap中的put方法

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        //插入元素
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
            
        //省去很多行，具体看jdk源码...........
        //插入元素后执行插入后操作，evict是一个布尔值，默认put操作传入的是true，表示是否需要判断是否过期淘汰最老的元素（参考我前面写的LRU博客）
        afterNodeInsertion(evict);
        return null;
    }

因为LinkedHashMap重写了afterNodeInsertion(evict);，所以LinkedHashMap调用父类的put方法插入元素时，最后就会执行重写的方法，具体实现如下：

    void afterNodeInsertion(boolean evict) { // possibly remove eldest
        LinkedHashMap.Entry<K,V> first;
        if (evict && (first = head) != null && removeEldestEntry(first)) {
            K key = first.key;
            removeNode(hash(key), key, null, false, true);
        }
    }

上面的注释中，我描述的是evict这个开关变量是是否需要判断是否过期淘汰最老的元素,第一个是否就是evict值，第二个是否就是(first = head) != null && removeEldestEntry(first)来决定的。
所以，如果evict为true，并且当前双向链表的头节点不是空（表示当前的map是有元素的，没元素还淘汰个der），并且removeEldestEntry(first)方法返回的值是true，那么就淘汰双向链表的头节点（前面已经介绍了，这个元素就是维护的最老的元素,上面探讨的需要你了解过LRU，可以参考我的这篇文章）

所以到底什么时候才淘汰最老的元素，最终都是取决于removeEldestEntry方法，在LinkedHashMap中这个方法如下：

    protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
        return false;
    }

可以看到默认LinkedHashMap是不会淘汰元素的，所以默认是不具备LRU功能的
23年的搬砖经验告诉我们，这个protect很明显就是要我们自己继承实现嘛，所以我们可以自己实现LinkedHashMap的子类，实现removeEldestEntry方法，自己决定淘汰的策略。比如我在前面的内存页面置换算法LRU中是这样实现的：

    //重写map的removeEldestEntry方法，相当于只有当前物理内存中的页帧数超过最大限制才会执行
    @Override
    protected boolean removeEldestEntry(Map.Entry eldest) {
        return size() > DEFAULT_LRUSIZE;
    }

所以，从上面我们就可以知道，通过removeEldestEntry方法就可以实现，每次插入元素后保证是否需要删除，也就是说removeEldestEntry这个方法就为我们提供了使用LinkedHashMap来实现LRU的入口；

那么你应该有个疑问，LinkedHashMap中维护了一个双向链表，这个链表头尾顺序记录的是元素插入和访问的顺序，那么上面的插入后执行的方法中我们也没有看到将当前插入的元素作为新的链表尾节点呀（使用链表记录插入顺序），其实不然，LinkedHashMap重写了HashMap中的newNode方法

    Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
        return new Node<>(hash, key, value, next);
    }

LinedHashMap重写后:

    Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
        LinkedHashMap.Entry<K,V> p =
            new LinkedHashMap.Entry<K,V>(hash, key, value, e);
        linkNodeLast(p);
        return p;
    }
    
    // link at the end of list
    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;
        }
    }

很明显，这里就解决了你担心的问题，更新链表尾节点就是在这里完成的，所以每次插入一定会执行，因为都需要newNode新建一个节点元素

元素访问执行
其实都是一样的思路，同样的在相关操作之后调用相应的回调方法
元素访问后，如果LinkedHashMap开启了维护访问顺序（就是如果一个元素被访问,如get操作等，那么就将这个元素移到双向链表尾部，表示这是最新操作的元素），那么就会执行相应的方法，下面是LinkedHashMap重写的get方法

    public V get(Object key) {
        Node<K,V> e;
        //调用HashMap的getNode方法获取元素
        if ((e = getNode(hash(key), key)) == null)
            return null;
        //获取元素后，如果开启了维护访问顺序，那么就执行afterNodeAccess
        if (accessOrder)
            afterNodeAccess(e);
        return e.value;
    }

afterNodeAccess方法在LinkedHashMap中被重写

void afterNodeAccess(Node<K,V> e) { // move node to last
        LinkedHashMap.Entry<K,V> last;
        //如果开启了维护访问顺序,并且当前访问的元素目前不在尾节点
        if (accessOrder && (last = tail) != e) {
            LinkedHashMap.Entry<K,V> p =
                (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
            //双向链表尾节点afer指针指向null
            p.after = null;
            //如果当前插入元素的前一个节点为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中的元素被访问后,如果开启了维护访问顺序,就可以实现LRU中的最新访问元素置新的效果;

元素移除执行

这个很简单,就是每次删除元素节点后,将双向链表中的元素也删除就好,LinkedHashMap中也就是这样重写的

    void afterNodeRemoval(Node<K,V> e) { // unlink
        LinkedHashMap.Entry<K,V> p =
            (LinkedHashMap.Entry<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继承了HashMap,其在内部维护了一个双向链表,默认情况下,这个双向链表会按照插入顺序保存元素节点,删除操作时也会维护同步双向链表,并且LinkedHashMap还提供了LRU的实现接口开关,用户自己实现removeEldestEntry方法来表示是否开启插入时判断是否淘汰元素(这个也是在插入后回调方法中), 并且LinkedHashMap还提供了是否开启维护访问顺序,如果也开启了,那么就是完整的LRU功能了.

可以看出来,LinkedHashMap无论是在时间还是空间上都会低于HashMap,因为其要维护一个双向链表.

本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名,转载请标明出处
最后编辑时间为: 2021/09/17 11:16