LRU算法原理及实现，最近最少使用算法

发布于：2025-07-06 ⋅ 阅读:(15) ⋅ 点赞:(0)

LRU算法原理及实现，最近最少使用算法

1 介绍背景

LRU是Least Recently Used的缩写，即最近最少使用页面置换算法，是为虚拟页式存储管理服务的，是根据页面调入内存后的使用情况进行决策了。由于无法预测各页面将来的使用情况，只能利用“最近的过去”作为“最近的将来”的近似，因此，LRU算法就是将最近最久未使用的页面予以淘汰。

在内存不够的场景下，淘汰旧内容的策略。LRU … Least Recent Used，淘汰掉最不经常使用的。计算机体系结构中，最大的最可靠的存储是硬盘，它容量很大，并且内容可以固化，但是访问速度很慢，所以需要把使用的内容载入内存中；内存速度很快，但是容量有限，并且断电后内容会丢失，并且为了进一步提升性能，还有CPU内部的 L1 Cache，L2 Cache等概念。因为速度越快的地方，它的单位成本越高，容量越小，新的内容不断被载入，旧的内容肯定要被淘汰，所以就有这样的使用背景。

2 LRU 原理

一般来讲，LRU将访问数据的顺序或时间和数据本身维护在一个容器当中。当访问一个数据时：

  • 该数据不在容器当中，则设置该数据的优先级为最高并放入容器中。
  • 该数据在容器当中，则更新该数据的优先级至最高。

当数据的总量达到上限后，则移除容器中优先级最低的数据。下图是一个简单的LRU原理示意图：

在这里插入图片描述

如果我们按照 7 0 1 2 0 3 0 4 的顺序来访问数据，且数据的总量上限为3，则如上图所示，LRU算法会依次淘汰 7 1 2 这三个数据。

3 最简单的LRU算法

那么我们现在就按照上面的原理，实现一个朴素的LRU算法。下面有三种方案：

方案一 基于数组

方案：为每一个数据附加一个额外的属性——时间戳，当每一次访问数据时，更新该数据的时间戳至当前时间。当数据空间已满后，则扫描整个数组，淘汰时间戳最小的数据。

不足：维护时间戳需要耗费额外的空间，淘汰数据时需要扫描整个数组。

方案二 基于长度有限的双向链表

方案：访问一个数据时，当数据不在链表中，则将数据插入至链表头部，如果在链表中，则将该数据移至链表头部。当数据空间已满后，则淘汰链表最末尾的数据。

不足：插入数据或取数据时，需要扫描整个链表。

方案三 基于双向链表和哈希表

方案：为了改进上面需要扫描链表的缺陷，配合哈希表，将数据和链表中的节点形成映射，将插入操作和读取操作的时间复杂度从O(N)降至O(1)

4 基于双向链表 + 哈希表实现LRU

整体的设计思路是，可以使用 HashMap 存储 key，这样可以做到 save 和 get key的时间都是 O(1)，而 HashMap 的 Value 指向双向链表实现的 LRU 的 Node 节点，如图所示。

在这里插入图片描述

/**
 *双向链表节点
 */
public class DoubleQueueNode {
    String key;
    String val;
    DoubleQueueNode pre;
    DoubleQueueNode next;

    public DoubleQueueNode(String key, String val) {
        this.key = key;
        this.val = val;
    }

    @Override
    public String toString() {
        return "{" +
                "val='" + val + '\'' +
                '}';
    }
}

public class LRUCache {

/**
 * 当前容量
 */
private int size;
/**
 * 限制大小
 */
private int capacity;
/**
 * 数据和链表中节点的映射
 */
private Map<String, DoubleQueueNode> map;
/**
 * 头结点 避免null检查
 */
private DoubleQueueNode head;
/**
 * 尾结点 避免null检查
 */
private DoubleQueueNode tail;

public LRUCache(int capacity) {
    this.capacity = capacity;
    this.map = new HashMap<>(capacity);
    this.head = new DoubleQueueNode(null, null);
    this.tail = new DoubleQueueNode(null, null);
    this.head.next = tail;
}

public String get(String key) {

    DoubleQueueNode node = map.get(key);
    if (node == null) {
        return null;
    }

    // 数据在链表中，则移至链表头部
    moveToHead(node);

    return node.val;
}

public String put(String key, String value) {

    String oldValue;
    DoubleQueueNode node = map.get(key);
    if (node == null) {
        // 淘汰数据
        eliminate();
        // 数据不在链表中，插入数据至头部
        DoubleQueueNode newNode = new DoubleQueueNode(key, value);
        DoubleQueueNode temp = head.next;
        head.next = newNode;
        newNode.next = temp;
        newNode.pre = head;
        temp.pre = newNode;
        map.put(key, newNode);
        size++;
        oldValue = null;
    } else {
        // 数据在链表中，则移至链表头部
        moveToHead(node);
        oldValue = node.val;
        node.val = value;
    }
    return oldValue;
}

public String remove(Integer key) {
    DoubleQueueNode deletedNode = map.get(key);
    if (deletedNode == null) {
        return null;
    }
    deletedNode.pre.next = deletedNode.next;
    deletedNode.next.pre = deletedNode.pre;
    map.remove(key);
    return deletedNode.val;
}

/**
 * 将节点插入至头部节点
 * @param node
 */
private void moveToHead(DoubleQueueNode node) {
    node.pre.next = node.next;
    node.next.pre = node.pre;
    DoubleQueueNode temp = head.next;
    head.next = node;
    node.next = temp;
    node.pre = head;
    temp.pre = node;
}

private void eliminate() {
    if (size < capacity) {
        return;
    }

    // 将链表中最后一个节点去除
    DoubleQueueNode last = tail.pre;
    map.remove(last.key);
    last.pre.next = tail;
    tail.pre = last.pre;
    size--;
    last = null;
}

public List<DoubleQueueNode> getAll(){
    List<DoubleQueueNode> list = new ArrayList<>();

    DoubleQueueNode tmp = this.head;
    while (tmp != null) {
        list.add(tmp);
        tmp = tmp.next;

    }
    return list;
}
}

利用单元测试插入并输出查看，测试程序如下：

@Test
public void testSave(){
    LRUCache lruCache = new LRUCache(5);

    System.out.println("初始输出：");
    System.out.println(lruCache.getAll());

    lruCache.put("key1", "val1");
    lruCache.put("key2", "val2");
    lruCache.put("key3", "val3");
    lruCache.put("key4", "val4");
    lruCache.get("key2");
    System.out.println("容量未满输出：");
    System.out.println(lruCache.getAll());
    lruCache.put("key5", "val5");
    System.out.println("过程中输出：");
    System.out.println(lruCache.getAll());
    lruCache.put("key6", "val6");
    lruCache.put("key7", "val7");
    lruCache.get("key2");
    lruCache.put("key8", "val8");

    System.out.println("结果输出：");
    System.out.println(lruCache.getAll());
}

结果输出如下：

初始输出：
[{val='null'}, {val='null'}]
容量未满输出：
[{val='null'}, {val='val2'}, {val='val4'}, {val='val3'}, {val='val1'}, {val='null'}]
过程中输出：
[{val='null'}, {val='val5'}, {val='val2'}, {val='val4'}, {val='val3'}, {val='val1'}, {val='null'}]
结果输出：
[{val='null'}, {val='val8'}, {val='val2'}, {val='val7'}, {val='val6'}, {val='val5'}, {val='null'}]

总结一下操作的步骤:

  1. save(key, value)，首先在 HashMap 找到 Key 对应的节点，如果节点存在，更新节点的值，并把这个节点移动队头。如果不存在，需要构造新的节点，并且尝试把节点塞到队头，如果LRU空间不足，则通过 tail 淘汰掉队尾的节点，同时在 HashMap 中移除 Key。
  2. get(key)，通过 HashMap 找到 LRU 链表节点，把节点插入到队头，返回缓存的值。

5 基于LinkedHashMap实现的LRU

其实我们可以直接根据JDK给我们提供的LinkedHashMap直接实现LRU。因为LinkedHashMap的底层即为双向链表和哈希表的组合，所以可以直接拿来使用。

public class LRUCache extends LinkedHashMap {

    private int capacity;

    public LRUCache(int capacity) {
        // 注意这里将LinkedHashMap的accessOrder设为true
        super(16, 0.75f, true);
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry eldest) {
        return super.size() >= capacity;
    }
}

默认LinkedHashMap并不会淘汰数据，所以我们重写了它的removeEldestEntry()方法，当数据数量达到预设上限后，淘汰数据，accessOrder设为true意为按照访问的顺序排序。整个实现的代码量并不大，主要都是应用LinkedHashMap的特性。
正因为LinkedHashMap这么好用，所以我们可以看到Dubbo的LRU缓存LRUCache也是基于它实现的。

6 LRU算法优化

朴素的LRU算法已经能够满足缓存的要求了，但是还是有一些不足。当热点数据较多时，有较高的命中率，但是如果有偶发性的批量操作，会使得热点数据被非热点数据挤出容器，使得缓存受到了“污染”。所以为了消除这种影响，又衍生出了下面这些优化方法。

7 LRU-K

LRU-K算法是对LRU算法的改进，将原先进入缓存队列的评判标准从访问一次改为访问K次，可以说朴素的LRU算法为LRU-1。

LRU-K算法有两个队列，一个是缓存队列，一个是数据访问历史队列。当访问一个数据时，首先先在访问历史队列中累加访问次数，当历史访问记录超过K次后，才将数据缓存至缓存队列，从而避免缓存队列被污染。同时访问历史队列中的数据可以按照LRU的规则进行淘汰。具体如下图所示：

在这里插入图片描述

// 直接继承我们前面写好的LRUCache
public class LRUKCache extends LRUCache {
    
    private int k; // 进入缓存队列的评判标准
    private LRUCache historyList; // 访问数据历史记录

    public LRUKCache(int cacheSize, int historyCapacity, int k) {
        super(cacheSize);
        this.k = k;
        this.historyList = new LRUCache(historyCapacity);
    }

    @Override
    public Integer get(Integer key) {

        // 记录数据访问次数
        Integer historyCount = historyList.get(key);
        historyCount = historyCount == null ? 0 : historyCount;
        historyList.put(key, ++historyCount);

        return super.get(key);
    }

    @Override
    public Integer put(Integer key, Integer value) {

        if (value == null) {
            return null;
        }
        
        // 如果已经在缓存里则直接返回缓存中的数据
        if (super.get(key) != null) {
            return super.put(key, value);;
        }

        // 如果数据历史访问次数达到上限，则加入缓存
        Integer historyCount = historyList.get(key);
        historyCount = historyCount == null ? 0 : historyCount;
        if (historyCount >= k) {
            // 移除历史访问记录
            historyList.remove(key);
            return super.put(key, value);
        }
    }
}

上面只是个简单的模型，并没有加上必要的并发控制。

一般来讲，当K的值越大，则缓存的命中率越高，但是也会使得缓存难以被淘汰。综合来说，使用LRU-2的性能最优。

8 Two Queue

Two Queue可以说是LRU-2的一种变种，将数据访问历史改为FIFO队列。好处的明显的，FIFO更简易，耗用资源更少，但是相比LRU-2会降低缓存命中率。

在这里插入图片描述

// 直接继承LinkedHashMap
public class TwoQueueCache extends LinkedHashMap<Integer, Integer> {

    private int k; // 进入缓存队列的评判标准
    private int historyCapacity; // 访问数据历史记录最大大小
    private LRUCache lruCache; // 我们前面写好的LRUCache

    public TwoQueueCache(int cacheSize, int historyCapacity, int k) {
        // 注意这里设置LinkedHashMap的accessOrder为false
        super();
        this.historyCapacity = historyCapacity;
        this.k = k;
        this.lruCache = new LRUCache(cacheSize);
    }

    public Integer get(Integer key) {
        // 记录数据访问记录
        Integer historyCount = super.get(key);
        historyCount = historyCount == null ? 0 : historyCount;
        super.put(key, historyCount);
        return lruCache.get(key);
    }

    public Integer put(Integer key, Integer value) {

        if (value == null) {
            return null;
        }

        // 如果已经在缓存里则直接返回缓存中的数据
        if (lruCache.get(key) != null) {
            return lruCache.put(key, value);
        }

         // 如果数据历史访问次数达到上限，则加入缓存
        Integer historyCount = super.get(key);
        historyCount = historyCount == null ? 0 : historyCount;
        if (historyCount >= k) {
            // 移除历史访问记录
            super.remove(key);
            return lruCache.put(key, value);
        }

        return null;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry eldest) {
        return super.size() >= historyCapacity;
    }
}

这里直接继承LinkedHashMap，并且accessOrder默认为false，意为按照插入顺序进行排序，二者结合即为一个FIFO的队列。通过重写removeEldestEntry()方法来自动淘汰最早插入的数据。

9 Multi Queue

相比于上面两种优化，Multi Queue的实现则复杂的多，顾名思义，Multi Queue是由多个LRU队列组成的。每一个LRU队列都有一个相应的优先级，数据会根据访问次数计算出相应的优先级，并放在该队列中。

在这里插入图片描述

数据插入和访问

当数据首次插入时，会放入到优先级最低的Q0队列。当再次访问时，根据LRU的规则，会移至队列头部。当根据访问次数计算的优先级提升后，会将该数据移至更高优先级的队列的头部，并删除原队列的该数据。同样的，当该数据的优先级降低时，会移至低优先级的队列中。

数据淘汰

数据淘汰总是从最低优先级的队列的末尾数据进行，并将它加入到Q-history队列的头部。如果数据在Q-history数据中被访问，则重新计算该数据的优先级，并将它加入到相应优先级的队列中。否则就是按照LRU算法完全淘汰。

Multi Queue也可以看做是LRU-K的变种，将原来两个队列扩展为多个队列，好处就是无论是加入缓存还是淘汰缓存数据都变得更加细腻，但是会带来额外开销。

10 最后，文章参考

  • https://juejin.cn/post/6844904049263771662
  • https://blog.csdn.net/belongtocode/article/details/102989685

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布