双向链表实现LRU缓存

前言

LRU，最近最久未使用算法，是操作系统里面一种页面调度算法，基于局部性原理。

假如当前内存的驻留集大小为2，已经放入了页面0，1，

$t_0$ 时刻放入页面0

$t_1$ 放入页面1

某个时刻( $t > t_1, t_0$)，OS需要将外存的页面2调入内存，那么需要选择一个页面置换出去。

LRU算法会选择最长时间未被访问的页面进行置换。

在以上例子中，页面0是最长时间没有被访问的，因此选择页面0进行置换。

置换后，内存中维持页面1和页面2

实现

来自@宫水三叶的刷题日记

思路

1. 将元素以键值对的形式存储，使用哈希表，保证插入和查询的时间复杂度为 $\Omicron(1)$

2. 使用一个双向链表来维持每个元素的访问顺序（优先级？）

• 一旦某个元素被访问（查询或者插入表中），将其优先级提到最高（放到链表头部）

• 当容量满，需要淘汰一个元素时，删除链表尾（优先级最低）的元素即可

  使用双向链表，主要保证移动元素到表头的时间复杂度为常数级的。

具体实现

元素形式:key-value键值对

• key作为哈希表的键

• value为双向链表的节点

插入

如果当前元素已经存在，则更新键值对，并将对应节点放到双向链表头部

如果当前元素不存在，检查容量是否足够：

• 如果容量足够，则插入新元素，并更新(将对应节点放到双向链表头)
• 如果容量不够，则将链表尾部元素删除，然后再插入当前元素，最后进行更新

查询

如果在哈希表中没有找到对应的key值，返回-1

如果存在，则返回相应的值，并将当前键值对对应的节点放到链表头部

---

代码

leetcode题目:146. LRU 缓存

public class LRUCache {
    class Node {
        int k, v;
        Node l, r;
        Node(int _k, int _v) {
            k = _k;
            v = _v;
        }
    }
    int n;
    Node head, tail;
    Map<Integer, Node> map;
    public LRUCache(int capacity) {
        n = capacity;
        map = new HashMap<>();
        head = new Node(-1, -1);
        tail = new Node(-1, -1);
        head.r = tail;
        tail.l = head;
    }

    public int get(int key) {
        if (map.containsKey(key)) {
            Node node = map.get(key);
            refresh(node);
            return node.v;
        }
        return -1;
    }

    public void put(int key, int value) {
        Node node = null;
        if (map.containsKey(key)) {
            node = map.get(key);
            node.v = value;
        } else {
            if (n == map.size()) {
                Node del = tail.l;
                map.remove(del.k);
                delete(del);
            }
            node = new Node(key, value);
            map.put(key, node);
        }
        refresh(node);
    }

    // refresh 操作分两步：
    // 1. 先将当前节点从双向链表中删除（如果该节点本身存在于双向链表中的话）
    // 2. 将当前节点添加到双向链表头部
    void refresh(Node node) {
        // 删除
        delete(node);
        // 插到头部
        node.r = head.r;
        head.r.l = node;
        node.l = head;
        head.r = node;

    }

    // delete 操作：将当前节点从双向链表中移除
    // 由于我们预先建立 head 和 tail 两位哨兵，因此如果 node.l 不为空，则代表了 node 本身存在于双向链表（不是新节点）
    void delete(Node node) {
        if (node.l != null) {
            node.r.l = node.l;
            node.l.r = node.r;
        }
    }

}

相关例题

432. 全 O(1) 的数据结构

class AllOne {
    class Node {
        int cnt;
        Set<String> set = new HashSet<>();
        Node l, r;
        Node(int _cnt) {
            cnt = _cnt;
        }
    }
    
    Node hh, tt;
    Map<String, Node> map = new HashMap<>();
    public AllOne() {
        hh = new Node(-1000); tt = new Node(-1000);
        hh.r = tt; tt.l = hh;
    }

    void clear(Node node) {
        // 删除set容量为0的节点
        if (node.set.size() == 0) {
            node.r.l = node.l;
            node.l.r = node.r;
        }
    }
    
    public void inc(String key) {
        // 添加
        if (map.containsKey(key)) {
            Node node = map.get(key);
            // 计数+1，当前cnt就要删去此key了
            node.set.remove(key);
            Node next = null;
            if (node.r.cnt == node.cnt + 1) {
                next = node.r;
            } else {
                next = new Node(node.cnt+1);
                next.r = node.r;
                node.r.l = next;
                next.l = node;
                node.r = next;
            }
            next.set.add(key);
            map.put(key, next);
            // 如果当前node的set容量为0，就clear
            clear(node);
        } else {
            Node node = null;
            if (hh.r.cnt != 1) {
                // 如果不存在cnt=1的节点则新建一个并且插入链表
                node = new Node(1);
                node.r = hh.r;
                node.l = hh;
                hh.r.l = node;
                hh.r = node;
            } else {
                node = hh.r;
            }
            node.set.add(key);
            map.put(key, node);
        }
    }
    
    public void dec(String key) {
        // 删除
        // 测试用例保证要删除的key-value存在
        Node node = map.get(key);
        node.set.remove(key);
        if (node.cnt == 1) map.remove(key);
        else {
            Node prev = null;
            if (node.l.cnt == node.cnt - 1) {
                prev = node.l;
            } else {
                prev = new Node(node.cnt - 1);
                prev.r = node;
                prev.l = node.l;
                node.l.r = prev;
                node.l = prev;
            }
            prev.set.add(key);
            map.put(key, prev);
        }
        clear(node);
    }
    
    public String getMaxKey() {
        Node node = tt.l;
        for (String str : node.set) return str;
        return "";
    }
    
    public String getMinKey() {
        Node node = hh.r;
        for (String str : node.set) return str;
        return "";
    }
}

添加的时候，一定要记得在map里面添加对应元素。

---

📔博文图谱

提及本博文的链接

• 基于双向链表的一些数据结构设计问题