【JS算法】LRU 缓存

先复习下迭代器和可迭代对象

迭代器是确使用户可在容器对象（如链表、数组）上遍访的对象，使用该接口无需关心对象的内部实现细节

const arr = [1, 2, 3, 4, 5, 6]
const iterator = arr[Symbol.iterator]() // 执行一个迭代器
console.log(iterator) // Object [Array Iterator] {}

console.log(iterator.next()) //{ value: 1, done: false }
console.log(iterator.next()) //{ value: 2, done: false }
let next = iterator.next()

while (!next.done) {
  console.log(next.value) //分别打印 3 4 5 6
  next = iterator.next()
}

可迭代对象 它和迭代器是不同的概念，这个对象必须实现@iterator 方法，在代码中我们使用 Symbol.iterator 访问该属性

const iteratorObj = {
  names: ['a', 'b', 'c', 'd'],
  index: 0,
  [Symbol.iterator]: function () {
    return {
      // 这边使用箭头函数，以使this指向iteratorObj
      next: () => {
        if (this.index < this.names.length) {
          // [this.index++] 是先调[this.index]，再++
          return { value: this.names[this.index++], done: false }
        } else {
          return { value: 'no name', done: true }
}}}}}
const iterator1 = iteratorObj[Symbol.iterator]()
console.log(iterator1) //[Map Iterator] { 'a', 'b', 'c' }

console.log(iterator1.next()) //{ value: 'a', done: false }
console.log(iterator1.next()) //{ value: 'b', done: false }
let next2 = iterator1.next()
while (!next2.done) {
  console.log(next2.value) //分别打印 c d
  next2 = iterator1.next()
}

Map对象.keys() 返回的是一个迭代对象

let cache = new Map()
cache.set('a', 1)
cache.set('b', 2)
cache.set('c', 3)
const data = cache.keys()
console.log(data) //[Map Iterator] { 'a', 'b', 'c' }

//错误用法
console.log(cache.keys().next()) //{ value: 'a', done: false }
console.log(cache.keys().next()) //{ value: 'a', done: false }

//正确
console.log(data.next()) //{ value: 'a', done: false }
console.log(data.next()) //{ value: 'b', done: false }
console.log(data.next()) //{ value: 'c', done: false }

LRU 缓存

它是一种缓存淘汰机制，顾名思义，将最近使用次数最少的缓存淘汰

如何设计一个简单的LRU缓存算法？

举个栗子，内存容量大小为2，按照key-value形式存储，结构的前面（最右侧）为最近最常使用的节点，后面（最左侧）为最近最少使用的节点。

LRU有两个操作：get和put，每次get和put操作都将查询的值变为最近最常使用的节点，当put容量已满时，删除最近最少使用的节点

var LRUCache = function (capacity) {
  this.cache = new Map()
  this.max = capacity //缓存最大个数
}

//原型链上挂get方法
LRUCache.prototype.get = function (key) {
  if (this.cache.has(key)) {
    let tmp = this.cache.get(key)
    this.cache.delete(key)
    this.cache.set(key, tmp) //删除后，重新放到最前面
    return tmp
  }
  return -1 //题目要求返回-1
}

LRUCache.prototype.put = function (key, value) {
  if (this.cache.has(key)) {
    this.cache.delete(key) //删除后，重新放到最前面
  } else if (this.cache.size >= this.max) {
    //新增就要有缓存的淘汰机制
    this.cache.delete(this.cache.keys().next().value)
  }
  this.cache.set(key, value)
}

let cache = new LRUCache(2)
cache.put(1, 1) // 缓存是 {1=1}
cache.put(2, 2) // 缓存是 {1=1, 2=2}
cache.get(1) // 返回 1 变{2=2, 1=1}
cache.put(3, 3) // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
cache.get(2) // 返回 -1 (未找到)
cache.put(4, 4) // 该操作会使得关键字 1 作废，缓存是 {3=3,4=4}
cache.get(1) // 返回 -1 (未找到)
cache.get(3) // 返回 3  变{4=4, 3=3}
cache.get(4) // 返回 4  变{3=3, 4=4}

vue中keep-alive 用到的就是 LRU 缓存