LRU 是 Least Recently Used 的缩写,即最近最少使用。作为一种经典的缓存策略,它的基本思想是长期不被使用的数据,在未来被用到的几率也不大,所以当新的数据进来时我们可以优先把这些数据替换掉。
下面提供两种实现方式,并完成相关代码。
在 Javascript 中,Map 的 key 是有序的,当迭代的时候,他们以插入的顺序返回键值。结合这个特性,我们也通过 Map 实现 LRU 算法。
我们也可通过双向链表(Doubly Linked List)维护缓存条目,通过对链表的增、删、改实现数据管理。为确保能够从链表中快速读取某个节点的数据,我们可以通过 Map 来存储对链表中节点的引用。
在 初始化时 完成两件事情:
在 添加数据 时:
基于 Javascript Map 实现 LRU,代码如下:
class LRUCache {
size = 5
constructor(size) {
this.cache = new Map()
this.size = size || this.size
}
get(key) {
if (this.cache.has(key)) {
// 存在即更新
let temp = this.cache.get(key)
this.cache.delete(key)
this.cache.set(key, temp)
return temp
}
return null
}
set(key, value) {
if (this.cache.has(key)) {
this.cache.delete(key)
}
if (this.cache.size >= this.size) {
this.cache.delete(this.cache.keys().next().value)
}
this.cache.set(key, value)
}
}
包含 prev,next,data 三个属性,分别用以存储指向前后节点的引用,以及当前节点要存储的数据。
{
prev: Node
next: Node
data: { key: string, data: any}
}
包含 head、tail 属性,分别指向链表的 头节点 和 尾节点。
当从链表中读取数据时,需要将当前读取的数据移动到链表头部;添加数据时,将新节点插入到头部;当链表节点数量大于限定的阀值,需要从链表尾部删除节点。
{
head: Node
next: Node
moveNodeToHead(node)
insertNodeToHead(node)
deleteLastNode()
}
为 LRU 定义属性:linkLine 用以存储指向链表的引用;size 用以配置存储空间大小限制;
为简化从链表中查找节点,再定义 map 属性,用以存储不同键指向链表节点的引用。
定义成员方法,set(key,value) 用以添加数据,get(key) 读取一条数据。
如果 map 中存在当前 key,从链表中读取节点,将其移动到链表头部,并返回结果,否则返回空。
{
linkLine: LinkLine
map: Map
size: Number
set(key, value)
get(key)
}
class LinkNode {
prev = null
next = null
constructor(key, value) {
this.data = { key, value }
}
}
class LinkLine {
head = null
tail = null
constructor() {
const headNode = new LinkNode('head', 'head')
const tailNode = new LinkNode('tail', 'tail')
headNode.next = tailNode
tailNode.prev = headNode
this.head = headNode
this.tail = tailNode
}
moveNodeToFirst(node) {
node.prev.next = node.next
node.next.prev = node.prev
this.insertNodeToFirst(node)
}
insertNodeToFirst(node) {
const second = this.head.next
this.head.next = node
node.prev = this.head
node.next = second
second.prev = node
}
delete(node) {
node.prev.next = node.next
node.next.prev = node.prev
}
deleteLastNode() {
const last = this.tail.prev
this.tail.prev = last.prev
last.prev.next = this.tail
return last
}
}
class LRUCache {
linkLine = null
map = {}
size = 5
constructor(size) {
this.size = size || this.size
this.linkLine = new LinkLine
}
get(key) {
let value
if (this.map[key]) {
const node = this.map[key]
value = node.value
this.linkLine.moveNodeToFirst(node)
}
return value
}
set(key, value) {
if (this.map[key]) {
const node = this.map[key]
node.value = value
this.linkLine.moveNodeToFirst(node)
} else {
// 删除最后一个元素
if (Object.keys(this.map).length >= this.size) {
const lastNode = this.linkLine.deleteLastNode()
delete this.map[lastNode.data.key]
}
const newNode = new LinkNode(key, value)
this.linkLine.insertNodeToFirst(newNode)
this.map[key] = newNode
}
}
}
有一个数组,我们需要通过js对数组的元素进行随机排序,然后输出,这其实就是洗牌算法,首页需要从元素中随机取一个和第一元进行交换,然后依次类推,直到最后一个元素。
程序员必须知道的10大算法:快速排序算法、堆排序算法、归并排序、二分查找算法、BFPRT(线性查找算法)、DFS(深度优先搜索)、BFS(广度优先搜索)、Dijkstra算法、动态规划算法、朴素贝叶斯分类算法
使用原生js将一维数组中,包含连续的数字分成一个二维数组,这篇文章分2种情况介绍如何实现?1、过滤单个数字;2、包含单个数字。
给定一个无序的整数序列, 找最长的连续数字序列。例如:给定[100, 4, 200, 1, 3, 2],最长的连续数字序列是[1, 2, 3, 4]。此方法不会改变传入的数组,会返回一个包含最大序列的新数组。
racking.js 是一个独立的JavaScript库,实现多人同时检测人脸并将区域限定范围内的人脸标识出来,并保存为图片格式,跟踪的数据既可以是颜色,也可以是人,也就是说我们可以通过检测到某特定颜色,或者检测一个人体/脸的出现与移动,来触发JavaScript 事件。
JS常见算法题目:xiaoshuo-ss-sfff-fe 变为驼峰xiaoshuoSsSfffFe、数组去重、统计字符串中出现最多的字母、字符串反序、深拷贝、合并多个有序数组、约瑟夫环问题
这篇文章主要是针对一种最常见的非对称加密算法——RSA算法进行讲解。其实也就是对私钥和公钥产生的一种方式进行描述,RSA算法的核心就是欧拉定理,根据它我们才能得到私钥,从而保证整个通信的安全。
PageRank,网页排名,又称网页级别、Google左侧排名或佩奇排名,是一种由 根据网页之间相互的超链接计算的技术,而作为网页排名的要素之一,以Google公司创办人拉里·佩奇(Larry Page)之姓来命名。
什么是回文字符串?即字符串从前往后读和从后往前读字符顺序是一致的。例如:字符串aba,从前往后读是a-b-a;从后往前读也是a-b-a
将一个整数中的数字进行颠倒,当颠倒后的整数溢出时,返回 0 ;当尾数为0时候需要进行舍去。解法:转字符串 再转数组进行操作,看到有人用四则运算+遍历反转整数。
内容以共享、参考、研究为目的,不存在任何商业目的。其版权属原作者所有,如有侵权或违规,请与小编联系!情况属实本人将予以删除!