算法就像搭乐高：带你手撸 LRU 算法 :: labuladong的算法小抄

[utterances-bot]

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

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

[zhuifengshaonian201]

非常好～

[wenxiong-xu]

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

[alexyuisme]

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

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

[Lucoin-yf]

不需要，因为调用removeLeastRecently(), 是在未来使用LRUCache容量满的情况下才会使用该函数移除头部元素

[ngokchaoho]

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

[labuladong]

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

[5Reasons]

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)
        }
    }
};

[5Reasons]

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

[XinranLiu2001]

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

[wangpeng1994]

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

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

[YiwenXie]

太厉害了

[yokiizx]

js...手撸

[Plasticine-Yang]

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);
    }
  }
}

[fantian007]

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

[615lyw]

看了下 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;
        }
    }
}

[shiboys]

这个是 LinkedHashMap 给 LRU 功能专门留出来的一个口子，阿东这个基本上没有用到这个强大的功能，不过手撸更适合锻炼

[shawn120]

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

[XiaofanLinUS]

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

[XiaofanLinUS]

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;
    }

[labuladong]

没关系的，因为 node 是引用，你 set 到 map 里面的还是之前的那个 node

[chloepei867]

啊！primitive type和reference type的区别

[yonggui-yan]

打卡！

[chloepei867]

打卡打卡！看完了，打算自己手写一遍！

[ghost]

我想问一下在get方法中为什么直接用LinkedHashMap中的get方法没有进行位置的变换？：
int param_1 = cache.get(key);
return param_1;

“LinkedHashMap中重写了HashMap的get方法,不止会取出所索要的节点的值,而且会调整LinkedHashMap中内置的链表中该键所对应的节点的位置,将该节点置为链表的尾部。”

谢谢！

[ok8722971]

用c++比較傳統的方法實現
結果TLE了
找了一下discuss裡面三種類似的實作doubly linked list也都TLE
沒啥頭緒

class LRUCache {
public:
    LRUCache(int capacity):cache(), capacity(capacity){}
    int get(int key) {
        if(hmap.find(key) == hmap.end()) {
            return -1;
        }
        cache.removeNode(hmap[key]);
        cache.addNewNode(hmap[key]);
        return hmap[key]->val;
    }
    
    void put(int key, int value) {
        // 沒找到
        if(hmap.find(key) == hmap.end()) {
            if(cache.size() == capacity) {
                node *oldnode = cache.removeFirstNode();
                hmap.erase(oldnode->key);
                delete(oldnode);
            }
            node *nnode = new node(key, value);
            cache.addNewNode(nnode);
            hmap.insert({key, nnode});
        }
        // 找到
        else {            
            node *n = hmap[key];
            n->val = value;
            cache.removeNode(n);
            cache.addNewNode(n);
        }
    }
    
private:     
    class node {
    public:
        node(int key, int val):key(key),val(val),prev(nullptr), next(nullptr){}
        int val;
        int key;
        node *prev;
        node *next;
    };
    
    class doublylinkedlist{
    public:
        doublylinkedlist():sz(0) {
            head = new node(-1,-1);
            tail = new node(-1,-1);
            head->next = tail;
            tail->prev = head;
        }
        
        void removeNode(node *rnode) {
            rnode->next->prev = rnode->prev;
            rnode->prev->next = rnode->next;
            --sz;
        }
        
        void addNewNode(node *nnode) {
            nnode->prev = tail->prev;
            nnode->next = tail;
            tail->prev->next = nnode;
            tail->prev = nnode;
            ++sz;
        }
        
        node* removeFirstNode() {
            if(head->next == tail) return nullptr;
            node *rnode = head->next;
            removeNode(rnode);
            return rnode;
        }
        
        int size() {return sz;}
    private:
        node *head;
        node *tail;
        int sz;
    };
    
    unordered_map<int, node*> hmap;
    doublylinkedlist cache;
    int capacity;
};

[NoOneHero]

golang实现

type LRUCache struct {
	memo map[int]*Node
	head *Node // 头尾虚节点
	tail *Node
	cap  int
}

func Constructor(capacity int) LRUCache {
	head, tail := &Node{}, &Node{}
	head.next, tail.prev = tail, head
	return LRUCache{memo: make(map[int]*Node), head: head, tail: tail, cap: capacity}
}

func (this *LRUCache) Get(key int) int {
	node := this.memo[key]
	if node == nil {
		return -1
	}
	// 更新为最新访问
	this.makeRecently(node)
	return node.value
}

func (this *LRUCache) Put(key int, value int) {
	if node, isPresent := this.memo[key]; isPresent {
		node.value = value
		// 更新为最新访问
		this.makeRecently(node)
	} else {
		if len(this.memo) >= this.cap {
			// 达到最大容量
			// 移除首个节点
			this.remove(this.head.next)
		}
		this.addLast(&Node{key: key, value: value})
	}
}

func (this *LRUCache) makeRecently(node *Node) {
	// 移除
	this.remove(node)
	// 放到队尾
	this.addLast(node)
}

func (this *LRUCache) remove(node *Node) {
	delete(this.memo, node.key)
	node.prev.next = node.next
	node.next.prev = node.prev
}

func (this *LRUCache) addLast(node *Node) {
	this.memo[node.key] = node
	prev := this.tail.prev
	// node前置节点
	prev.next = node
	node.prev = prev
	// node后置节点
	node.next = this.tail
	this.tail.prev = node
}

type Node struct {
	prev, next *Node
	key        int
	value      int
}

[Showcoding]

面试用LinkedlListHashMap不行吧？

[muxingg]

// C++手动双向链表（没有内存泄漏）

struct Node
{
    Node()
    :key(0), value(0), prev(nullptr), next(nullptr) {}
    Node( int key, int value )
    :key(key), value(value), prev(nullptr), next(nullptr) {}
    // 未书写相应自增自减的运算符重载

    int key;
    int value;
    Node* prev; 
    Node* next;
};

// 双向链表做为容器
class DLinkedList
{
public:
    using iterator = Node*;
public:
    DLinkedList()
    : _head(new Node())
    , _tail(new Node())
    , _size(0)
    {
        // 带头尾虚结点的双向链表
        _head->next = _tail;
        _tail->prev = _head;
    }
    ~DLinkedList()
    {
        // 有 allocate类后，由allocate类回收空间
        // 回收链表申请的堆空间，从后往前删
        Node* last = _tail ;
        Node* cur = last->prev;
        while (cur != nullptr) {         
            delete last;
            last = cur;
            cur = cur->prev;
            // delete cur;  // error 2:释放了堆空间下面又去使用cur，使用已释放的空间；；
            //cur = cur->prev;
        }
        _head = nullptr;
        _tail = nullptr;
        //_alloc.~Allocator();
    }

    Node front() const { return *_head->next; }
    Node back()  const { return *_tail->prev; }
    // [begin, end)
    iterator begin() const { return _head->next; }
    iterator end()   const { return _tail; }

    int size() const { 
        return _size;

        // 标准库中也不是 begin() - end();
        /* 是从链表起始遍历链表，_n = 0; ++_n;
        size_t _n = 0;
        Node* _first = _head->next;
        Node* _last = _tail;
        while (_first != _last) {
            _first = _first->next;
            ++_n;
        }
        return _n;
        //用时更多了，。。。*/
    }

    void addToHead(  const Node& node )
    {
        Node* tmp = new Node(node);
        //Node* tmp = createNode(node);
                /* free(tmp); *1/ */
        
        // 先把新结点与第一个元素连上
        tmp->next = _head->next;
        tmp->prev = _head;
        _head->next->prev = tmp;
        _head->next = tmp;

        // 链表长度加一
        ++_size;
    }

    void removeNode( Node* pNode )
    {
        // 先把前驱与后继连上
        pNode->prev->next = pNode->next;
        pNode->next->prev = pNode->prev;

        // 回收堆空间
        delete pNode; 
        //destroyNode(pNode);
        pNode = nullptr;
        // 链表长度减一
        --_size;
    }

    void moveToHead( Node* pNode )
    {
        // error 1: pNode删除了，再去添加，它已经没有了
        /* removeNode(pNode); */
        /* addToHead(*pNode); */
        // 先把前驱与后继连上
        pNode->prev->next = pNode->next;
        pNode->next->prev = pNode->prev;

        // 再把结点放到头部
        pNode->next = _head->next;
        pNode->prev = _head;
        _head->next->prev = pNode;
        _head->next = pNode;
    }

    void removeTail()
    {
        Node* tmp = _tail->prev;
        removeNode(tmp);
    }

private:
    // 初始化顺序时按什么顺序进行！
    // 头尾虚结点
    // 标准库中是一个头结点类(成员有前驱指针，后继指针)的循环链表
    Node* _head; 
    Node* _tail;
    // 链表元素个数
    int _size;  
};

class LRUCache
{
public:
    LRUCache( int capacity )
    : _capacity(capacity)
    {
    }

    int get( int key )
    {
        if (!_cache.count(key)) {
            // 1、key不存在返回-1
            return -1;
        }
        else {

            // 2、如果key 存在，先通过哈希表定位，再移到头部
            Node* pNode = _cache[key];
            _dlist.moveToHead(pNode);
            return pNode->value;
        }
    }

    void put( int key, int value )
    {
        if (_cache.count(key)) {
            // 2、key 存在
           // 更新 value
           Node* p = _cache[key];
           p->value = value;
           // 放到链表头部
           _dlist.moveToHead(p);
        }
        else {
            // 2、如果 key 不存在，创建一个新的结点，
            // 1）缓存已满
            if (_dlist.size() == _capacity) {
                // 删除哈希表中的项和 双向链表尾部的结点
                int deleteKey = _dlist.back().key;
                /* Node* tmp = _cache[deleteKey]; */
                // point: 先从哈希表中删除，再删链表中相应结点
                // 若先删链表中结点，那么哈希表中该key对应的value指向了未知地方
                _cache.erase(deleteKey);
                _dlist.removeTail();
            }
            // 2)不管缓存满没满，在队头插入新结点
            _dlist.addToHead(Node(key, value)); 
            // 添加进哈希表
            _cache[key] = _dlist.begin();
        }
    }

private:
    DLinkedList _dlist;
    unordered_map<int, DLinkedList::iterator> _cache;
    int _capacity;
};

[bruceeewong]

酷！是一个不算复杂但是实用的算法

[ANewSwift]

使用LinkedHashMap，不用自己写makeRecently，它有个属性accessOrder，初始设置为true，然后get访问时，内部就会把访问的值，提升到最近访问的。

[zhangSun123]

为什么前面说的需要用双链表实现，后面又突然切换回单链表，文中却只字未提转换的原因，这种没有语言过渡的感觉给人一种复制粘贴、毫无思考的廉价感。我发现后面的文章没有前面的文章打磨的细。当然，我只是提个建议，毕竟这个系列很棒！

[juexingyezuile]

看 JAVA 代码吧。
我开始看的 C++ 代码，整篇文章看的一头雾水，各种地方牛头不对马嘴。

[zhangSun123]

这是来自QQ邮箱的自动回复邮件。你好，你的邮件我主人的QQ邮箱已收到，但是主人无法马上回复你的邮件。我会提醒主人，尽快给你回复。

[zhangSun123]

这是来自QQ邮箱的自动回复邮件。你好，你的邮件我主人的QQ邮箱已收到，但是主人无法马上回复你的邮件。我会提醒主人，尽快给你回复。

[larry0442]

完整代码： leetcode 146 通过

// 节点设计
var node = function(k, v) {
    this.key = k;
    this.val = v;
    this.prev = null;
    this.next = null;
}

// 双链表设计
var DoubleList = function() {
    // 头尾虚拟节点
    this.head = new node(0,0);
    this.tail = new node(0,0);
    this.size = 0;
    // 初始化双链表数据
    this.head.next = this.tail;
    this.tail.prev = this.head;
}
DoubleList.prototype.addLast = function(x) {
    // 注意链接顺序
    this.tail.prev.next = x;
    x.next = this.tail;
    x.prev = this.tail.prev;
    this.tail.prev = x;
    this.size++;
}

DoubleList.prototype.remove = function(x) {
    x.prev.next = x.next;
    x.next.prev = x.prev;
    this.size--;
}

DoubleList.prototype.removeFirst = function() {

    if(this.head.next == this.tail) {
        return null;
    }
    var first = this.head.next;
    this.remove(first);
    return first;
}

DoubleList.prototype.size = function() {
    return this.size;
}

/**
 * @param {number} capacity
 */
var LRUCache = function(capacity) {
    this.map = new Map();
    this.cache = new DoubleList();
    this.cap = capacity;

    this.makeRecently = function(key) {
        var x = this.map.get(key);
        // 先从链表中删除这个节点
        this.cache.remove(x);
        // 重新插到队尾
        this.cache.addLast(x);
    }
    /* 添加最近使用的元素 */
    this.addRecently = function(key, val) {
        var x = new node(key, val);
        // 链表尾部就是最近使用的元素
        this.cache.addLast(x);
        // 别忘了在 map 中添加 key 的映射
        this.map.set(key, x);
    }
     /* 删除某一个 key */
    this.deleteKey = function(key) {
        var x = this.map.get(key);
        // 从链表中删除
        this.cache.remove(x);
        // 从 map 中删除
        this.map.delete(key);
    }

     /* 删除最久未使用的元素 */
    this.removeLeastRecently = function() {
        // 链表头部的第一个元素就是最久未使用的
        var deletedNode = this.cache.removeFirst();
        // 同时别忘了从 map 中删除它的 key
        if(deletedNode != null) {
            var deletedKey = deletedNode.key;
            this.map.delete(deletedKey);
        }
        
    }
};

/** 
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function(key) {
    if(!this.map.has(key)) {
        return -1;
    }
    this.makeRecently(key);
    return this.map.get(key).val;
};

/** 
 * @param {number} key 
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function(key, val) {
    if (this.map.has(key)) {
      // 删除旧的数据
      this.deleteKey(key);
      // 新插入的数据为最近使用的数据
      this.addRecently(key, val);
      return;
    }

    if (this.cap === this.cache.size) {
      // 删除最久未使用的元素
      this.removeLeastRecently();
    }
    // 添加为最近使用的元素
    this.addRecently(key, val);
};

/**
 * 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)
 */

[zhangSun123]

这是来自QQ邮箱的自动回复邮件。你好，你的邮件我主人的QQ邮箱已收到，但是主人无法马上回复你的邮件。我会提醒主人，尽快给你回复。