本文共 1671 字，大约阅读时间需要 5 分钟。
最近，我在对缓存算法产生了浓厚的兴趣，尤其是对 LRU（Least Recently Used） 算法充满了好奇。为了更深入地理解它的工作原理，我决定自己动手实现一个简易的LRU结构。通过这个过程，我不仅加深了对LRU的理解，还锻炼了自己的编程技巧。以下是我的实现过程和思考。
LRU（Least Recently Used） 是一种常用的缓存替换算法，其核心思想是：在缓存空间有限的情况下，优先移除那些长时间未被使用的数据项。简单来说，就是“最近最少使用”的数据优先被替换出缓存。
为了实现LRU，我遵循以下几个步骤：
基于以上步骤，我尝试写出了第一版代码：
let lruArr = [];const limit = 3;function put(val) { let index = lruArr.findIndex(item => item === val); if (index !== -1) { lruArr.splice(index, 1); } lruArr.unshift(val); if (lruArr.length > limit) { lruArr.splice(-1, 1); }} 这个版本虽然能够实现基本的LRU功能，但有一些地方可以优化。首先，查找元素是否存在的方法使用了 findIndex，这会导致在每次调用 put 函数时都进行一次O(n)的遍历。如果队列很大，这样做效率会比较低。其次，代码中的一些操作可以合并成更少的行，简化代码结构。
为了进一步优化，我考虑使用ES6类结构来封装LRU的实现：
class LRU { constructor(limit) { this.limit = limit; this.arr = []; } put(val) { this.arr.unshift(val); this.arr = [...new Set(this.arr)]; if (this.arr.length > this.limit) { this.arr.pop(); } }} 这个版本将代码封装在类中，使用了 unshift 将元素插入队首，Set 来去重，pop 移除超出限制的元素。这种实现不仅代码简洁，而且避免了多次重复使用 splice 方法，提升了代码的可读性和效率。
为了测试这个LRU的实现，我进行了以下操作：
put('麻辣烫')：队列变为 ['麻辣烫']。put('砂锅粥')：队列变为 ['砂锅粥', '麻辣烫']。put('麻辣香锅')：队列变为 ['麻辣香锅', '砂锅粥', '麻辣烫']。put('烧烤')：队列变为 ['烧烤', '麻辣香锅', '砂锅粥']。put('砂锅粥')：队列变为 ['砂锅粥', '烧烤', '麻辣香锅']。这些测试步骤模拟了用户的搜索行为，验证了LRU算法在实际使用中的表现。每次新元素的添加都会被正确地处理，超出限制的元素也会被及时移除。
通过这次实现，我对LRU的理解更加深入了。虽然代码实现简单，但展示了该算法的核心逻辑和应用场景。未来，我可以进一步探索LRU的其他变种，如LFU（Least Frequently Used）或者更复杂的缓存替换策略，并尝试将其应用到更复杂的系统中。同时，我也计划进一步优化现有代码，使其更加高效和易于维护。
转载地址：http://nstf.baihongyu.com/