JS 实现缓存算法（FIFO/LRU）

awokezhou 发布于2019-08-22 15:31 / 2609人阅读

摘要：最简单的一种缓存算法，设置缓存上限，当达到了缓存上限的时候，按照先进先出的策略进行淘汰，再增加进新的。队列算法实现缓存需要一个对象和一个数组作为辅助数组记录进入顺序先进先出，删除队列第一个元素无论存在与否都对中的赋值，最近最少使用算法。

FIFO

最简单的一种缓存算法，设置缓存上限，当达到了缓存上限的时候，按照先进先出的策略进行淘汰，再增加进新的 k-v 。

使用了一个对象作为缓存，一个数组配合着记录添加进对象时的顺序，判断是否到达上限，若到达上限取数组中的第一个元素key，对应删除对象中的键值。

/**
 * FIFO队列算法实现缓存
 * 需要一个对象和一个数组作为辅助
 * 数组记录进入顺序
 */
class FifoCache{
    constructor(limit){
        this.limit = limit || 10
        this.map = {}
        this.keys = []
    }
    set(key,value){
        let map = this.map
        let keys = this.keys
        if (!Object.prototype.hasOwnProperty.call(map,key)) {
            if (keys.length === this.limit) {
                delete map[keys.shift()]//先进先出，删除队列第一个元素
            }
            keys.push(key)
        }
        map[key] = value//无论存在与否都对map中的key赋值
    }
    get(key){
        return this.map[key]
    }
}

module.exports = FifoCache

LRU

LRU（Least recently used，最近最少使用）算法。该算法的观点是，最近被访问的数据那么它将来访问的概率就大，缓存满的时候，优先淘汰最无人问津者。

算法实现思路：基于一个双链表的数据结构，在没有满员的情况下，新来的 k-v 放在链表的头部，以后每次获取缓存中的 k-v 时就将该k-v移到最前面，缓存满的时候优先淘汰末尾的。

双向链表的特点，具有头尾指针，每个节点都有 prev(前驱) 和 next(后继) 指针分别指向他的前一个和后一个节点。

关键点：在双链表的插入过程中要注意顺序问题，一定是在保持链表不断的情况下先处理指针，最后才将原头指针指向新插入的元素，在代码的实现中请注意看我在注释中说明的顺序注意点！

class LruCache {
    constructor(limit) {
        this.limit = limit || 10
        //head 指针指向表头元素，即为最常用的元素
        this.head = this.tail = undefined
        this.map = {}
        this.size = 0
    }
    get(key, IfreturnNode) {
        let node = this.map[key]
        // 如果查找不到含有`key`这个属性的缓存对象
        if (node === undefined) return
        // 如果查找到的缓存对象已经是 tail (最近使用过的)
        if (node === this.head) { //判断该节点是不是是第一个节点
            // 是的话，皆大欢喜，不用移动元素，直接返回
            return returnnode ?
                node :
                node.value
        }
        // 不是头结点，铁定要移动元素了
        if (node.prev) { //首先要判断该节点是不是有前驱
            if (node === this.tail) { //有前驱，若是尾节点的话多一步，让尾指针指向当前节点的前驱
                this.tail = node.prev
            }
            //把当前节点的后继交接给当前节点的前驱去指向。
            node.prev.next = node.next
        }
        if (node.next) { //判断该节点是不是有后继
            //有后继的话直接让后继的前驱指向当前节点的前驱
            node.next.prev = node.prev
            //整个一个过程就是把当前节点拿出来，并且保证链表不断，下面开始移动当前节点了
        }
        node.prev = undefined //移动到最前面，所以没了前驱
        node.next = this.head //注意！！！ 这里要先把之前的排头给接到手！！！！让当前节点的后继指向原排头
        if (this.head) {
            this.head.prev = node //让之前的排头的前驱指向现在的节点
        }
        this.head = node //完成了交接，才能执行此步！不然就找不到之前的排头啦！
        return IfreturnNode ?
            node :
            node.value
    }
    set(key, value) {
        // 之前的算法可以直接存k-v但是现在要把简单的 k-v 封装成一个满足双链表的节点
        //1.查看是否已经有了该节点
        let node = this.get(key, true)
        if (!node) {
            if (this.size === this.limit) { //判断缓存是否达到上限
                //达到了，要删最后一个节点了。
                if (this.tail) {
                    this.tail = this.tail.prev
                    this.tail.prev.next = undefined
                    //平滑断链之后，销毁当前节点
                    this.tail.prev = this.tail.next = undefined
                    this.map[this.tail.key] = undefined
                    //当前缓存内存释放一个槽位
                    this.size--
                }
                node = {
                    key: key
                }
                this.map[key] = node
                if(this.head){//判断缓存里面是不是有节点
                    this.head.prev = node
                    node.next = this.head
                }else{
                    //缓存里没有值，皆大欢喜，直接让head指向新节点就行了
                    this.head = node
                    this.tail = node
                }
                this.size++//减少一个缓存槽位
            }
        }
        //节点存不存在都要给他重新赋值啊
        node.value = value
    }
}

module.exports = LruCache

具体的思路就是如果所要get的节点不是头结点（即已经是最近使用的节点了，不需要移动节点位置）要先进行平滑的断链操作，处理好指针指向的关系，拿出需要移动到最前面的节点，进行链表的插入操作。

GPU云服务器云服务器 js实现缓存数据 cdn缓存算法算法实现 cdn缓存如何实现

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/93506.html

《CDN 之我见》系列二：原理篇（缓存、安全）

摘要：真正要做高性能的系统，不仅需要在数据结构与算法层面深入，更要从硬件操作系统文件系统底层原理等多个领域做更多的研究例如阿里云自研的系统使用了裸盘技术。《CDN之我见》共由三个篇章组成，分为原理篇、详解篇和陨坑篇。本篇章适合那些从未接触过、或仅了解一些 CDN 专业术语，想深入了解和感受 CDN 究竟是什么的同学。本次由白金老师继续为大家分享《CDN之我见》系列二，主要讲解缓存是什么、工...

maxmin 2019-06-24 18:02 评论0 收藏0
《CDN 之我见》系列二：原理篇（缓存、安全）

摘要：真正要做高性能的系统，不仅需要在数据结构与算法层面深入，更要从硬件操作系统文件系统底层原理等多个领域做更多的研究例如阿里云自研的系统使用了裸盘技术。《CDN之我见》共由三个篇章组成，分为原理篇、详解篇和陨坑篇。本篇章适合那些从未接触过、或仅了解一些 CDN 专业术语，想深入了解和感受 CDN 究竟是什么的同学。本次由白金老师继续为大家分享《CDN之我见》系列二，主要讲解缓存是什么、工...

rainyang 2019-06-21 16:47 评论0 收藏0
你应该知道的缓存进化史

摘要：先简单介绍一下爱奇艺的缓存道路的发展吧。可以看见图中分为几个阶段第一阶段数据同步加通过消息队列进行数据同步至，然后应用直接去取缓存这个阶段优点是由于是使用的分布式缓存，所以数据更新快。爱奇艺的缓存的发展也是基于此之上，通过对的二次开发 1.背景本文是上周去技术沙龙听了一下爱奇艺的Java缓存之路有感写出来的。先简单介绍一下爱奇艺的java缓存道路的发展吧。 showImg(https...

remcarpediem 2019-08-16 15:35 评论0 收藏0
你应该知道的缓存进化史

摘要：先简单介绍一下爱奇艺的缓存道路的发展吧。可以看见图中分为几个阶段第一阶段数据同步加通过消息队列进行数据同步至，然后应用直接去取缓存这个阶段优点是由于是使用的分布式缓存，所以数据更新快。爱奇艺的缓存的发展也是基于此之上，通过对的二次开发 1.背景本文是上周去技术沙龙听了一下爱奇艺的Java缓存之路有感写出来的。先简单介绍一下爱奇艺的java缓存道路的发展吧。 showImg(https...

Tangpj 2019-08-06 13:40 评论0 收藏0
【Mybatis系列】从源码角度深度理解Mybatis的缓存特性

摘要：一级缓存介绍及相关配置。在这个章节，我们学习如何使用的一级缓存。一级缓存实验配置完毕后，通过实验的方式了解一级缓存的效果。源码分析了解具体的工作流程后，我们队查询相关的核心类和一级缓存的源码进行走读。我，后端Java工程师，现在美团点评工作。爱健身，爱技术，也喜欢写点文字。个人网站: http://kailuncen.me公众号: KailunTalk (凯伦说) 前言本文主要涉及...

Ku_Andrew 2019-08-15 10:47 评论0 收藏0