江苏龙网

  1. 主页 > 生活百科 > >

LRU算法到底是怎么一回事？

LRU算法

LRU是Least Recently Used的缩写，即最近最少使用，是一种常用的页面置换算法，选择最近最久未使用的页面予以淘汰 。当限定的空间已存满数据时，应当把最久没有被访问到的数据淘汰 。
简单描述一下在《操作系统》这本书里面对于LRU算法的解说 。
假定系统为某进程分配了3个物理块，进程运行时的页面走向为 7 0 1 2 0 3 0 4，开始时3个物理块均为空，那么LRU 算法是如下工作的：
LRU算法到底是怎么一回事？

文章插图
 
这就是最基本的LRU的磁盘调度逻辑，该算法运用领域比较广泛比如redis的内存淘汰策略等等，该算法也是面试中面试官常常用来考验面试者代码能力和对LRU算法的正确理解 。
以下我主要以为双向链表+HashMap的方式手撕一个时间复杂度为O(1)的LRU算法 。
在JAVA中，其实LinkedHashMap已经实现了LRU缓存淘汰算法，需要在构造方法第三个参数传入true( accessOrder = true;)，表示按照时间顺序访问 。可以直接继承LinkedHashMap来实现 。
public class LRULinkedHashMap<K, V> extends LinkedHashMap<K, V> {    private int capacity;    LRULinkedHashMap(int capacity) {        //true是表示按照访问时间排序,        super(capacity, 0.75f, true);        //传入指定的缓存最大容量        this.capacity = capacity;    }    /**     * 实现LRU的关键方法，如果map里面的元素个数大于了缓存最大容量，则删除链表的顶端元素     */    @Override    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {        return size() > capacity;    }}算法设计思路
  • 访问某个节点时，将其从原来的位置删除，并重新插入到链表头部 。
  • 这样就能保证链表尾部存储的就是最近最久未使用的节点，当节点数量大于缓存最大空间时就淘汰链表尾部的节点 。
  • 为了使删除操作时间复杂度为 O(1)，就不能采用遍历的方式找到某个节点 。
  • HashMap 存储着 Key 到节点的映射，通过 Key 就能以 O(1) 的时间得到节点，然后再以 O(1) 的时间将其从双向队列中删除 。

LRU算法到底是怎么一回事？

文章插图
 
一.构建双向链表Node节点
    /**     * 定义双向链表其中K为Map中的K 降低查找时间复杂度     */    class Node {        K k;        V v;        Node pre;        Node next;        Node(K k, V v) {            this.k = k;            this.v = v;        }    }二.定义变量
//定义缓存大小private int size;// 存储K和Node节点的映射 Node中会存放KVprivate HashMap<K, Node> map;private Node head;private Node tail;三.初始化结构体
XLRUCache(int size) {    this.size = size;    map = new HashMap<>();}四.添加元素
/** * 添加元素 * 1.元素存在，将元素移动到队尾 * 2.不存在，判断链表是否满 。 * 如果满，则删除队首（head）元素，新元素放入队尾元素 * 如果不满，放入队尾（tail）元素 */public void put(K key, V value) {    Node node = map.get(key);    if (node != null) {        //更新值        node.v = value;        moveNodeToTail(node);    } else {        Node newNode = new Node(key, value);        //链表满，需要删除首节点        if (map.size() == size) {            Node delHead = removeHead();            map.remove(delHead.k);        }        addLast(newNode);        map.put(key, newNode);    }}


推荐阅读


上一篇：茶树菇骨头汤怎么做,看看茶树菇干锅怎么做

下一篇：冬瓜茶砖怎么煮,普洱茶砖怎么撬不碎