My Muri Life

切换主题

本页目录

LRU ​

LRU是Least Recently Used的缩写，即最近最少使用，是一种常用的页面置换算法，选择最近最久未使用的页面予以淘汰。

双向链表 + 哈希表 ​

实现过程描述：

  1. 首先初始化双向链表与哈希表;
  2. 对于get操作，先查询哈希表是否存在该key：
    • 若不存在，直接返回-1;
    • 若存在，由于get操作访问了该key，需将该key对应的节点更新至链表头部，再返回该节点值。
  3. 对于put操作，先判断key是否在hashTable中：
    • 若不存在，在链表头部插入该key的节点同时更新hashTable，并且判断hashTable的size是否超出cap限制： 若超出，则删除最近最不常用节点，即尾节点并更新哈希表
    • 若存在，直接更新hashTable对应的值和链表节点（移至链表头部） 。

设计dummyHead和dummyTail的意义：

虚拟头尾节点，只是为了让对真实头尾节点的操作，和对其他节点的操作一致，方便快速访问头尾节点。

JavaScript
class ListNode {
  constructor(key, val) {
    this.key = key
    this.val = val
    this.prev = null  // 前驱指针
    this.next = null  // 后继指针
  }
}

class LRUCache {
  constructor(capacity) {
    this.cap = capacity
    this.hashTable = {}
    this.len = 0
    // 初始化双向链表
    this.dummyHead = new ListNode()
    this.dummyTail = new ListNode()
    this.dummyHead.next = this.dummyTail
    this.dummyTail.prev = this.dummyHead
  }
  // 链头添加节点
  addToHead(node) {
    node.prev = this.dummyHead
    node.next = this.dummyHead.next
    this.dummyHead.next.prev = node  //  先执行
    this.dummyHead.next = node  //  再执行
  }
  // 删除节点
  removeNode(node) {
    let prevNode = node.prev
    let nextNode = node.next
    prevNode.next = nextNode
    nextNode.prev = prevNode
  }
  // 移动链表
  moveToHead(node) {
    this.removeNode(node)
    this.addToHead(node)
  }

  get(key) {
    const node = this.hashTable[key]
    if (!node) return -1  // 不存在直接返回-1
    this.moveToHead(node)  // 更新链表
    return node.val
  }

  put(key, val) {
    const node = this.hashTable[key]
    if (!node) {  // 先判断其是否在hashTable中
      const newNode = new ListNode(key, val)
      this.addToHead(newNode) // key不在时，链表头部插入节点并更新hashTable
      this.hashTable[key] = newNode  // 存入节点
      this.len++
      // 判断hashTable的size是否超出cap限制
      if (this.len > this.cap) {
        // 删除最近最不常用节点，即尾节点并更新哈希表
        const tail = this.dummyTail.prev
        this.removeNode(tail)
        delete this.hashTable[tail.key]
        this.len--
      }
    } else {  // key已存在直接更新hashTable和链表
      node.val = val   // 更新值
      this.moveToHead(node)
    }
  }
}

hashMap ​

关于JavaScript中的hashMap你可以前往MDN了解更多， 这里就说一个重要特性：

Map保存键值对时，会记住键的原始插入顺序。

JavaScript
class LRUCache {
  constructor(capacity) {
    this.cap = capacity
    this.map = new Map()
  }

  get(key) {
    if (!this.map.has(key)) return -1
    // 存在
    const buf = this.map.get(key)
    this.map.delete(key)
    this.map.set(key, buf)
    return buf
  }

  put(key, val) {
    if (this.map.has(key)) this.map.delete(key)
    this.map.set(key, val)
    if (this.map.size > this.cap) {
      // 按顺序插入，故第一个键就是被淘汰的值
      this.map.delete(this.map.keys().next().value)
    }
  }
}

数据结构应用 ​

leetcode
  1. LRU缓存