LRU策略算法

妖狐艹你老母 2022-11-13 01:52 201阅读 0赞

缓存是一种提高数据读取性能的技术，在硬件设计、软件开发中都有着非常广泛的应用，比如常见的 CPU 缓存、数据库缓存、浏览器缓存等等。

缓存的大小有限，当缓存被用满时，哪些数据应该被清理出去，哪些数据应该被保留？这就需要缓存淘汰策略来决定。常见的策略有三种：先进先出策略 `FIFO（First In，First Out）`、最少使用策略 `LFU（Least Frequently Used）`、最近最少使用策略 `LRU（Least Recently Used）`，本篇将介绍LRU策略算法。

## LRU Cache ##

这一算法的核心思想是，当缓存数据达到预设的上限后，会优先淘汰掉近期最少使用的缓存对象。

### LinkedHashMap实现 ###

在LinkedHashMap中，有一个很少用到的构造函数：

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

其中`accessOrder`这一属性，在其他的构造函数中是默认为`false`的，如果我们通过该构造函数将其设为`true`之后，就实现了LRU功能，下面的程序简单了做了下演示：

public static void main(String[] args) {
    
            int cacheSize = 3;
            // 最大容量 = （缓存大小 / 负载因子）+ 1，保证不会触发自动扩容
            LinkedHashMap<String, String> cache = new LinkedHashMap<String, String>(
                    (int)(cacheSize/ 0.75f) + 1, 0.75f, true) {
                @Override
                protected boolean removeEldestEntry(Map.Entry eldest) {
                    return size() > cacheSize;
                }
            };
    
            cache.put("1", "a");
            cache.put("2", "b");
            cache.put("3", "c");
    
            // head => "1" => "2" => "3" => null
    
            // put已存在的值，和get方法是一样的效果
            cache.put("1", "a");
    
            // head => "2" => "3" => "1" => null;
    
            cache.put("4", "d");
    
            // head => "3" => "1" => "4" => null;
            
            for (String key: cache.keySet()) {
                System.out.println(key);
            }
        }
    复制代码

其实还有很重要的一点，就是需要重写`removeEldestEntry()`这一方法，默认是返回`false`的，当返回`true`时，会移除最久没有使用的节点，所以我们要做的，就是当容量达到缓存限制时，移除LRU算法判定的最近最久未使用节点

可以看到，我们依次插入节点1、2、3后，如果此时再插入节点4，就会导致`removeEldestEntry()`返回为`true`，然后移除队首节点，即节点1。但是我们这里由于中间重复插入了一次节点1，所以会判断节点1是“经常访问的节点”，所以节点1被提到链表最后，队首节点就变成了节点2，当容量超过限制时，会把节点2移除

**实现原理**

探索LinkedHashMap中LRU的实现原理，我们就要追溯到HashMap中的`putVal`方法，这个方法最后触发了一个回调函数：

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                       boolean evict) {
            // ...
            
                if (e != null) { // existing mapping for key
                    // ...
                    afterNodeAccess(e);
                    return oldValue;
                }
            }
            afterNodeInsertion(evict);
            return null;
        }
    复制代码

`putVal()`方法在插入后会触发方法的回调，有两种情况：

*  如果插入的值已存在，则触发`afterNodeAccess(e)`
 *  如果插入的值不存在，则触发`afterNodeInsertion(evict)`

其中，变量e是“撞车”的节点，变量evict在子类不重写`put()`方法的情况下是默认为`true`的，所以我们就把它当作常量来看

然后我们回到，LinkedHashMap中，来看这个两个钩子方法（HashMap中这两个方法实现均为空）：

void afterNodeInsertion(boolean evict) {
            LinkedHashMap.Entry<K,V> first;
            // 以下情况满足时，调用removeNode移除最久未使用的节点：
            //      1. evict为true
            //      2. 头结点不为空
            //      3. 符合移除条件：removeEldestEntry返回true
            if (evict && (first = head) != null && removeEldestEntry(first)) {
                K key = first.key;
                removeNode(hash(key), key, null, false, true);
            }
        }
    
        void afterNodeAccess(Node<K,V> e) {
            LinkedHashMap.Entry<K,V> last;
            // 开启LRU模式，且访问的节点不是尾节点，则将被访问的节点置于链表尾
            if (accessOrder && (last = tail) != e) {
                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;
            }
        }
    复制代码

显而易见，`afterNodeInsertion`负责在**插入**之后判断是否需要移除最近最久未使用的节点（即链表头节点），`afterNodeAccess`负责在**访问**某节点之后，将该节点移动到链表尾

在`afterNodeAccess`中，因为要考虑到各种特殊情况，而且是一个带有头尾节点的双向链表，所以情况判断比较复杂，实际上就是将指定节点移动到队尾，如果自己想实现一个类似的功能可以不做的这么复杂

### 自实现 ###

LRU淘汰算法涉及数据的添加与删除，出于性能考虑，采用链表来进行实现，思路如下：

*  维护一个双向链表用于存放缓存数据，越接近链表尾部的数据表示越少被使用到。
 *  放入一个数据时，如果数据已存在则将其移动到链表头部，并更新Key所对应的Value值，如果不存在，则：
    
     *  如果缓存容量已达到最大值，则将链表尾部节点删除掉，将新的数据放入链表头部；
     *  如果缓存容量未达到最大值，则直接将新的数据放入链表头部；
 *  查询一个数据时，遍历整个链表，如果能查询到对应的数据，则将其移动到链表头部；如果查询不到则返回`null`；
    
     *  由于遍历链表的时间复杂度为`O(n)`，我们可以使用散列表`HashMap`来记录每个Key所对应的Node节点，将时间复杂度降为O(1)。

![LRU-Cache][]

**代码**

package one.wangwei.algorithms.utils;
    
    
    import java.util.HashMap;
    import java.util.Map;
    
    /**
     * LRU Cache
     *
     * @author https://wangwei.one
     * @date 2019/01/29
     */
    public class LRUCache<K, V> {
    
        private int capacity;
        private Node head;
        private Node tail;
        private Map<K, Node> nodeMap;
    
        public LRUCache(int capacity) {
            this.capacity = capacity;
            this.nodeMap = new HashMap<>(capacity);
        }
    
        /**
         * Get Key
         *
         * @param key
         * @return
         */
        public V get(K key) {
            Node existNode = nodeMap.get(key);
            if (existNode == null) {
                return null;
            }
            remove(existNode);
            addFirst(existNode);
            return existNode.value;
        }
    
        /**
         * Add Key-Value
         *
         * @param key
         * @param value
         */
        public void put(K key, V value) {
            Node existNode = nodeMap.get(key);
            if (existNode == null) {
                Node newNode = new Node(key, value);
                if (nodeMap.size() >= capacity) {
                    removeLast();
                }
                addFirst(newNode);
            }
            else {
                // update the value
                existNode.value = value;
                remove(existNode);
                addFirst(existNode);
            }
        }
    
        /**
         * remove node
         *
         * @param node
         */
        private void remove(Node node) {
            Node prev = node.prev;
            Node next = node.next;
    
            if (prev == null) {
                head = next;
            } else {
                prev.next = next;
            }
            if (next == null) {
                tail = prev;
            } else {
                next.prev = prev;
            }
            nodeMap.remove(node.key);
        }
    
        /**
         * add first node
         *
         * @param node
         */
        private void addFirst(Node node) {
            node.prev = null;
            if (head == null) {
                head = tail = node;
            } else {
                node.next = head;
                head.prev = node;
                head = node;
            }
            nodeMap.put(node.key, node);
        }
    
        /**
         * remove last
         */
        private void removeLast() {
            if (tail == null) {
                return;
            }
            // remove key from map
            nodeMap.remove(tail.key);
            // remove node from linked list
            Node prev = tail.prev;
            if (prev != null) {
                prev.next = null;
                tail = prev;
            } else {
                head = tail = null;
            }
        }
    
        private class Node {
    
            private K key;
            private V value;
            private Node prev;
            private Node next;
    
            private Node(K key, V value) {
                this.key = key;
                this.value = value;
            }
        }
    }

[LRU-Cache]: /images/20221022/3c88569113a04766af5e0bac4465304f.png