头条面试题：如何实现 LRU 原理？

点击上方 蓝字 关注我们

下面开始今天的学习～

LRU 原理作为操作系统课程中的一个重要部分在很多地方会被考到（比如操作系统课的考试或者一些公司的面试题）。

LRU 算法的设计原则是：如果一个数据在最近一段时间没有被访问到，那么在将来它被访问的可能性也很小。也就是说，当限定的空间已存满数据时，应当把最久没有被访问到的数据淘汰。

这个算法的出发点在于：如果某个页面被访问了，则它可能马上还要访问。反之，如果很长时间未被访问，则它在最近一段时间也不会被访问。

该算法的性能接近于最佳算法，但实现起来较困难。因为要找出最近最久未使用的页面，必须为每一页设置相关记录项，用于记录页面的访问情况，并且每访问一次页面都须更新该信息。这将使系统的开销加大，所以在实际系统中往往使用该算法的近似算法。

对于考试题目而言，由于一般是卷面考试，所以我们通常需要完成的是在纸上描绘出 LRU 的置换原理，一般题目如下：

最近最久未使用算法例

假定系统为某进程分配了 3 个物理块，进程运行时的页面走向为 1，2，3，4，1，2，5，1，2，3，4，5，开始时 3 个物理块均为空，计算采用   最近最久未使用页面淘汰算法时的缺页率  ？（10/12）

对于面试而言，可能就不仅仅是「明白概念」+「画出示例」那么简单了，可能还需要自己动手去实现一个 LRU 算法的小 Demo。

146.LRU缓存机制

在力扣上有这么一道题：

并且给出了提示——在 O(1) 时间复杂度内完成 get 和 put 操作。

一个比较通用的做法是通过 Hashmap + Double Linked List 来完成，图示如下：

这样，整个数据的操作过程如下：

实现算法代码如下：

Redis

Redis LRU algorithm is not an exact implementation. This means that Redis is not able to pick the best candidate for eviction, that is, the access that was accessed the most in the past. Instead it will try to run an approximation of the LRU algorithm, by sampling a small number of keys, and evicting the one that is the best (with the oldest access time) among the sampled keys.

Redis 是一个著名的键值对数据库，在   Using Redis as an LRU cache   中我 们知道 Redis 可以用来做为 LRU 缓存（虽然不是一个非常标准的实现，因为 Redis 可能无法选出最佳换出项），Redis 的方法是随机取出若干个 key，然后按照访问时间 排序 后，淘汰掉最不经常使用的页面，一个较为详尽的分析在参考资料中已经有所提及，建议有兴趣的读者参考。

参考资料

1. LRU原理和Redis实现——一个今日头条的面试题

2.LeetCode 算法题解——LRU 缓存机制

本文作者：Nova Kwok

编辑&版式：霍霍

声明：本文归 “力扣” 版权所有，如需转载请联系。

推荐阅读