LRU 与 LFU 页面置换算法对比及 Golang 实现

LRU 和 LFU 是两种常见的内存管理页面置换算法。LRU 基于最近使用时间淘汰最久未使用的页面，适合较大文件场景；LFU 基于使用频率淘汰最少访问的页面，适合小文件或系统文件。文章对比了两者区别，并提供了 Golang 语言下的完整数据结构设计与代码实现，涵盖缓存读写、容量管理及节点移动逻辑。

KernelLab发布于 2026/3/16更新于 2026/4/183 浏览

LRU 和 LFU 的区别

LRU 和 LFU 都是内存管理的页面置换算法。

LRU：最近最少使用 (最长时间) 淘汰算法（Least Recently Used）。LRU 是淘汰最长时间没有被使用的页面。

LFU：最不经常使用 (最少次) 淘汰算法（Least Frequently Used）。LFU 是淘汰一段时间内，使用次数最少的页面。

当需要使用页面 4 时，内存块中存储着 1、2、3，内存块中没有页面 4，就会发生缺页中断，而且此时内存块已满，需要进行页面置换。
若按 LRU 算法，应替换掉页面 1。因为页面 1 是最长时间没有被使用的了，页面 2 和 3 都在它后面被使用过。
若按 LFU 算法，应换页面 3。因为在这段时间内，页面 1 被访问了 2 次，页面 2 被访问了 3 次，而页面 3 只被访问了 1 次，一段时间内被访问的次数最少。
LRU 算法适合：较大的文件比如游戏客户端（最近加载的地图文件）;
LFU 算法适合：较小的文件和零碎的文件比如系统文件、应用程序文件 ;
LRU 消耗 CPU 资源较少，LFU 消耗 CPU 资源较多。

例子

假设 LFU 方法的时期 T 为 10 分钟，访问如下页面所花的时间正好为 10 分钟，内存块大小为 3。若所需页面顺序依次如下：

2 1 2 1 2 3 4

---------------------------------------->

**LRU 关键是看页面最后一次被使用到发生替换的时间长短，时间越长，页面就会被置换；

LFU 关键是看一定时间段内页面被使用的频率（次数），使用频率越低，页面就会被置换。**

LRU (最长时间)

最近最久未使用算法，LRU 是淘汰最长时间没有被使用的页面

功能

缓存容量 capacity 为正整数，缓存的 key、value 均为 int 类型
读缓存 func get(key int) int：
- key 已存在，返回对应 value
- key 不存在，返回 -1
写缓存 func put(key int, value int)：
- key 已存在，修改对应 value
- key 不存在，写入该组缓存，若写入前缓存容量已达上限，则应淘汰最久未使用的缓存（强调：读、写缓存均视为使用）

数据结构

使用双向链表维护缓存的上一次使用时间：约定：链表正方向（从头部到尾部）节点按照使用时间排序——越早使用（即久未使用）的节点，越靠近链表尾部维护：每使用一次缓存，就将该缓存对应的链表节点移动到链表头部；缓存淘汰时，只需要删除尾部节点即可增加一个 map，记录 key 到链表节点的映射关系; 解决如果只使用双向链表，每次判断 key 是否存在时，都要遍历链表

cache：map[int]*listNode，key 到节点的映射; 其中 listNode data：key, value
list：*listNode，双向链表，维护缓存的上一次使用时间
capacity：int，链表容量

伪代码

读缓存
1. key 存在：
  - 在原链表中删除该缓存节点，重新插入到链表头部,
  - 返回对应的 value
2. key 不存在:
  - 返回 -1
写缓存 (更新缓存)

相关免费在线工具

加密/解密文本

使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。在线工具，加密/解密文本在线工具，online

Base64 字符串编码/解码

将字符串编码和解码为其 Base64 格式表示形式即可。在线工具，Base64 字符串编码/解码在线工具，online

Base64 文件转换器

将字符串、文件或图像转换为其 Base64 表示形式。在线工具，Base64 文件转换器在线工具，online

Markdown转HTML

将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。在线工具，Markdown转HTML在线工具，online

HTML转Markdown

将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。在线工具，HTML转Markdown在线工具，online

JSON 压缩

通过删除不必要的空白来缩小和压缩JSON。在线工具，JSON 压缩在线工具，online

// 双向链表节点 type doublyListNode struct { key int value int prev *doublyListNode next *doublyListNode } // 构造一个双向空链表 (首尾几点都是空节点) func newDoublyList() *doublyListNode { headNode := &doublyListNode{} tailNode := &doublyListNode{} headNode.next = tailNode tailNode.prev = headNode return headNode } // 把节点添加到链表头部 func (dl *doublyListNode) addToHead(node *doublyListNode) { dl.next.prev = node node.next = dl.next dl.next = node node.prev = dl } // 删除链表中的节点 func removeNode(node *doublyListNode) { node.next.prev = node.prev node.prev.next = node.next } // LRUCache 具体的缓存 type LRUCache struct { cache map[int]*doublyListNode head *doublyListNode tail *doublyListNode capacity int } // Constructor 构建缓存容器 func Constructor(capacity int) LRUCache { dl := newDoublyList() return LRUCache{ cache: make(map[int]*doublyListNode), head: dl, tail: dl.next, capacity: capacity, } } func (lruCache *LRUCache) Get(key int) int { // 根据 key 获取缓存 v, ok := lruCache.cache[key] // 如果没有缓存，返回 -1 if !ok { return -1 } // 如果有缓存 removeNode(v) // 把缓存添加双向链表头部 lruCache.head.addToHead(v) return v.value } // Put 新建缓存 func (lruCache *LRUCache) Put(key int, value int) { // 已经有缓存 if v, ok := lruCache.cache[key]; ok { // v 是双链表中的节点 v.value = value // 更新链表节点中的值 lruCache.cache[key] = v // 更新缓存中映射关系 removeNode(v) // 移除该缓存 lruCache.head.addToHead(v) // 把缓存添加双向链表头部 return } // 缓存超长淘汰缓存 if len(lruCache.cache) >= lruCache.capacity { node := lruCache.tail.prev removeNode(node) // 删除该节点 delete(lruCache.cache, node.key) // 清除最近最少使用的缓存 } newNode := &doublyListNode{ key: key, value: value, } lruCache.cache[key] = newNode lruCache.head.addToHead(newNode) }

// 双向链表 type doublyList struct { head *doublyListNode tail *doublyListNode } // 删除尾结点 func (dl *doublyList) removeTail() { pre := dl.tail.prev.prev pre.next = dl.tail dl.tail.prev = pre } // 链表是否为空 func (dl *doublyList) isEmpty() bool { return dl.head.next == dl.tail } // 双向链表节点 type doublyListNode struct { key int value int frequency int // 使用次数 prev *doublyListNode next *doublyListNode } // 在某一个节点之前插入一个节点 func addBefore(currNode *doublyListNode, newNode *doublyListNode) { pre := currNode.prev pre.next = newNode newNode.next = currNode currNode.prev = newNode newNode.prev = pre } // LFUCache 具体的缓存 type LFUCache struct { recent map[int]*doublyListNode // frequency 到使用次数为 frequency 的节点中，最近使用的一个的映射 count map[int]int // frequency 到对应频率的节点数量的映射 cache map[int]*doublyListNode // key 到节点的映射 list *doublyList // 双向链表，维护缓存的使用次数（优先）和上一次使用时间 capacity int // 容量 } func removeNode(node *doublyListNode) { node.prev.next = node.next node.next.prev = node.prev } // Constructor 构建缓存容器 func Constructor(capacity int) LFUCache { return LFUCache{ recent: make(map[int]*doublyListNode), count: make(map[int]int), cache: make(map[int]*doublyListNode), list: newDoublyList(), capacity: capacity, } } func newDoublyList() *doublyList { headNode := &doublyListNode{} tailNode := &doublyListNode{} headNode.next = tailNode tailNode.prev = headNode return &doublyList{ head: headNode, tail: tailNode, } } func (lfu *LFUCache) Get(key int) int { if lfu.capacity == 0 { return -1 } node, ok := lfu.cache[key] if !ok { // key 不存在 return -1 } // key 已存在 next := node.next if lfu.count[node.frequency+1] > 0 { // 存在其他使用次数为 n+1 的缓存，将指定缓存移动到所有使用次数为 n+1 的节点之前 removeNode(node) addBefore(lfu.recent[node.frequency+1], node) } else if lfu.count[node.frequency] > 1 && lfu.recent[node.frequency] != node { // 不存在其他使用次数为 n+1 的缓存，但存在其他使用次数为 n 的缓存，且当前节点不是最近的节点 // 将指定缓存移动到所有使用次数为 n 的节点之前 removeNode(node) addBefore(lfu.recent[node.frequency], node) } // 更新 recent lfu.recent[node.frequency+1] = node if lfu.count[node.frequency] <= 1 { // 不存在其他 freq = n 的节点，recent 置空 lfu.recent[node.frequency] = nil } else if lfu.recent[node.frequency] == node { // 存在其他 freq = n 的节点，且 recent = node，将 recent 向后移动一位 lfu.recent[node.frequency] = next } // 更新使用次数对应的节点数 lfu.count[node.frequency+1]++ lfu.count[node.frequency]-- // 更新缓存使用次数 node.frequency++ return node.value } // Put 新建缓存 func (lfu *LFUCache) Put(key int, value int) { if lfu.capacity == 0 { return } node, ok := lfu.cache[key] if ok { // key 已存在 lfu.Get(key) node.value = value return } // key 不存在 if len(lfu.cache) >= lfu.capacity { // 缓存已满，删除最后一个节点，相应更新 cache、count、recent（条件） tailNode := lfu.list.tail.prev lfu.list.removeTail() if lfu.count[tailNode.frequency] <= 1 { lfu.recent[tailNode.frequency] = nil } lfu.count[tailNode.frequency]-- delete(lfu.cache, tailNode.key) } newNode := &doublyListNode{ key: key, value: value, frequency: 1, } // 插入新的缓存节点 if lfu.count[1] > 0 { addBefore(lfu.recent[1], newNode) } else { addBefore(lfu.list.tail, newNode) } // 更新 recent、count、cache lfu.recent[1] = newNode lfu.count[1]++ lfu.cache[key] = newNode }

LRU 与 LFU 页面置换算法对比及 Golang 实现

LRU 和 LFU 的区别

LRU (最长时间)

功能

数据结构

伪代码

更多推荐文章

相关免费在线工具

Golang 代码实现

LFU (最少次)

功能

数据结构

伪代码

Golang 代码实现

LRU 与 LFU 页面置换算法对比及 Golang 实现

LRU 和 LFU 的区别

LRU (最长时间)

功能

数据结构

伪代码

微信扫一扫，关注极客日志

更多推荐文章

相关免费在线工具

Golang 代码实现

LFU (最少次)

功能

数据结构

伪代码

Golang 代码实现