這篇文章主要介紹了JS 實作快取演算法的範例（FIFO/LRU）,現在分享給大家，也給大家做個參考。
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 = FifoCacheLRU
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的節點不是頭結點（即已經是最近使用的節點了，不需要移動節點位置）要先進行平滑的斷鍊操作，處理好指針指向的關係，拿出需要移動到最前面的節點，進行鍊錶的插入操作。
上面是我整理給大家的，希望今後對大家有幫助。
相關文章：
以上是JS 實作快取演算法的範例的詳細內容。更多資訊請關注PHP中文網其他相關文章！
