缓存淘汰–LRU算法

共计 2833 个字符，预计需要花费 8 分钟才能阅读完成。

计算机里通常讲的缓存就是指一片高速数据存储层，现在大部分系统的设计通常使用Memcache或Redis来作为缓存介质，缓解DB的负载压力。

举个简单的例子，当多个浏览器访问不同的页面时，会先从缓存层返回数据给浏览器，但是每天访问的页面不计其数，涉及到的数据很难估计。如果把所有数据都缓存下来，需要大量的存储介质。而缓存通常用的是比较昂贵的硬件，比如RAM。缓存的容量有限，但是数据是无限的，所以就需要只缓存热点数据或者符合实际业务制定的规则的这些数据。

LRU是什么？

LRU算法是一种缓存淘汰算法，淘汰缓存中不常用的数据，缓存有用的数据，使缓存效率最大化。LRU就是Least Recently Used的缩写，就是最近最少使用的意思，也就是LRU的淘汰规则。

LRU淘汰规则

LRU实质就是通过双向链表实现的

新数据加入，写加入到头结点
被访问的数据，会被移动到头结点
缓存达到最大容量，就会把尾结点淘汰，也就是淘汰最近最少访问的数据

LRU的实现

从上面的分析可以看出，LRU核心就两个功能，一个是存数据（put），一个是取数据（get）。

我们可以利用Python中自建的collections包中的OrderedDict，是一个有顺序的字典列表。来实现这个功能。在 Java 语言中，同样有类似的数据结构 LinkedHashMap。不过这种做法，是不会满足面试官的要求的，所以代码就不写了。

下面我们采用 哈希表+双端链表 的方式来实现，保证get 和 put 操作都以 O(1) 的时间复杂度运行。

LRU的缓存机制可以通过哈希表辅以双向链表实现，我们采用一个哈希表和一个双向链表维护所有在缓存中的键值对。

你可能会有个疑问，为什么要用双向链表，单向链表不行吗？

其实也是可以的，用双向链表，就不用在添加和删除链表时，检查相邻节点是否存在了。但是要设置伪头部和伪尾部。

双向链表：按照使用顺序存储键值对，靠近头部的键值对就是最近使用的，靠近尾部的就是最久未使用的。
哈希表：通过缓存数据的键映射到其在双向链表中的位置

这样一来，就可以先使用哈希表完成定位，找出缓存项在双向链表中的位置，随后将其移动到链表头部，即可完成O(1)时间内的 get 或 put 操作。

get 操作
- key 不存在，返回 -1
- key 存在，通过哈希表定位到该节点在双向链表中的位置，将其移动到头部，返回该节点的值
put 操作
- key 不存在，使用 key 和 value 创建一个新的节点，在链表头部添加节点，并将该节点加入到哈希表中。然后判断链表的节点数是否超出容量，超出，就删除链表尾部节点，并删除对应哈希表中对应的项
- key 存在，则与 get 操作类似，通过哈希表找到节点，更新节点的值，并将节点移动到链表头部

import java.util.HashMap;
import java.util.Map;
public class LRUCache {
    /* 双向链表 */
    class DlinkedNode {
        int key;
        Object value;
        DlinkedNode prev;
        DlinkedNode next;
        public DlinkedNode() {};
        public DlinkedNode(int key, Object value) {
            this.key = key;
            this.value = value;
        }
    }
    private Map<Integer, DlinkedNode> cache = new HashMap<Integer, DlinkedNode>();
    private int size;  // 链表长度
    private final int capacity;  // 容量
    private DlinkedNode head, tail;
    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.size = 0;
        // 初始化一个空的双向链表
        // 伪头结点
        head = new DlinkedNode();
        // 伪尾结点
        tail = new DlinkedNode();
        head.next = tail;
        tail.prev = head;
    }
    /* 
        @params key 查找的键
        @return key对应的值
    */
    public Object get(int key) {
        DlinkedNode node = cache.get(key);
        if (node == null) {
            return null;
        }
        // key 存在，通过哈希表定位，再移动到头部
        moveToHead(node);
        return node.value;
    }
    /* 
        key不存在，新建节点，往hashMap中添加节点，将该节点添加到链表头部，检查是否容量，超出，则删除尾部节点，并删除hashMap中对应项
        key存在，更新hashMap，将对应节点移动到头部
    */
    public void put(int key, Object value) {
        DlinkedNode node = cache.get(key);
        if (node == null) {
            DlinkedNode newNode = new DlinkedNode(key, value);
            cache.put(key, newNode);
            addToHead(newNode);
            ++size;
            if (size > capacity) {
                DlinkedNode tailNode = removeTail();
                cache.remove(tailNode.key);
                --size;
            }
        } else {
            node.value = value;
            moveToHead(node);
        }
    }
    /* 
        将节点添加到双向链表头部
        @params node: 节点
    */
    public void addToHead(DlinkedNode node) {
        // 1.将需要添加的节点node前后指针指向head和head.next
        node.prev = head;
        node.next = head.next;
        // 2.将head.next节点的prev指向node
        head.next.prev = node;
        // 3.将head节点的next指向node
        head.next = node;
    }
    /* 
        移除节点
    */
    public void removeNode(DlinkedNode node) {
        // 1.将node.prev节点的next指向node的下一节点
        node.prev.next = node.next;
        // 2.将node.next节点的prev指向node的上一节点
        node.next.prev = node.prev;
    }
    /* 
        移动到头结点（先删除，再添加）
    */
    public void moveToHead(DlinkedNode node) {
        removeNode(node);
        addToHead(node);
    }
    /* 
        删除尾节点
    */
    public DlinkedNode removeTail() {
        // tail是伪尾结点，需要删除tail的上一个节点
        DlinkedNode node = tail.prev;
        removeNode(node);
        return node;
    }
}

正文完