17 | 如何通过链表做LRU/LFU缓存？
石川
你好，我是石川。
前面我们在第 10-13 讲讲过了数组这种数据类型，以及通过它衍生出的栈和队列的数据结构。之后，我们在讲到散列表的时候，曾经提到过一种链表的数据结构。今天，我们就来深入了解下链表和它所支持的相关的缓存算法。链表有很多使用场景，最火的例子当属目前热门的区块链了。它就是用了链表的思想，每一个区块儿之间都是通过链表的方式相连的。在链表结构里，每一个元素都是节点，每个节点有自己的内容和相连的下一个元素的地址参考。
既然我们讲的是 JavaScript，还是回到身边的例子，就是缓存。无论是我们的操作系统，还是浏览器，都离不开缓存。我们把链表和散列表结合起来，就可以应用于我们常说的缓存。那这种缓存是如何实现的呢？接下来就先从链表说起吧。
如何实现单双循环链表
单链表
下面我们先来看看一个单向链表是怎么实现的。链表就是把零散的节点（node）串联起来的一种数据结构。在每个节点里，会有两个核心元素，一个是数据，一个是下一个节点的地址，我们称之为后继指针（next）。在下面的例子里，我们先创建了一个节点（node），里面有节点的数据（data）和下一个节点的地址（next）。
在实现上，我们可以先创建一个节点的函数类，里面包含存储数据和下一节点两个属性。
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线笔记
复制
AI
- 深入了解
- 翻译
- 解释
- 总结
LRU和LFU缓存算法是常见的缓存策略，本文深入介绍了它们的实现细节和应用场景。首先，文章详细讨论了LFU缓存的实现，包括LFU节点、LFU双链表和相关操作场景。LFU缓存通过两个散列表来实现，一个是键值散列表，另一个是频率散列表。在LFU缓存中，插入、更新和读取是三个核心操作场景。接着，文章提到了LRU缓存的实现方式，强调了需要追踪节点的访问时间，并介绍了LRU缓存的节点和散列表的使用。最后，文章对比了LRU和LFU缓存的使用情况，指出在实际应用中更多地使用LRU的原因。总的来说，LFU没有考虑时间局部性，而LRU更符合实际应用的需求。通过本文的阅读，读者可以深入了解缓存算法的实现细节，对于想要深入了解缓存算法的读者来说，是一篇值得阅读的文章。
仅可试看部分内容，如需阅读全部内容，请付费购买文章所属专栏
《JavaScript 进阶实战课》，新⼈⾸单¥59
《JavaScript 进阶实战课》，新⼈⾸单¥59
立即购买
© 版权归极客邦科技所有，未经许可不得传播售卖。 页面已增加防盗追踪，如有侵权极客邦将依法追究其法律责任。
登录 后留言
全部留言(2)
- 最新
- 精选
天择
LRU具备时间“局部”性，而LFU恰恰一种“全局”性。在需要考虑全局频率的场景里面，LFU是有用的。最近有大量访问，不代表始终有大量访问；比如电商的热门商品，可能在几个月的维度上做了统计，如果采用LRU策略，短时促销活动可能会把这些长期热门商品冲出缓存，导致过了促销，原来的热门商品缓存无法命中。作者回复: 有道理
2022-10-27归属地：北京3
无咎频率分布有规律的场景，比如：点餐，热销的菜品集中在少数几个。2023-05-05归属地：北京
收起评论