文章链接点这里：算法就像搭乐高：带你手撸 LRU 算法

评论礼仪 见这里，违者直接拉黑。

非常好～

东哥真是666，想不出别的语言了

private void removeLeastRecently() { // 链表头部的第一个元素就是最久未使用的 Node deletedNode = cache.removeFirst(); // 同时别忘了从 map 中删除它的 key int deletedKey = deletedNode.key; map.remove(deletedKey); }

cache.removeFirst() 有可能返回空值, 删除之前需要判空吗?

由於只有一種方法去插入而且每次都會檢查是否需要刪除， if (cache.size() >= this.cap) { 我認為應該可改成 if (cache.size() == this.cap) { 原本的寫法是擔心特殊的刪除失敗的情況嗎？如此一來是否用While會更好？

@ngokchaoho 这是一种编程习惯罢了，可以改成 ==

JS代码供参考

class Node{
    constructor(key,value){
        this.key = key
        this.value = value
    }
}
class DoubleList{
    constructor(){
        // 头、尾的虚拟节点
        this.head = new Node(0,0)
        this.tail = new Node(0,0)
        this.head.next = this.tail
        this.tail.prev = this.head
        this.size = 0
    }
    addLast(node){
        node.prev = this.tail.prev
        node.next = this.tail
        this.size++
        this.tail.prev.next = node
        this.tail.prev = node
    }
    removeNode(node){
        node.prev.next = node.next
        node.next.prev = node.prev
        this.size--
        return node.key
    }
    removeFirst(){
        if(this.head.next == this.tail)
            return null
        return this.removeNode(this.head.next)
    }
}
/**
 * @param {number} capacity
 */
var LRUCache = function(capacity) {
    this.hash = new Map()
    this.cache = new DoubleList()
    this.capacity = capacity
};

/** 
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function(key) {
    // console.log('get',key)
    if(this.hash.has(key)){
        // get要调整顺序
        let moveNode = this.hash.get(key)
        this.cache.removeNode(moveNode)
        this.cache.addLast(moveNode)
        
        return this.hash.get(key).value
    }
    else
        return -1
};

/** 
 * @param {number} key 
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function(key, value) {
    // console.log('push',key,value)
    // hash表中已经有了
    if(this.hash.has(key)){
        let moveNode = this.hash.get(key)
        this.cache.removeNode(moveNode)
        let newNode = new Node(key,value)
        this.cache.addLast(newNode)
        this.hash.set(key,newNode)
    } 
    // hash表中没有
    else {
        // 超出容量，删除头节点，然后追加在尾部
        if(this.cache.size == this.capacity){
            let deleted = this.cache.removeFirst()
            this.hash.delete(deleted)

            let newNode = new Node(key,value)
            this.cache.addLast(newNode)
            this.hash.set(key,newNode)
        }
        // 未超出容量，直接追加
        else {
            let newNode = new Node(key,value)
            this.cache.addLast(newNode)
            this.hash.set(key,newNode)
        }
    }
};

上面代码没有把 makeRecently、addRecently 这些方法提出来，直接在LRU的get、put方法里操作 hashMap和双向链表了 不过应该还算能看懂（js真的..优先级队列、哈希链表都必须纯手撸 还是java刷题比较友好

put()里面的makeRecently是不是可以不用啊

put()里面的makeRecently是不是可以不用啊

要的，put 里的那个 makeRecently 是判断了 key 已经存在于目前数据结构中，第一次put只是更新值，应该不会改变位置，所以要再调 makeRecently 来把更新后的值重新 put 到链表尾部。 个人理解

太厉害了

js...手撸

TypeScript 实现 LRU

class DNode {
  // 结点存储的数据为 key - value
  public key: number;
  public value: number;
  // 指向前驱和后继
  public prev: DNode | null;
  public next: DNode | null;

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

/** 双向链表 */
class DoubleLinkedList {
  // 虚拟头尾结点
  private head: DNode;
  private tail: DNode;

  public size: number = 0;

  constructor() {
    // 初始化虚拟头尾结点
    this.head = new DNode(-1, -1);
    this.tail = new DNode(-1, -1);
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }

  /**
   * @description 在双向链表末尾插入结点
   * @param node 待添加的结点
   */
  public addLast(node: DNode): void {
    // 将 node 插入到最后
    node.prev = this.tail.prev;
    node.next = this.tail;
    // 将 tail 的指针修正
    this.tail.prev!.next = node;
    this.tail.prev = node;
    this.size++;
  }

  /**
   * @description 将结点从双向链表中移除
   * @param node 待移除的结点
   */
  public remove(node: DNode): void {
    node.prev!.next = node.next;
    node.next!.prev = node.prev;
    this.size--;
  }

  /**
   * @description 移除双向链表的第一个结点
   */
  public removeFirst(): DNode | null {
    if (this.head.next === this.tail) {
      // 双向链表为空则没法移除
      return null;
    }

    const first = this.head.next;
    this.remove(first!);

    return first;
  }
}

class LRUCache {
  private capacity: number;
  private map: Map<number, DNode>;
  private cache: DoubleLinkedList;

  constructor(capacity: number) {
    this.capacity = capacity;
    this.map = new Map();
    this.cache = new DoubleLinkedList();
  }

  private makeRecently(key: number): void {
    // 从哈希表中获取到双向链表结点
    const node = this.map.get(key);
    if (node) {
      // 将其从链表中删除
      this.cache.remove(node);
      // 再将其插入到尾部 表示最近使用过
      this.cache.addLast(node);
    }
  }

  /**
   * @description 删除 key 的时候统一从哈希表和双向链表中删除
   * @param key 待删除的 key
   */
  private deleteKey(key: number): void {
    const node = this.map.get(key);
    if (node) {
      this.map.delete(key);
      this.cache.remove(node);
    }
  }

  /**
   * @description 添加元素并让其成为最近使用过的
   */
  private addRecently(key: number, value: number): void {
    const node = new DNode(key, value);
    this.cache.addLast(node);
    this.map.set(key, node);
  }

  /**
   * @description 移除最近最久未使用的结点 要在 map 和链表中都移除
   */
  private removeLeastRecently(): void {
    const node = this.cache.removeFirst();
    node && this.map.delete(node.key);
  }

  get(key: number): number {
    const node = this.map.get(key);
    if (node) {
      this.makeRecently(key);
      return node.value;
    } else {
      return -1;
    }
  }

  put(key: number, value: number): void {
    const node = this.map.get(key);
    if (node) {
      // 删除旧数据
      this.deleteKey(key);
      // 新插入的数据作为最近使用过的
      this.addRecently(key, value);
    } else {
      // 新增的元素 要注意是否超出容量
      if (this.cache.size >= this.capacity) {
        this.removeLeastRecently();
      }

      // 把元素添加 作为最近使用过的键值对
      this.addRecently(key, value);
    }
  }
}

js 的 map 天然具有 hash + 顺序的特性，可以用来实现 LRU，但是本文的思路值得学习，还是以本文答案为准吧

/*
 * @lc app=leetcode.cn id=146 lang=typescript
 *
 * [146] LRU 缓存
 * 利用 Map 键具有顺序的特性
 */

// @lc code=start
class LRUCache {
    cache: Map<number, number> = new Map();
    capacity: number = 0;

    constructor(capacity: number) {
        this.capacity = capacity;
    }

    get(key: number): number {
        if (this.cache.has(key)) {
            const v = this.cache.get(key);

            // 先删除，再插入，放入最后的位置
            this.cache.delete(key);
            this.cache.set(key, v);

            return v;
        }

        return -1;
    }

    put(key: number, value: number): void {
        if (this.cache.has(key)) {
            this.cache.delete(key);
        } else {
            if (this.cache.size >= this.capacity) {
                // 最久的 key
                const firstKey = this.cache.keys().next().value;

                this.cache.delete(firstKey);
            }
        }

        this.cache.set(key, value);
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * var obj = new LRUCache(capacity)
 * var param_1 = obj.get(key)
 * obj.put(key,value)
 */
// @lc code=end

看了下 LinkedHashMap 实现，发现还可以这样写，挺有意思的：

class LRUCache {
    int cap;
    LRULinkedHashMap<Integer, Integer> cache;

    public LRUCache(int capacity) {
        this.cap = capacity;
        // 最后一个参数 true 表示按访问排序
        this.cache = new LRULinkedHashMap<>(capacity, 0.75F, true);
    }
    
    public int get(int key) {
        if (cache.get(key) == null) {
            return -1;
        }
        return cache.get(key);
    }
    
    public void put(int key, int value) {
        cache.put(key, value);
    }

    private class LRULinkedHashMap<K, V> extends LinkedHashMap<K, V> {

        public LRULinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {
            super(initialCapacity, loadFactor, accessOrder);
        }

        @Override
        protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
            return size() > cap;
        }
    }
}

python实现

class LRUCache:

    def __init__(self, capacity: int):
        self.map = {}
        self.cache = DoubleList()
        self.cap = capacity
        
    def get(self, key: int) -> int:
        if key not in self.map:
            return -1
        
        self.makeRecently(key)
        return self.map[key].val

    def put(self, key: int, value: int) -> None:
        if key in self.map:
            self.deleteKey(key)
            self.addRecently(key, value)
            return
        
        if self.cap == self.cache.size:
            self.removeLeastRecently()
        
        self.addRecently(key,value)
        return
        
    def makeRecently(self, key):
        temp = self.map[key]
        self.cache.remove(temp)
        self.cache.addLast(temp)
    
    def addRecently(self, key, val):
        temp = Node(key, val)
        self.cache.addLast(temp)
        self.map[key] = temp
    
    def deleteKey(self, key):
        temp = self.map[key]
        self.cache.remove(temp)
        del self.map[key]
    
    def removeLeastRecently(self):
        temp = self.cache.removeFirst()
        temp_key = temp.key
        del self.map[temp_key]
    
    
class Node:
    def __init__(self, key, val):
        self.key = key
        self.val = val
        self.next = None
        self.prev = None

class DoubleList:
    def __init__(self):
        self.head = Node(0,0)
        self.tail = Node(0,0)
        self.head.next = self.tail
        self.tail.prev = self.head
        self.size = 0
    
    def addLast(self, new_node: Node):
        new_node.prev = self.tail.prev
        new_node.next = self.tail
        self.tail.prev.next = new_node
        self.tail.prev = new_node
        self.size += 1
    
    def remove(self, node: Node):
        node.prev.next = node.next
        node.next.prev = node.prev
        node.prev = None
        node.next = None
        self.size -= 1
    
    def removeFirst(self):
        if self.head.next == self.tail:
            return None

        first = self.head.next
        self.remove(first)
    
        return first

来个最夸张的Java LinkedHashMap版本，没有一丝操作，所以面试也不可以用，lol Constructor的参数分别是初始容量，扩容的比例阈值（0～1），排序机制——true按访问排序，false按插入排序 因为容量最大只会到capacity+1，所以设置初始容量capacity+2和100%阈值，就永远不会扩容了。

class LRUCache {
    private LinkedHashMap<Integer, Integer> map;
    
    public LRUCache(int capacity) {
        map = new LinkedHashMap<>(capacity + 2, 1, true) {
            protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
                return size() > capacity;
            }
        };
    }

    public int get(int key) {
        return map.getOrDefault(key, -1);
    }
    
    public void put(int key, int value) {
        map.put(key, value);
    }
}

东哥，你的makeRecently没有更新hash table里面的node， 你删了和更新了链表的node却没有更新table下面key对应的node

get_recent(key: number): number {
        let node = this.hashmap.get(key);
        if(node == undefined) return -1;
        this.list.delete(node);
        node = this.list.push(node.key, node.val);
        this.hashmap.set(key, node);
        return node.val;
    }