Java LinkedHashMap 和 LRU算法

问题：使用Java完成一个简单的LRU算法

什么是LRU算法

LRU（Least Recently Used），也就是最近最少使用。一种有限的空间资源管理的解决方案，会在空间资源不足的情况下移除掉最近没被使用过的数据，以保证接下来需要的空间资源。

在现在通用的操作系统中为了解决内存不足这个问题，提出了虚拟内存这种解决方案，其实虚拟内存也就是将机器的内存分为多个页面（提个小问题，一个页面包含了多少kb的空间？），内存中只存放当前需要的页面信息，暂时不使用的内存数据就保存到磁盘中。这可以很好的解决内存不足的问题。当然了这就无故出现页面交换的情况，使得读取内存的速度降低（磁盘的读取速度远小于内存的读取速度），这种方案肯定有利有弊，只需要我们的服务能够接受这种情况，那就完全没有问题。

Redis做为一种内存数据库，内存大小对数据库的影响更重要，所以redis也需要及时的移除掉那些过期数据。在redis中有定时清楚、惰性删除、定期删除，但是其策略主要分为两种，基于访问时间和基于访问频率。基于访问时间就是LRU算法，看看LRU算法的图解过程，如下图。

image.png

先定义好一个定长的队列
按照FIFO的流程，依次申请一段空间
直到队列被占满了，出现内存不足的情况，淘汰策略开始工作
会淘汰队列中最先进入的数据，最先进去的数据也就是最近最久未被使用的数据，然后把其移除出队列

LRU 算法小demo

整体的算法实现没有太多的难度，维护一个有限长度的队列的进出，需要移除或者插入数据。时间复杂度可能会是个问题。

队列如果是链表，则移除数据的时间复杂度是O(1)，但是查找数据的时间复杂度是O(n)
队列如果是数组，则移除数据的时间复杂度是O(n)，而且移除数据还伴随着数组的平行移动，查找数据也是O(n)，除非另外再加一个Map存储其索引值会使得其查找的速度降低到O（1），但是却又提高了空间复杂度

接下来写个基于数组的LRU的简单代码

public class LruDemo<T> {

    private Object[] items;

    private HashMap<T, Integer> map;

    private int size;

    private int index;

    public LruDemo() {
        this(8);
    }

    public LruDemo(int size) {
        this.size = size;
        this.items = new Object[size];
        this.map = new HashMap<>(16);
        this.index = 0;
    }

    public void put(T t) {
        Integer value = map.get(t);
        if (value == null) {
            if (index >= size) {
                // 满了，需要移除第一个元素
                for(int i=1; i<size;i++) {
                    items[i-1] = items[i];
                    map.replace((T)items[i-1], i);
                }
                index -= 1;
            }
            items[index] = t;
            map.put(t, index);
            index += 1;
        } else {
            for(int i=value; i<index; i++) {
                items[i] = items[i+1];
                map.replace((T)items[i], i);
            }
            items[index-1] = t;
            map.replace(t, index-1);
        }
    }

    public void getAll() {
        for(int i=0;i<index; i++) {
            System.out.println(items[i]);
        }
        System.out.println("======");
    }

    public static void main(String[] args) {
        LruDemo<String> lruDemo = new LruDemo<String>(6);
        lruDemo.put("aliace");
        lruDemo.put("bob");
        lruDemo.put("cat");
        lruDemo.put("dog");
        lruDemo.put("egg");
        lruDemo.getAll();
        lruDemo.put("bob");
        lruDemo.getAll();
        lruDemo.put("fine");
        lruDemo.put("good");
        lruDemo.getAll();
    }
}

输出的结果是

aliace
bob
cat
dog
egg
======
aliace
cat
dog
egg
bob
======
cat
dog
egg
bob
fine
good
======

这只是一种简单的写法，而且效率也比较低，现在就来介绍下将要学习的LinkedHashMap

LinkedHashMap

LinkedHashMap是继承自HashMap的，只是另外添加了排序相关的功能，使得其成为了有序hashmap，关于HashMap的介绍可以看看Java8的HashMap原理学习，接下来重点关注LinkedHashMap相比HashMap拓展了哪些功能呢？

Entry节点信息

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);
    }
}

头尾节点

transient LinkedHashMap.Entry<K,V> head;

transient LinkedHashMap.Entry<K,V> tail;

Entry节点就包含了前置节点和后置节点的地址信息，再加上在LinkedHashMap又中添加了head和tail头尾节点，这样就使得之前的链表+数据的数据结构基础上又加上了双向链表，通过双向链表实现有序性，并且 LinkedHashMap = Linked + HashMap。

accessOrder 值

final boolean accessOrder; 是一个非常关键的字段值，暂时按下不表，接下来会知道其真正的含义

get操作

HashMap进行get操作还是很简单的，通过hash获取index，再可能涉及到链表（红黑树）的遍历操作，在LinkedHashMap中同样重写了相关方法

public V get(Object key) {
    Node<K,V> e;
    if ((e = getNode(hash(key), key)) == null)
        return null;
    if (accessOrder)
        afterNodeAccess(e);
    return e.value;
}

进行常规的getNode操作后在找到对应的节点e之后，当accessOrder是true时，调用afterNodeAccess方法，从其名称也可以看出来时访问节点后的操作。

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;
        // b 和 a 分别是访问的节点e的前置和后置节点
        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;
    }
}

也就是说当accessOrder为true时，会修改其双向链表的节点顺序，而且搜索整个类也会发现accessOrder只在这里发挥用处。顺带观察下其key、value、entry的迭代器遍历情况，可以发现都是使用了for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after) 这种条件去循环遍历。

所以accessOrder就是起到控制访问顺序的作用，设置为true之后每访问一个元素，就将该元素移动到双向链表的尾部节点，通过改变节点在双向链表的位置实现对链表顺序的控制。

put 操作

在HashMap中通过put方法插入一个新的节点数据，LinkedHashMap并没有重写该方法。在HashMap中先检查是否存在对应的key，如果不存在则会通过newNode方法创建一个新节点，然后等待插入到合适的位置，LinkedHashMap则重写了newNode方法，如下代码块：

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;
    }
}

创建完一个LinkedHashMap.Entry节点p后，p节点的before, after都是null，然后调用linkNodeLast方法，采取尾插法，形成新的尾节点（这里有一种情况是最早的时候tail==head==null的情况，会使得头节点和尾节点都指向同一个节点）。

新插入一个节点后还会调用afterNodeInsertion方法，看起方法名称也知道是在node节点插入后的操作，在HashMap中是空实现，在LinkedHashMap则实现了该方法，如下代码块：

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);
    }
}
    
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    return false;
}

默认传入的evict值是true，而removeEldestEntry方法默认返回false，也就是什么都不做。当在put一个已经存在的节点的情况，会调用afterNodeAccess方法，也会去改变在链表中的位置。重写removeEldestEntry方法并且当起返回true时，调用removeNode节点移除head节点。这个就包含了LRU最近最少使用的实现原理。

自定义LRU算法

设置accessOrder为true后，每次访问、新增的节点都会移动到尾部，当removeEldestEntry返回true时就会移除头节点，那么只需要设置一种特定的判断逻辑使得removeEldestEntry返回true就可以了。按照上面LRU算法的思想，只有当空间满了的情况下才会移除头节点数据，同理只需要判断当前map中的节点数是否达到相关的阈值即可。继承LinkedHashMap重载removeEldestEntry方法，代码如下：

public class LruMap<K,V> extends LinkedHashMap<K, V> {

    private int maxSize;

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

    public LruMap(int maxSize) {
        this(16, 0.75f, true, maxSize);
    }

    public LruMap(int tableSize, int maxSize) {
        this(tableSize, 0.75f, true, maxSize);
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        boolean flag = size() > maxSize;
        if (flag) {
            System.out.println("移除头节点, key:" + eldest.getKey() + ", value:" + eldest.getValue());
        }
        return flag;
    }

    public static void main(String[] args) {
        LruMap<Integer, String> lruMap = new LruMap<>(4, 4);

        lruMap.put(1, "aaaa");
        lruMap.put(2, "bbbb");
        lruMap.put(3, "cccc");
        lruMap.put(4, "dddd");
        lruMap.put(5, "eeee");

        lruMap.entrySet().forEach(node -> {
            System.out.println("key:" + node.getKey() + ", value:" + node.getValue());
        });
    }
}

运行结果如下图，测试了table大小时4个，当插入了1～4 4个节点后，再插入5这个节点时，会移除头节点也就是节点1，从输出的日志也很清楚了。

image

如果利用get方法改变一下双向链表的顺序，可以控制移除的节点，修改一下测试数据，如下代码块

lruMap.put(1, "aaaa");
lruMap.put(2, "bbbb");
lruMap.put(3, "cccc");
lruMap.get(1);
lruMap.get(2);
lruMap.put(4, "dddd");
lruMap.put(5, "eeee");

这时候访问节点1和2，就会使得1和2移动到双向链表的尾部，头节点就是节点3，所以移除的头节点肯定是节点3，如下图符合我们的设想。