(资料图)

Least Recently Used(LRU) 是缓存淘汰一种常用的策略，内存满了则优先删除最久没被使用的数据。

LRU 算法的需求

1. 接收一个参数 capacity作为缓存的最大容量
2. 实现一个函数 put()添加数据到缓存
3. 实现一个函数 get()查询缓存中的数据
4. 以上函数应该在 \(O(1)\) 的时间内完成

满足以上需求的数据结构 —— 哈希表 + 双向链表，通过哈希表快速定位到链表中的节点，然后完成添加、删除等操作。

LRU 算法的实现

节点定义

public class Node {    public int key;    public String data;    public Node next;    public Node prev;        public Node(int key, String data) {        this.key = key;        this.value = value;        this.next = null;        this.prev = null;    }}

双向链表

public class MyLinkedList {    private Node head;    // 头节点    private Node tail;    // 尾节点    private int size;        public MyLinkedList() {        this.head = new Node(-1, "head");        this.tail = new Node(-1, "tail");                head.next = tail;        tail.prev = head;                this.size = 0;    }         // 添加新的数据到缓存     public void addLast(Node node) {         node.prev = tail.prev;         node.next = tail;         tail.prev.next = node;         tail.prev = node;                  this.size += 1;     }        // 删除缓存中的某项数据    public void remove(Node node) {        node.prev.next = node.next;        node.next.prev = node.prev;                this.size -= 1;    }        // 缓存空间已满，删除最早未被使用的数据    public Node removeFirst() {        if (head.next == tail) {            return null;        }                Node first = head.next;        remove(first);                return first;    }         public int size() {        return this.size;    }}

LRU Cache

目前使用的双向链表支持从尾部插入，即尾部为最新的数据，头部则是最久未被使用的数据。

public class LRUCache {    private Map map;    private MyLinkedList cache;    private int capacity;        public LRUCache(int capacity) {        this.map = new HashMap<>();        this.cache = new MyLinkedList();        this.capacity = capacity;    }        public String get(int key) {        if (!map.containsKey(key)) {            return null;        }                makeRecently(key);        return map.get(key).data;    }        /**     * 1. 判断 key 是否已存在于缓存，若已存在则更新对应的data，并设置为最新使用即添加到队尾     * 2. 判断缓存空间是否已满，若已满则删除最久未使用的数据     */    public void put(int key, String data) {        if (map.containsKey(key)) {            deleteKey(key);            addRecently(key, data);            return;        }                // 缓存空间已满        if (this.capacity == cache.size()) {            removeLeastRecently();        }                addRecently(key, data);    }        private void addRecently(int key, String data) {        Node node = new Node(key, data);        cache.addLast(node);        map.put(key, node);    }        private void makeRecently(int key) {        Node node = map.get(key);        cache.remove(node);        cache.addLast(node);    }        private void deleteKey(int key) {        Node node = map.get(key);        cache.remove(node);        map.remove(key);    }        /**     * 删除最久未被使用的数据     */    private void removeLeastRecently() {        Node node = cache.removeFirst();        map.remove(node.key);    }}

标签：