{"id":2636,"date":"2026-01-23T11:57:30","date_gmt":"2026-01-23T03:57:30","guid":{"rendered":"https:\/\/womeifei.cn\/?p=2636"},"modified":"2026-01-23T17:03:11","modified_gmt":"2026-01-23T09:03:11","slug":"lru%e7%bc%93%e5%ad%98-%e5%8f%8c%e5%90%91%e9%93%be%e8%a1%a8","status":"publish","type":"post","link":"https:\/\/womeifei.cn\/index.php\/2026\/01\/23\/lru%e7%bc%93%e5%ad%98-%e5%8f%8c%e5%90%91%e9%93%be%e8%a1%a8\/","title":{"rendered":"LRU\u7f13\u5b58 — \u53cc\u5411\u94fe\u8868 + HashMap"},"content":{"rendered":"\n

LRU\u7f13\u5b58 — \u8be6\u7ec6\u601d\u8def\u548c\u5e94\u7528<\/a><\/p>\n\n\n\n

class Node {\n    constructor(key = 0, value = 0) {\n        this.key = key;\n        this.value = value;\n        this.prev = null;\n        this.next = null;\n    }\n}\n\nclass LRUCache {\n    constructor(capacity) {\n        this.capacity = capacity;\n        this.dummy = new Node(); \/\/ \u54e8\u5175\u8282\u70b9\n        this.dummy.prev = this.dummy;\n        this.dummy.next = this.dummy;\n        this.keyToNode = new Map();\n    }\n\n    \/\/ \u83b7\u53d6 key \u5bf9\u5e94\u7684\u8282\u70b9\uff0c\u540c\u65f6\u628a\u8be5\u8282\u70b9\u79fb\u5230\u94fe\u8868\u5934\u90e8\n    #getNode(key) {\n        if (!this.keyToNode.has(key)) { \/\/ \u6ca1\u6709\u8fd9\u672c\u4e66\n            return null;\n        }\n        const node = this.keyToNode.get(key); \/\/ \u6709\u8fd9\u672c\u4e66\n        this.#remove(node); \/\/ \u628a\u8fd9\u672c\u4e66\u62bd\u51fa\u6765\n        this.#pushFront(node); \/\/ \u653e\u5230\u6700\u4e0a\u9762\n        return node;\n    }\n\n    get(key) {\n        const node = this.#getNode(key); \/\/ getNode \u4f1a\u628a\u5bf9\u5e94\u8282\u70b9\u79fb\u5230\u94fe\u8868\u5934\u90e8\n        return node ? node.value : -1;\n    }\n\n    put(key, value) {\n        let node = this.#getNode(key); \/\/ getNode \u4f1a\u628a\u5bf9\u5e94\u8282\u70b9\u79fb\u5230\u94fe\u8868\u5934\u90e8\n        if (node) { \/\/ \u6709\u8fd9\u672c\u4e66\n            node.value = value; \/\/ \u66f4\u65b0 value\n            return;\n        }\n        node = new Node(key, value) \/\/ \u65b0\u4e66\n        this.keyToNode.set(key, node);\n        this.#pushFront(node); \/\/ \u653e\u5230\u6700\u4e0a\u9762\n        if (this.keyToNode.size > this.capacity) { \/\/ \u4e66\u592a\u591a\u4e86\n            const backNode = this.dummy.prev;\n            this.keyToNode.delete(backNode.key);\n            this.#remove(backNode); \/\/ \u53bb\u6389\u6700\u540e\u4e00\u672c\u4e66\n        }\n    }\n\n    \/\/ \u5220\u9664\u4e00\u4e2a\u8282\u70b9\uff08\u62bd\u51fa\u4e00\u672c\u4e66\uff09\n    #remove(x) {\n        x.prev.next = x.next;\n        x.next.prev = x.prev;\n    }\n\n    \/\/ \u5728\u94fe\u8868\u5934\u6dfb\u52a0\u4e00\u4e2a\u8282\u70b9\uff08\u628a\u4e00\u672c\u4e66\u653e\u5230\u6700\u4e0a\u9762\uff09\n    #pushFront(x) {\n        x.prev = this.dummy;\n        x.next = this.dummy.next;\n        x.prev.next = x;\n        x.next.prev = x;\n    }\n}\n\n\/\/ \u521b\u5efa\u5bb9\u91cf\u4e3a2\u7684LRU\u7f13\u5b58\nconst cache = new LRUCache(2);\n\n\/\/ \u5b58\u5165\u6570\u636e\ncache.put(1, \"\u82f9\u679c\");\ncache.put(2, \"\u9999\u8549\");\n\n\/\/ \u83b7\u53d6\u6570\u636e\nconsole.log(cache.get(1));    \/\/ \u8f93\u51fa: \"\u82f9\u679c\"\nconsole.log(cache.get(2));    \/\/ \u8f93\u51fa: \"\u9999\u8549\"\nconsole.log(cache.get(3));    \/\/ \u8f93\u51fa: -1 (key\u4e0d\u5b58\u5728)\n\n\/\/ \u5f53\u5bb9\u91cf\u8d85\u8fc7\u65f6\uff0c\u6dd8\u6c70\u6700\u4e45\u672a\u4f7f\u7528\u7684\ncache.put(3, \"\u6a59\u5b50\");  \/\/ \u52a0\u5165\u7b2c\u4e09\u4e2a\u5143\u7d20\uff0c\u6dd8\u6c70key=1\nconsole.log(cache.get(1));    \/\/ \u8f93\u51fa: -1 (\u5df2\u88ab\u6dd8\u6c70)\nconsole.log(cache.get(2));    \/\/ \u8f93\u51fa: \"\u9999\u8549\" (\u8fd8\u5728\u7f13\u5b58\u4e2d)\nconsole.log(cache.get(3));    \/\/ \u8f93\u51fa: \"\u6a59\u5b50\"\n\n\/\/ \u518d\u6b21\u83b7\u53d6key=2\uff0c\u4f7f\u5176\u53d8\u4e3a\u6700\u8fd1\u4f7f\u7528\nconsole.log(cache.get(2));    \/\/ \u8f93\u51fa: \"\u9999\u8549\" (\u53d8\u4e3a\u6700\u8fd1\u4f7f\u7528\u7684)\n\ncache.put(4, \"\u8461\u8404\");  \/\/ \u52a0\u5165\u7b2c\u56db\u4e2a\u5143\u7d20\uff0c\u6dd8\u6c70key=3\nconsole.log(cache.get(3));    \/\/ \u8f93\u51fa: -1 (\u5df2\u88ab\u6dd8\u6c70)\nconsole.log(cache.get(2));    \/\/ \u8f93\u51fa: \"\u9999\u8549\" (\u8fd8\u5728\u7f13\u5b58\u4e2d)\nconsole.log(cache.get(4));    \/\/ \u8f93\u51fa: \"\u8461\u8404\"<\/code><\/pre>\n\n\n\n
<\/p>\n","protected":false},"excerpt":{"rendered":"
LRU\u7f13\u5b58 — \u8be6\u7ec6\u601d\u8def\u548c\u5e94\u7528<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[10,1,4,6,7],"tags":[],"class_list":["post-2636","post","type-post","status-publish","format-standard","hentry","category-javascript","category-1","category-4","category-6","category-7"],"_links":{"self":[{"href":"https:\/\/womeifei.cn\/index.php\/wp-json\/wp\/v2\/posts\/2636","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/womeifei.cn\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/womeifei.cn\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/womeifei.cn\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/womeifei.cn\/index.php\/wp-json\/wp\/v2\/comments?post=2636"}],"version-history":[{"count":7,"href":"https:\/\/womeifei.cn\/index.php\/wp-json\/wp\/v2\/posts\/2636\/revisions"}],"predecessor-version":[{"id":2647,"href":"https:\/\/womeifei.cn\/index.php\/wp-json\/wp\/v2\/posts\/2636\/revisions\/2647"}],"wp:attachment":[{"href":"https:\/\/womeifei.cn\/index.php\/wp-json\/wp\/v2\/media?parent=2636"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/womeifei.cn\/index.php\/wp-json\/wp\/v2\/categories?post=2636"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/womeifei.cn\/index.php\/wp-json\/wp\/v2\/tags?post=2636"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}