{"action":"opened","issue":{"url":"https://api.github.com/repos/13030112030/blog/issues/1","repository_url":"https://api.github.com/repos/13030112030/blog","labels_url":"https://api.github.com/repos/13030112030/blog/issues/1/labels{/name}","comments_url":"https://api.github.com/repos/13030112030/blog/issues/1/comments","events_url":"https://api.github.com/repos/13030112030/blog/issues/1/events","html_url":"https://github.com/13030112030/blog/issues/1","id":448012098,"node_id":"MDU6SXNzdWU0NDgwMTIwOTg=","number":1,"title":"LRU Cache","user":{"login":"13030112030","id":31573022,"node_id":"MDQ6VXNlcjMxNTczMDIy","avatar_url":"https://avatars1.githubusercontent.com/u/31573022?v=4","gravatar_id":"","url":"https://api.github.com/users/13030112030","html_url":"https://github.com/13030112030","followers_url":"https://api.github.com/users/13030112030/followers","following_url":"https://api.github.com/users/13030112030/following{/other_user}","gists_url":"https://api.github.com/users/13030112030/gists{/gist_id}","starred_url":"https://api.github.com/users/13030112030/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/13030112030/subscriptions","organizations_url":"https://api.github.com/users/13030112030/orgs","repos_url":"https://api.github.com/users/13030112030/repos","events_url":"https://api.github.com/users/13030112030/events{/privacy}","received_events_url":"https://api.github.com/users/13030112030/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":0,"created_at":"2019-05-24T07:07:51Z","updated_at":"2019-05-24T07:07:51Z","closed_at":null,"author_association":"OWNER","body":"LRU是内存管理的算法，以下引入一段百科的简单介绍\r\n\r\n> 内存管理的一种页面置换算法，对于在内存中但又不用的数据块（内存块）叫做LRU，操作系统会根据哪些数据属于LRU而将其移出内存而腾出空间来加载另外的数据。\r\n什么是LRU算法？ LRU是Least Recently Used的缩写，即最近最少使用，常用于页面置换算法，是为虚拟页式存储管理服务的。\r\n### 简述\r\n比如有一个内存队列，LRU算法的主要特点就是**最近被访问到的内存**会放在这段**内存队列的首位**，如果有新的内容要放入内存里，则新建一段内存放入队列中，再检查内存队列的容量，内容都是有容量了，如果超出了内容队列的容量，则把内容队列**最久未被访问的那段内存**移出队列。\r\n### sample\r\n```js\r\ncache = [];\r\ncache maxSize = 3\r\n// cache 最多只能放三个\r\ncache.set(1)\r\ncache: [1]\r\ncache.set(2)\r\ncache: [2, 1]\r\ncache.get(1)\r\ncache: [1,2]\r\n// 1 被访问了移到首位\r\ncache.set(3)\r\ncache: [3,1,2]\r\ncache.set(4)\r\n// 这时cache里已有3个内存 就需要把最久为访问的移出队列 腾出空间\r\ncache: [4,3,1] // 把末尾的2去掉了\r\n```\r\n### problem\r\n实现这个LRU Cache还要考虑到内存队列是会经常被存取的，存取后还可能溢出队列容量需要对内存队列做一个更新维护，普通的遍历来进行这些操作是很耗时的，leetCode上也有关于LRU Cache的题目[146. LRU Cache](https://leetcode.com/problems/lru-cache/)。\r\n下面是用双向链表+hashMap js实现的LRU Cache在O(1)的时间完成更新优先级、删除、插入新内存的操作\r\n### code\r\n\r\n```js\r\n/**\r\n * @param {number} capacity\r\n */\r\nfunction Node(key, val) {\r\n    this.key = key\r\n    this.val = val\r\n    this.prev = this.next = null\r\n}\r\n// 把内存从内存队列中切出来 把指向该内存的关联去掉\r\nfunction cutNode(node) {\r\n    node.next.prev = node.prev;\r\n    node.prev.next = node.next;\r\n}\r\n\r\nvar LRUCache = function(capacity) {\r\n    this.map = new Map()\r\n    this.capacity = capacity\r\n    this.head = new Node('head', 'head')\r\n    this.tail = new Node('tail', 'tail')\r\n    this.head.next = this.tail\r\n    this.tail.next = this.head\r\n};\r\n\r\n/** \r\n * @param {number} key\r\n * @return {number}\r\n */\r\nLRUCache.prototype.get = function(key) {\r\n    if (!this.map.has(key)) {\r\n        return -1;\r\n    }\r\n    const node = this.map.get(key);\r\n    cutNode(node)\r\n    this.updateHead(node);\r\n    \r\n    return node.val;\r\n};\r\n\r\n\r\n\r\nLRUCache.prototype.updateHead = function(node) {\r\n    const head = this.head;\r\n    node.prev = head;\r\n    node.next = head.next;\r\n    head.next.prev = node;\r\n    head.next = node;\r\n};\r\n\r\nLRUCache.prototype.removeTail = function() {\r\n    const tail = this.tail.prev;\r\n    tail.next = null;\r\n    if (tail.prev) {\r\n        tail.prev.next = this.tail;\r\n        this.tail.prev = tail.prev;\r\n    }\r\n};\r\n\r\n/** \r\n * @param {number} key \r\n * @param {number} value\r\n * @return {void}\r\n */\r\nLRUCache.prototype.put = function(key, value) {\r\n    if (this.map.has(key)) {\r\n        const node = this.map.get(key);\r\n        node.val = value;\r\n        cutNode(node)\r\n        this.updateHead(node);\r\n        return\r\n    }\r\n    const node = new Node(key, value);\r\n    this.map.set(key, node);\r\n    \r\n    this.updateHead(node);\r\n    \r\n    if (this.map.size > this.capacity) {\r\n        this.map.delete(this.tail.prev.key);\r\n        this.removeTail();\r\n    }\r\n    \r\n};\r\n```"}}
{"actor":{"display_login":"13030112030"}}