欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

LRU的理解与Java实现

程序员文章站 2022-10-18 13:07:28
简介 LRU(Least Recently Used)直译为“最近最少使用”。其实很多老外发明的词直译过来对于我们来说并不是特别好理解,甚至有些词并不在国人的思维模式之内,比如快速排序中的Pivot,模拟信号中的Analog 等等。笔者认为最好的理解方式就是看他诞生的原因,看这个概念的出现如何一步一 ......

简介

lru(least recently used)直译为“最近最少使用”。其实很多老外发明的词直译过来对于我们来说并不是特别好理解,甚至有些词并不在国人的思维模式之内,比如快速排序中的pivot,模拟信号中的analog 等等。笔者认为最好的理解方式就是看他诞生的原因,看这个概念的出现如何一步一步演变为现在的样子。假如说你自己对某个问题想到了一个解决办法,于是你按照语义给他起了个名字,假如你直接将这个词儿说给别人,不知道这个词儿来历的人大概很难理解。所以为了力求方便理解,下面我们先来看看lru是什么,主要是为了解决什么问题。

其实lru这个概念映射到现实生活中非常好理解,就好比说小明的衣柜中有很多衣服,假设他的衣服都只能放在这个柜子里,小明每过一阵子小明就会买新衣服,不久小明的衣柜就放满了衣服。这个小明想了个办法,按照衣服上次穿的时间排序,丢掉最长时间没有穿过那个。这就是lru策略。

映射到计算机概念中,上述例子中小明的衣柜就是内存,而小明的衣服就是缓存数据。我们的内存是有限的。所以当缓存数据在内存越来越多,以至于无法存放即将到来的新缓存数据时,就必须扔掉最不常用的缓存数据。所以对于lru的抽象总结如下:

  • 缓存的容量是有限的
  • 当缓存容量不足以存放需要缓存的新数据时,必须丢掉最不常用的缓存数据

实现

理解了lru的原理之后,想要将其转换为代码并不是一件很困难的事。我们访问缓存通常使用一个字符串来定位缓存数据(事实上其他数据形式也没有关系),这种场景我们反射性的想到hashmap。所以我们先来简单的定义一下lrucachce类。

public class lrucache {
    private hashmap<string, object> map;
    private int capacity;
    public object get(string key) {
        return map.get(key);
    }
    public void set(string key, object value) {
        this.map.put(key, value);
    }
    public lrucache(int capacity) {
        this.capacity = capacity;
        this.map = new hashmap<string, object>();
    }
}

这样我们仅仅是定义了一个容量有限的lrucache,可以存取数据,但并没有实现缓存容量不足时丢弃最不常用的数据的功能,而这件事做起来似乎显得稍微麻烦一些,问题在于我们如何找到最久没有用的缓存。

一个最容易想到的办法是我们在给这个缓存数据加一个时间戳,每次get缓存时就更新时间戳,这样找到最久没有用的缓存数据问题就能够解决,但与之而来的会有两个新问题:

  • 虽然使用时间戳可以找到最久没用的数据,但我们最少的代价也要将这些缓存数据遍历一遍,除非我们维持一个按照时间戳排好序的sortedlist。
  • 添加时间戳的方式为我们的数据带来了麻烦,我们并不太好在缓存数据中添加时间戳的标识,这可能需要引入新的包含时间戳的包装对象。

而且我们的需要只是找到最久没用使用的缓存数据,并不需要精确的时间。添加时间戳的方式显然没有利用这一特性,这就使得这个办法从逻辑上来讲可能不是最好的。

然而办法总是有的,我们可以维护一个链表,当数据每一次查询就将数据放到链表的head,当有新数据添加时也放到head上。这样链表的tail就是最久没用使用的缓存数据,每次容量不足的时候就可以删除tail,并将前一个元素设置为tail,显然这是一个双向链表结构,因此我们定义lrunode如下:

class lrunode {
    string key;
    object value;
    lrunode prev;
    lrunode next;
    public lrunode(string key, object value) {
        this.key = key;
        this.value = value;
    }
}

而lrucache的简单实现最终如下:

public class lrucache {
    private hashmap<string, lrunode> map;
    private int capacity;
    private lrunode head;
    private lrunode tail;
    public void set(string key, object value) {
        lrunode node = map.get(key);
        if (node != null) {
            node = map.get(key);
            node.value = value;
            remove(node, false);
        } else {
            node = new lrunode(key, value);
            if (map.size() >= capacity) {
                // 每次容量不足时先删除最久未使用的元素
                remove(tail, true);
            }
            map.put(key, node);
        }
        // 将刚添加的元素设置为head
        sethead(node);
    }
    public object get(string key) {
        lrunode node = map.get(key);
        if (node != null) {
            // 将刚操作的元素放到head
            remove(node, false);
            sethead(node);
            return node.value;
        }
        return null;
    }
    private void sethead(lrunode node) {
        // 先从链表中删除该元素
        if (head != null) {
            node.next = head;
            head.prev = node;
        }
        head = node;
        if (tail == null) {
            tail = node;
        }
    }
    // 从链表中删除此node,此时要注意该node是head或者是tail的情形
    private void remove(lrunode node, boolean flag) {
        if (node.prev != null) {
            node.prev.next = node.next;
        } else {
            head = node.next;
        }
        if (node.next != null) {
            node.next.prev = node.prev;
        } else {
            tail = node.prev;
        }
        node.next = null;
        node.prev = null;
        if (flag) {
            map.remove(node.key);
        }
    }
    public lrucache(int capacity) {
        this.capacity = capacity;
        this.map = new hashmap<string, lrunode>();
    }
}