【前端热知识】一步步教你如何实现LRU

前言

了解到 LRU 其实我还是从 vue 的 <keep-alive> 知道这玩意的，大概知道怎么个流程，也能基于es6提供的 Map 写出来。

但是今天刷leetcode发现了这道题，偶然看了下题解发现这题的优解是 哈希表 + 双向链表，然后就火速的更新了一下我的知识库，把这个过程分享给大伙。

思考过程

我们先通过最简单的容量为1的例子来分析：

可以看到我们通过双向链表来存储的话，无论是插入节点，还是删除节点的时间复杂度都是O(1)

逐步实现

0、基础准备

// 实现双向链表的节点类
class Node {
  public prev: Node | null;
  public next: Node | null;

  constructor(public key: number, public value: number) {
    this.prev = null;
    this.next = null;
  }
}

export class LRU {
  //  哑结点
  public dummy: Node;
  //  哈希表，通过key找到节点
  public keyToMap: Map<number, Node>;

  constructor(public capacity: number) {
    this.dummy = new Node(-1, -1);
    this.dummy.prev = this.dummy;
    this.dummy.next = this.dummy;
    this.keyToMap = new Map();
  }

  get(key: number) {

  }

  put(key: number, value: number) {

  }
  
  //  获取最旧的节点
  getOldestNode() {
    return this.dummy.prev;
  }

  //  将节点从链表中移除
  remove(node: Node) {
    node.prev!.next = node.next;
    node.next!.prev = node.prev;
  }

  //  将节点塞到链表头部(哑结点之后)
  putFront(node: Node) {
    node.next = this.dummy.next;
    node.prev = this.dummy;

    this.dummy.next!.prev = node;
    this.dummy.next = node;
  }
}

1、实现基础的get和put

先看测试用例，就是可以存进去再取出来

it('should can put and get', () => {
  const cache = new LRU(2);

  cache.put(1, 1);

  expect(cache.get(1)).toBe(1);
});

实现

export class LRU {
  // ...
  get(key: number) {
    const node = this.keyToMap.get(key);
    return node ? node.value : -1;
  }

  put(key: number, value: number) {
    const node = new Node(key, value);
    this.keyToMap.set(key, node);
    this.putFront(node);
  }
  //  ...
}

2、当设置的key超过容量会删除旧的key

it.skip('should delete old keys when capacity is over than limit', () => {
  const cache = new LRU(2);

  cache.put(1, 1);
  cache.put(2, 2);
  
  cache.put(3, 3);  // 此时会替换成[3,2]
  cache.put(4, 4);  // 此时会替换成[4,3]

  expect(cache.get(1)).toBe(-1);
  expect(cache.get(2)).toBe(-1);
});

export class LRU {
  // ...
  put(key: number, value: number) {
    const node = new Node(key, value);
    this.keyToMap.set(key, node);
    this.putFront(node);

    //  大于容量，需要获取链表中最后一个节点删除（即哑结点的前一个）
    if (this.keyToMap.size > this.capacity) {
      const oldestNode = this.getOldestNode()!;
      this.remove(oldestNode);
      this.keyToMap.delete(oldestNode.key);
    }
  }
  //  ...
}
  

3、当访问旧的key值会将其重新放到前面

it('should get will let key to be latest key', () => {
  const cache = new LRU(2);

  cache.put(1, 1);
  cache.put(2, 2);
  cache.put(3, 3);  // 此时为 [3,2]
   
  cache.get(2); // 此时为 [2,3]
  cache.put(4, 4);  // 此时为 [4,2]

  expect(cache.get(2)).toBe(2);
  expect(cache.get(3)).toBe(-1);
  expect(cache.get(4)).toBe(4);
});

export class LRU {
  // ...
  //  获取节点，并会将其更新为最新的节点
  getNode(key: number) {
    if (!this.keyToMap.has(key))
      return null;

    const node = this.keyToMap.get(key);

    this.remove(node!);
    this.putFront(node!);

    return node;
  }

  get(key: number) {
    const node = this.getNode(key);
    return node ? node.value : -1;
  }
  //  ...
}

4、当给旧的key设置新值时，会将其放到最前面

it('should put will let key to be latest key', () => {
  const cache = new LRU(2);

  cache.put(1, 1);
  cache.put(2, 2);
  cache.put(3, 3); // [(3,3),(2,2)]
  cache.put(2, 4); // [(2,4),(3,3)]
  cache.put(4, 4); // [(4,4),(2,4)]

  expect(cache.get(2)).toBe(4);
  expect(cache.get(3)).toBe(-1);
  expect(cache.get(4)).toBe(4);
});

export class LRU {
  // ...
  put(key: number, value: number) {
    //  调用一下getNode并更新值即可
    let node = this.getNode(key);
    if (node) {
      node.value = value;
      return;
    }

    // const node = new Node(key, value);
    node = new Node(key, value);
    this.keyToMap.set(key, node);
    this.putFront(node);

    //  大于容量，需要获取链表中最后一个节点删除（即哑结点的前一个）
    if (this.keyToMap.size > this.capacity) {
      const oldestNode = this.getOldestNode()!;
      this.remove(oldestNode);
      this.keyToMap.delete(oldestNode.key);
    }
  }
  //  ...
}

结语

done，总体写下来还是很简单的，希望对大家有帮助

参考链接

leetcode原题

github链接