LinkedHashMap 源码分析

| 作者 Siran | 2100字 | 阅读大约需要5分钟

归档于 Java | 标签 #Map

问题

LinkedHashMap 的内部结构是什么？
LinkedHashMap 是有序的吗？
LinkedHashMap如何实现LRU缓存淘汰策略？

简述

LinkedHashMap 继承HashMap，拥有HashMap的所有特性，并且添加了顺序访问的特点，HashMap是无序的

内部维护一个双向链表，能保证元素的插入是顺序访问的，也能以访问顺序访问，可以用来实现LRU缓存策略。

可以把LinkHashMap 看做是 LinkedList + HashMap 的结合体

源码分析

Map 类图

属性

//LinkedHashMap中双向链表的头节点
transient LinkedHashMap.Entry<K,V> head;

//LinkedHashMap中双向链表的尾节点
transient LinkedHashMap.Entry<K,V> tail;

//是否按访问顺序排序 
final boolean accessOrder;

构造方法

public LinkedHashMap(int initialCapacity, float loadFactor) {
        super(initialCapacity, loadFactor);
        accessOrder = false;
    }
public LinkedHashMap(int initialCapacity) {
        super(initialCapacity);
        accessOrder = false;
    }
public LinkedHashMap() {
        super();
        accessOrder = false;
    }
public LinkedHashMap(Map<? extends K, ? extends V> m) {
        super();
        accessOrder = false;
        putMapEntries(m, false);
    }
public LinkedHashMap(int initialCapacity,
                         float loadFactor,
                         boolean accessOrder) {
        super(initialCapacity, loadFactor);
        this.accessOrder = accessOrder;
    }

前四个构造方法accessOrder都等于false，说明双向链表是按插入顺序存储元素。

最后一个构造方法accessOrder从构造方法参数传入，如果传入true，则就实现了按访问顺序存储元素，这也是实现LRU缓存策略的关键。

LRU(Least Recently Used)：最近最少使用，也就是优先淘汰最近最少使用的元素。
还有一个和LRU类似的算法LFU(Least Frequence Used)：最近使用次数最少的，也就是优先淘汰最近使用次数最少的元素的。

Entry 内部类

//位于LinkedHashMap中
static class Entry<K,V> extends HashMap.Node<K,V> {
        //before、after 用于存放双向链表，保证有序
        Entry<K,V> before, after;

        //这里的Node就是HashMap中的单向链表
        Entry(int hash, K key, V value, Node<K,V> next) {
            super(hash, key, value, next);
        }
    }

也就是说LinkedHashMap 单独维护了一个双向链表为了增加有序访问的特性，性能会比HashMap 差一点

afterNodeInsertion(boolean evict)方法

在节点插入之后做些什么，在HashMap#putVal()方法中被调用，可以看到HashMap中这个方法的实现为空。

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

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

（1）如果evict为true，且头节点不为空，且确定移除最老的元素，那么就调用HashMap.removeNode()把头节点移除（这里的头节点是双向链表的头节点，而不是某个桶中的第一个元素）；

（2）HashMap.removeNode()从HashMap中把这个节点移除之后，会调用afterNodeRemoval()方法；

（3）afterNodeRemoval()方法在LinkedHashMap中也有实现，用来在移除元素后修改双向链表

（4）默认removeEldestEntry()方法返回false，也就是不删除元素。

afterNodeAccess(Node e)方法

在节点访问之后被调用，主要在put()已经存在的元素或get()时被调用，如果accessOrder为true，调用这个方法把访问到的节点移动到双向链表的末尾。

void afterNodeAccess(Node<K,V> e) { // move node to last
        LinkedHashMap.Entry<K,V> last;
        //<1> accessOder 为true的话就是按照访问顺序排序， 并且访问的节点不是尾节点(尾节点不需要移动)
        if (accessOrder && (last = tail) != e) {
            //<2> 把访问的节点赋值为p  前节点赋值b  后继节点赋值a  
            LinkedHashMap.Entry<K,V> p =
                (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
            //<2.1> 把p节点从双向链表中移除
            p.after = null;
            if (b == null)
                head = a;
            else
                b.after = a;
            if (a != null)
                a.before = b;
            else
                last = b;
            //<2.2> 把p节点放到双向链表的末尾
            if (last == null)
                head = p;
            else {
                p.before = last;
                last.after = p;
            }
            //尾节点等于p
            tail = p;
            ++modCount;
        }
    }

（1）如果accessOrder为true，并且访问的节点不是尾节点

（2）从双向链表中移除访问的节点

（3）把访问的节点加到双向链表的末尾（末尾为最新访问的元素）

afterNodeRemoval(Node e)方法

在节点被删除之后调用的方法。

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

get(Object key)方法

获取元素

public V get(Object key) {
        Node<K,V> e;
        //<1> 调用HashMap中的 getNode 方法获取元素的值
        if ((e = getNode(hash(key), key)) == null)
            return null;
        //<2> 如果查找到了元素，且accessOrder为true，则调用afterNodeAccess()方法把访问的节点移到双向链表的末尾。
        if (accessOrder)
            afterNodeAccess(e);
        return e.value;
    }

(1) 调用 HashMap 中的 getNode 方法获取元素的值

(2) 如果查找到了元素，且accessOrder为true，则调用afterNodeAccess()方法把访问的节点移到双向链表的末尾。

使用LinkedHashMap实现LRU缓存淘汰策略

public class LinkedHashMapLRU {
    public static void main(String[] args) {
        LRU<Integer,Integer> l = new LRU<>(0.75f,5);
        l.put(1,1);
        l.put(2,2);
        l.put(3,3);
        l.put(4,4);
        l.put(5,5);
        l.put(6,6);
        l.put(7,7);
        System.out.println(l.get(4));
        l.put(6,666);
        System.out.println(l);
    }
}

class LRU<K,V> extends LinkedHashMap<K,V>{
    private int capacity;

    public LRU( float loadFactor, int capacity) {
        super(capacity, loadFactor,true);
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > this.capacity;
    }
}

总结

LinkedHashMap 继承HashMap，拥有HashMap的所有特性
LinkedHashMap 除了拥有HashMap的数组+单链表+红黑树结构之外，还维护一个双向链表保证有序性
- 如果accessOrder为false，则可以按插入元素的顺序遍历元素
- 如果accessOrder为true，则可以按访问元素的顺序遍历元素
在HashMap中留的钩子（Hook），直接实现这些Hook就可以实现对应的功能了，并不需要再重写put()等方法
默认的LinkedHashMap并不会移除旧元素，如果需要移除旧元素，则需要重写removeEldestEntry()方法设定移除策略
LinkedHashMap可以用来实现LRU缓存淘汰策略

参考

死磕 java集合之LinkedHashMap源码分析

问题

简述