最新要闻

广告

手机

光庭信息跌4.57% 2021上市超募11亿2022扣非降74% 时快讯

光庭信息跌4.57% 2021上市超募11亿2022扣非降74% 时快讯

 搜狐汽车全球快讯 | 大众汽车最新专利曝光：仪表支持拆卸 可用手机、平板替代-环球关注

搜狐汽车全球快讯 | 大众汽车最新专利曝光：仪表支持拆卸 可用手机、平板替代-环球关注

家电

  1. 首页
  2. 移动通信
  3. 内容

LRU 缓存淘汰算法

来源：博客园


(相关资料图)

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

关键词：