JavaScript双向链表实现LFU缓存算法

目录

什么是LFU描述解题思路1、构造节点结构体2、构造双向链表3、编写链表头添加节点方法4、编写删除节点方法5、构造LRU缓存结构体6、编写get方法7、编写put方法

什么是LFU

LFU（Least Frequently Used），最近最少使用策略，也就是说在一段时间内，数据被使用频次最少的，优先被淘汰。
它是一种用于管理计算机内存的缓存算法，采用LFU算法的最简单方法是为每个加载到缓存的块分配一个计数器。每次引用该块时，计数器将增加一。当缓存达到容量并有一个新的内存块等待插入时，系统将搜索计数器最低的块并将其从缓存中删除。

描述

请你为 最不经常使用（LFU）缓存算法设计并实现数据结构。

实现 LFUCache 类：

LFUCache(int capacity) - 用数据结构的容量 capacity 初始化对象

int get(int key) - 如果键 key 存在于缓存中，则获取键的值，否则返回 -1 。

void put(int key, int value) - 如果键 key 已存在，则变更其值；如果键不存在，请插入键值对。

当缓存达到其容量 capacity 时，则应该在插入新项之前，移除最不经常使用的项。

在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，应该去除 最近最久未使用 的键。

为了确定最不常使用的键，可以为缓存中的每个键维护一个 使用计数器 。使用计数最小的键是最久未使用的键。

当一个键首次插入到缓存中时，它的使用计数器被设置为 1 (由于 put 操作)。对缓存中的键执行 get 或 put 操作，使用计数器的值将会递增。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

解题思路

1、构造节点结构体

保存对应的数据信息

const LFUNode = function ( key = "", val = "", freq = 0, pre = null, next = null) { this.key = key; this.val = val; this.freq = freq; this.pre = pre; this.next = next;};

2、构造双向链表

构造带有头尾节点的双向链表，head和tail为哨兵节点，不保存信息，仅用于标记头尾。

const LFULinkLine = function (node) { let head = new LFUNode("head"); let tail = new LFUNode("tail"); head.next = node; tail.pre = node; node.pre = head; node.next = tail; this.head = head; this.tail = tail;};

3、编写链表头添加节点方法

将节点插入到链表的头结点之后，其他节点往后移。

LFULinkLine.prototype.addNode = function (node) { this.head.next.pre = node; node.pre = this.head; node.next = this.head.next; this.head.next = node;};

4、编写删除节点方法

将节点从链表中删除。

LFULinkLine.prototype.removeNode = function (node) { node.pre.next = node.next; node.next.pre = node.pre;};

5、构造LRU缓存结构体

构造LRU缓存结构体，具体信息如下代码，capacity用于保存最大缓存数，即该类的容量；num保存当前存储的数据量，用于判别是否超出最大容量；minFreq保存当前存储的数据中的最小频率，删除的时候需要优先删除频率最小的；kvMap保存节点详细信息，索引为节点的key值，查询可以直接从这里查出信息；freqMap保存对应频率的链表信息，索引为节点的freq（频率），删除的时候可以快速从这里获取需要删除节点的信息。

/*** @param {number} capacity*/var LFUCache = function (capacity) { this.capacity = capacity;//最大缓存 this.num = 0;//当前数目 this.minFreq = 0;//当前最小频率 this.kvMap = new Map();//保存节点信息 this.freqMap = new Map();//保存对应频率的链表信息};

6、编写get方法

get主要有以下两种情况：

（1）节点存在

通过kvMap获取到对应节点将节点从freqMap中删除判断是否需要修改minFreq修改节点的freq重新将节点插入freqMap返回节点的value

（2）节点不存在
容量capacity为0或者kvMap中没有该节点信息，直接返回-1即可。

/*** @param {number} key* @return {number}*/LFUCache.prototype.get = function (key) { if (this.capacity === 0) return -1; if (!this.kvMap.has(key)) return -1; //通过kvMap获取到对应节点 let node = this.kvMap.get(key); let linkLine = this.freqMap.get(node.freq); //将节点从freqMap中删除 linkLine.removeNode(node); //判断是否需要修改minFreq //清空了 if (linkLine.head.next === linkLine.tail) {  this.freqMap.delete(node.freq);  if (this.minFreq == node.freq) this.minFreq++; } //修改节点的freq node.freq++; //重新将节点插入freqMap if (this.freqMap.has(node.freq)) {  linkLine = this.freqMap.get(node.freq);  linkLine.addNode(node); } else {  this.freqMap.set(node.freq, new LFULinkLine(node)); } //返回节点的value return node.val;};

7、编写put方法

put操作主要有以下两种情况：

（1）更新

通过kvMap获取到对应节点将节点从freqMap中删除判断是否需要修改minFreq更新节点信息重新将节点插入freqMap

（2）存入

存入情况下又有两种情况：

容量已满

通过minFreq找到需要删除的节点将节点从freqMap中删除判断是否需要修改minFreq将新节点插入freqMap更新minFreq

容量未满

修改num将新节点插入freqMap更新minFreq

/*** @param {number} key* @param {number} value* @return {void}*/LFUCache.prototype.put = function (key, value) { if (this.capacity === 0) return; if (this.kvMap.has(key)) {  //更新  //通过kvMap获取到对应节点  let node = this.kvMap.get(key);  //将节点从freqMap中删除  let linkLine = this.freqMap.get(node.freq);  linkLine.removeNode(node);  //判断是否需要修改minFreq  if (linkLine.head.next === linkLine.tail) {   if (this.minFreq == node.freq) this.minFreq++;   this.freqMap.delete(node.freq);  }  //更新节点信息  node.val = value;  node.freq++;  //重新将节点插入freqMap  if (this.freqMap.has(node.freq)) {   linkLine  if (this.capacity == this.num) {   //存满   let freq = this.minFreq;   let linkLine = this.freqMap.get(freq);   let node = linkLine.tail.pre;   linkLine.removeNode(node);   this.kvMap.delete(node.key);   if (linkLine.head.next === linkLine.tail) {    this.freqMap.delete(node.freq);   }  } else {   this.num++;  }  let node = new LFUNode(key, value, 0);  this.kvMap.set(key, node);  if (this.freqMap.has(0)) {   let linkLine = this.freqMap.get(0);   linkLine.addNode(node);  } else {   let linkLine = new LFULinkLine(node);   this.freqMap.set(0, linkLine);  }  this.minFreq = 0; }};/*** Your LFUCache object will be instantiated and called as such:* var obj = new LFUCache(capacity)* var param_1 = obj.get(key)* obj.put(key,value)*/