写一个可以让面试官惊到掉下巴的LRU缓存算法

站长

2024年04月14日 17:55 · 阅读数 8

基本介绍

LRU （Least Recently Used）算法基于"最近最少使用"的原则进行淘汰，是一个处理数据的方式， 通常我们用它管理一组数据，当我们往这一组数据添加数据的时候如果加入后数据量超过一个阈值，那么就将这一组数据中最晚使用的那个元素给删除。或者也可以理解为按使用时间的时间戳从大到小排列，时间戳最小的那个元素将被删除。

ps: LRU 是一个处理数据的范式，不局限于任何数据，链表，堆，数组对象，有n种数据结构，n种处理方式来实现这个范式，但是本质上的思想还是一样的

正文开始

这天主人公阿辉如约到一家公司参加面试，hr让他填完表坐在旁边等一下，说是技术负责人还在开晨会，阿辉心里犯了下嘀咕：都10点了还在开晨会，过一会儿hr向我挥了挥手，示意我去一个小会议室里面，我进去之后，在hr示意的位置坐下后hr对我说：你简历带了吧，先放到桌子上，技术负责人马上就来。

过了一会儿，一个发际线很像一个n的男人走进来了，绷着一张不是很好开的脸，上来就是一通触发连招，自我介绍，项目介绍，技术上的基本问题，这些对经历过n次面试的阿辉来说已经熟记于心了。

面试官的脸色稍稍有点缓和下来了，只见他又说了一句，来实现一个LRU缓存吧，阿辉听到后心里一阵窃喜，LRU 缓存，昨晚刚好背了这道八股文，还手搓了好几遍，这不就大熊猫吃竹子——胸有成竹了。

阿辉比了一个十字的手势说：十分钟给你写出来。然后他写出了以下的代码

class Lru {
   
     catchMap = new Map()
     limit = 10
     constructor(limit) {
        
         this.limit = limit
     }
     
     get(key) {
         if (this.catchMap.has(key)) {
            const value = this.catchMap.get(key)
            this.catchMap.delete(key)
            this.catchMap.set(key, value)
             
            return value
         }
         return undefined
     }

     set(key, value) {
       /* 
         Map set 的key 重复的话 会沿用旧的，所以这里删除一下再插进去
       */
         if (this.catchMap.has(key)) {
             this.catchMap.delete(key)
         }
         if (this.catchMap.size >= this.limit) {
             const lastKey = this.catchMap.keys().next().value
             this.catchMap.delete(lastKey)
         }
         this.catchMap.set(key, value)
     }

     getAllKeys() {
         return this.catchMap.keys()
     }

     size() {
         return this.catchMap.size
     }
 }

const lru = new Lru(3)

lru.set(1, 1)
lru.set(2, 2)
lru.set(3, 3)
lru.set(4, 4)

// 正常输出 undefined 3
console.log(
   lru.get(1),
   lru.get(3),

)
console.log(lru.getAllKeys()) // 正常输出234

阿辉给出代码后脸上多了一丝得意的笑容，随后道：这种写法利用了Map 的顺序是根据插入的先后来决定的，不像是对象那种 key是根据编码后来排序的，另外他又补充到八股文的剩余内容，另外还有数组对象和双向链表这种实现方式。说完后阿辉脸上的笑容就更得以了，心里想，这一面稳了。

阿辉看了看面试官的脸色，发现毫无变化，心里感觉到了一丝丝的不对劲，之后面试官缓缓的张口道：你这个类构造实例的时候我limit传个0 不就gameOver 了么？阿辉赶紧连忙看向代码处，确实0的话就始终在一个元素无限徘徊。随后面试官继续追问

面试官：limit 万一我传个字符串你不就g了

阿辉：。。。

面试官：limit 是小数的时候这种情况你好像没有处理哦，不论是四舍五入，还是向下取整

阿辉：。。。

面试官：limit 万一我传个Infinity 这时候你这个类不就相当于白写了么

阿辉：。。。

面试官：get 方法没找到直接返回undefined 难道你不知道undefined 不是关键字么

阿辉：。。。

面试官追问了一通之后阿辉的脸色沉了下来，之间面试官说，要不你改一下，又过了10分钟，阿辉拿出了下面的代码

class Lru {
   catchMap = new Map()
   limit = 10
   error = false
   constructor(limit) {
       limit = Number(limit)
       const isNaN = Number.isNaN(limit)
       if (isNaN) {
           this.error = true
       }
       if (!isNaN && String(limit).includes('.')) {
           limit = Math.floor(limit)
           console.warn("limit 需要是一个整数的哦 小数位将被忽略")
       }
       this.limit = Number(limit)
   }
   reg() {
       const doneUnit = [this.limit < 1, this.error]
       if (doneUnit.some(i => Boolean(i))) {
           return false
       }
       return true
   }
   get(key, { ignorePush } = {}) {
       if (this.catchMap.has(key)) {
           const value = this.catchMap.get(key)
           if (!ignorePush) {
               this.catchMap.delete(key)
               this.catchMap.set(key, value)
           }
           return value
       }
       return void 0
   }

   set(key, value) {
       if (!this.reg()) return
       if (this.catchMap.has(key)) {
           this.catchMap.delete(key)
       }
       if (this.catchMap.size >= this.limit) {
           const lastKey = this.catchMap.keys().next().value
           this.catchMap.delete(lastKey)
       }
       this.catchMap.set(key, value)
   }

   getAllKeys() {
       return this.catchMap.keys()
   }

   size() {
       return this.catchMap.size
   }
}

const lru = new Lru(3)

lru.set(1, 1)
lru.set(2, 2)
lru.set(3, 3)
lru.set(4, 4)

console.log(
   lru.get(1),
   lru.get(3),

)
console.log(lru.getAllKeys())

然后道，这次我单独做了一个错误信息字段，后续新功能拓展也可以用，并且设置了校验的函数，如果没有校验通过的话操作将会被直接拦截 undefined 改成使用void，还顺带给get方法也拓展了配置操作

面试官看了，很满意的点了点头，但是他随后又说道，你有没有发现你的这个构造类有一个致命的缺陷。阿辉咽了口口水说到，不会是继承的时候当作基类使用.... ，对面还没等阿辉说完就抢答道，没错，你的这个基类没有遵守开放封闭这个原则， 基类应该提供给子类操作的方法，比如get方法，但子类直接操作 map 操作 error 等关键信息，做限制，万一子类刚好也有一个 error 属性，你这个实例逻辑不久炸了么。

阿辉思考了一下，随后不等面试官反应，花了10分钟给出了最终的代码

class Lru {
    #catchMapKey = Symbol('catchMapKey')
    #limitKey = Symbol('limitKey')
    #errorKey = Symbol('errorKey')

    constructor(limit) {
        this[this.#catchMapKey] = new Map()
        this[this.#limitKey] = 10
        this[this.#errorKey] = false



        limit = Number(limit)
        const isNaN = Number.isNaN(limit)
        if (isNaN) {
            this[this.#errorKey] = true
        }
        if (!isNaN && String(limit).includes('.')) {
            limit = Math.floor(limit)
            console.warn("limit 需要是一个整数的哦 小数位将被忽略")
        }
        this[this.#limitKey] = Number(limit)
    }
    #getNowMap() {
        return this[this.#catchMapKey]
    }
    #getNowLimit() {
        return this[this.#limitKey]
    }
    #getNowError() {
        return this[this.#errorKey]
    }
    #reg() {
        const doneUnit = [this.#getNowLimit() < 1, this.#getNowError()]
        if (doneUnit.some(i => Boolean(i))) {
            return false
        }
        return true
    }
    get(key, { ignorePush } = {}) {
        if (this.#getNowMap().has(key)) {
            const value = this.#getNowMap().get(key)
            if (!ignorePush) {
                this.#getNowMap().delete(key)
                this.#getNowMap().set(key, value)
            }
            return value
        }
        return void 0
    }

    set(key, value) {
        if (!this.#reg()) return
        if (this.#getNowMap().has(key)) {
            this.#getNowMap().delete(key)
        }
        if (this.#getNowMap().size >= this.#getNowLimit()) {
            const lastKey = this.#getNowMap().keys().next().value
            this.#getNowMap().delete(lastKey)
        }
        this.#getNowMap().set(key, value)
    }

    getAllKeys() {
        return this.#getNowMap().keys()
    }

    size() {
        return this.#getNowMap().size
    }
}

const lru = new Lru(3)

lru.set(1, 1)
lru.set(2, 2)
lru.set(3, 3)
lru.set(4, 4)

console.log(
    lru.get(1),
    lru.get(3),

)
console.log(lru.getAllKeys())

这次我用私有属性 + Symbol 来彻底把对应的方法和数据对子类关闭，只对父类开放，这样既遵守了设计原则，也防止了子类重名的风险。

说罢阿辉摸了一把头上的汗

不错不错，在一旁的面试官鼓起来了掌，阿辉看了看面试官的头顶，感觉他头顶映射出来的灯光，又亮了几分。

几天后

阿辉收到了这家公司的offer ，心想这不得来个30k，结果点开邮件一看，基本工资+绩效才4500，阿辉直接当场大骂****************。

完

结语

本文想通过讲故事的形式，来对LRU缓存算法这样一道常考的面试题进行深入的讲解，不局限于常规的解题思路，还延伸出了写法的局限性，构造类潜在的问题，来拨云见日的对LUR算法有一个更清晰的见解。

任何代码知识点都不是孤立的，档期把你的代码知识点都关联起来的时候，你才能更深入的理解它

文末思考

你以为这样就结束了么？不还远远不止，我留了几个问题给大家，大家可以充分发表你们的见解

如果这个 limit 限制是动态的需要实时的更新呢？比如掉接口后之类的

set 的时候如果需要异步操作怎么处理？是用中间件？还是直接实现？

目前set 一次只能set 单个如果我想一次批量set呢？

如果我现在set 的这挑数据已知的不是重要的数据怎么样给他排在最末呢？

现在get 一次只能拿到一个数据如果我想到一次拿多个，那lru 应该怎么设计呢？