{"id":10021016,"date":"2025-09-25T20:20:36","date_gmt":"2025-09-25T12:20:36","guid":{"rendered":"https:\/\/itmax.cn\/?p=10021016"},"modified":"2025-09-25T20:20:36","modified_gmt":"2025-09-25T12:20:36","slug":"%e5%b7%a5%e4%bd%9c-10-%e5%b9%b4%ef%bc%81redis-%e5%86%85%e5%ad%98%e6%b7%98%e6%b1%b0%e7%ad%96%e7%95%a5-lru-%e5%92%8c%e4%bc%a0%e7%bb%9f-lru-%e5%b7%ae%e5%bc%82%ef%bc%8c%e8%bf%98%e5%82%bb%e5%82%bb%e5%88%86","status":"publish","type":"post","link":"https:\/\/itmax.cn\/?p=10021016","title":{"rendered":"\u5de5\u4f5c 10 \u5e74\uff01Redis \u5185\u5b58\u6dd8\u6c70\u7b56\u7565 LRU \u548c\u4f20\u7edf LRU \u5dee\u5f02\uff0c\u8fd8\u50bb\u50bb\u5206\u4e0d\u6e05"},"content":{"rendered":"

\u5927\u5bb6\u597d\uff0c\u6211\u662f\u5c0f\u5bcc\uff5e<\/strong><\/p>\n

\u9762\u8bd5\u90fd\u80cc\u8fc7\u9053\u516b\u80a1\u9898\uff1aRedis \u7684\u5185\u5b58\u6dd8\u6c70\u7b56\u7565 LRU<\/code> \u548c LFU<\/code> \u662f\u4ec0\u4e48\uff1f\u600e\u4e48\u9009\u597d\uff1f<\/p>\n

\u5f88\u591a\u540c\u5b66\u5bf9\u8fd9\u4e24\u4e2a\u7b97\u6cd5\u7684\u7406\u89e3\uff0c\u53ea\u505c\u7559\u5728\u90fd\u662f\u7f13\u5b58\u6dd8\u6c70\uff0c\u4f46\u8bf4\u4e0d\u6e05\u5b83\u4eec\u5177\u4f53\u533a\u522b\uff0c\u6982\u5ff5\u6df7\u6dc6\uff0c\u66f4\u4e0d\u77e5\u9053\u5b9e\u9645\u573a\u666f\u8be5\u600e\u4e48\u9009\uff1f<\/p>\n

\u800c\u4e14 Redis \u7684 key \u6dd8\u6c70\u7b97\u6cd5\u5176\u5b9e\u8fd8\u4e0d\u662f\u6b63\u7edf<\/strong>\u7684 LRU<\/code> \u548c LFU<\/code> \u7b97\u6cd5\uff0c\u800c\u662f\u57fa\u4e8e LRU\/LFU \u7684\u4e00\u4e2a\u53d8\u79cd\u3002\u6240\u4ee5\u6211\u4eec\u5148\u4e86\u89e3\u4e0b LRU\/LFU \u57fa\u7840\u7b97\u6cd5\uff0c\u518d\u770b\u770b\u5b83\u548c\u53d8\u79cd\u7684 Redis LRU \u7b97\u6cd5\u6709\u4f55\u4e0d\u540c\u3002<\/p>\n

\u4e00\u3001\u4ec0\u4e48\u662f LRU \u7b97\u6cd5\uff1f<\/h2>\n

LRU \u7684\u5168\u79f0\u662f Least Recently Used\uff08\u6700\u8fd1\u6700\u5c11\u4f7f\u7528\uff09\uff0c\u6838\u5fc3\u903b\u8f91\u7279\u522b\u597d\u8bb0\uff1a\u6700\u8fd1\u6ca1\u88ab\u7528\u8fc7\u7684\uff0c\u4e0b\u6b21\u4e5f\u5927\u6982\u7387\u7528\u4e0d\u4e0a<\/strong>\u3002<\/p>\n

\u4e3e\u4e2a\u4f8b\u5b50\uff1a\u4f60\u7535\u8111\u684c\u9762\u4e0a\u653e\u7740\u5e38\u7528\u7684\u8f6f\u4ef6\u56fe\u6807\uff08\u5fae\u4fe1\u3001IDE\uff09\uff0c\u8fd9\u4e9b\u662f\u6700\u8fd1\u5e38\u7528\u7684\uff1b\u800c\u51e0\u4e2a\u6708\u6ca1\u6253\u5f00\u8fc7\u7684\u538b\u7f29\u5de5\u5177\uff0c\u4f1a\u88ab\u4f60\u62d6\u5230\u6587\u4ef6\u5939\u91cc\u3002\u8fd9\u5c31\u662f LRU \u7684\u601d\u8def\uff1a\u4fdd\u7559\u6700\u8fd1\u4f7f\u7528<\/code>\u7684\uff0c\u6dd8\u6c70\u6700\u8fd1\u6700\u5c11\u4f7f\u7528<\/code>\u7684\u3002<\/p>\n

\n

\u5047\u8bbe\u7f13\u5b58\u5bb9\u91cf\u53ea\u6709 3\uff0c\u4f9d\u6b21\u5b58\u5165 A\u3001B\u3001C\uff0c\u6b64\u65f6\u7f13\u5b58\u662f [A,B,C]\uff1b<\/p>\n

\u82e5\u6b64\u65f6\u8bbf\u95ee A\uff08A \u53d8\u6210\u6700\u8fd1\u4f7f\u7528\uff09\uff0c\u7f13\u5b58\u987a\u5e8f\u53d8\u4e3a [B,C,A]<\/p>\n

\u82e5\u518d\u5b58\u5165D\uff08\u7f13\u5b58\u6ee1\u4e86\uff09\uff0c\u9700\u8981\u6dd8\u6c70\u6700\u8fd1\u6700\u5c11\u4f7f\u7528\u7684 B\uff0c\u6700\u7ec8\u7f13\u5b58\u662f [C,A,D]<\/p>\n<\/blockquote>\n

LRU \u7684\u4f18\u7f3a\u70b9<\/h3>\n

\u4f18\u70b9\uff1a<\/h4>\n
    \n
  • \u903b\u8f91\u7b80\u5355\uff1a\u53ea\u5173\u6ce8\u4f7f\u7528\u65f6\u95f4\uff0c\u5b9e\u73b0\u6210\u672c\u4f4e\uff0c\u5bb9\u6613\u7406\u89e3<\/li>\n
  • \u54cd\u5e94\u5feb\uff1a\u63d2\u5165\u3001\u5220\u9664\u3001\u67e5\u8be2\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u53ef\u4ee5\u505a\u5230 O (1)\uff08\u7528\u94fe\u8868 + \u54c8\u5e0c\u8868\u5b9e\u73b0\uff09<\/li>\n
  • \u8d34\u5408\u77ed\u671f\u5c40\u90e8\u6027\uff1a\u5f88\u591a\u4e1a\u52a1\u573a\u666f\u4e2d\uff0c\u6700\u8fd1\u7528\u7684\u6570\u636e\uff0c\u786e\u5b9e\u63a5\u4e0b\u6765\u66f4\u53ef\u80fd\u7528\uff08\u6bd4\u5982\u4f60\u521a\u6253\u5f00\u7684\u6587\u6863\uff0c\u63a5\u4e0b\u6765\u5927\u6982\u7387\u4f1a\u7ee7\u7eed\u7f16\u8f91\uff09\u3002<\/li>\n<\/ul>\n

    \u7f3a\u70b9\uff1a<\/h4>\n
      \n
    • \n

      \u7a81\u53d1\u8bbf\u95ee\u8bef\u6dd8\u6c70<\/strong>\uff1a\u5982\u679c\u7a81\u7136\u6709\u5927\u91cf\u4e00\u6b21\u6027\u6570\u636e<\/code>\u8bbf\u95ee\uff0c\u4f1a\u628a\u539f\u672c\u5e38\u7528\u7684\u7f13\u5b58\u6324\u6389\u3002<\/p>\n

      \u6bd4\u5982\u7f13\u5b58\u5bb9\u91cf 3\uff0c\u539f\u672c\u7f13\u5b58 [A,B,C]\uff08A \u662f\u9ad8\u9891\u4f7f\u7528\uff09\uff0c\u7a81\u7136\u8fde\u7eed\u8bbf\u95ee D\u3001E\u3001F\uff0c\u6b64\u65f6\u4f1a\u6dd8\u6c70 A\u3001B\u3001C\uff0c\u7f13\u5b58\u53d8\u6210 [D,E,F]\uff1b\u4f46\u540e\u7eed\u518d\u8bbf\u95ee A \u65f6\uff0cA \u5df2\u7ecf\u88ab\u6dd8\u6c70\uff0c\u9700\u8981\u91cd\u65b0\u4ece\u6570\u636e\u5e93\u52a0\u8f7d\uff0c\u5bfc\u81f4\u7f13\u5b58\u547d\u4e2d\u7387\u9aa4\u964d<\/code>\u3002<\/p>\n<\/li>\n

    • \u4e0d\u8003\u8651\u4f7f\u7528\u9891\u7387<\/strong>\uff1a\u5982\u679c A \u6bcf\u5929\u7528 100 \u6b21\uff0cB \u6bcf\u5929\u7528 1 \u6b21\uff0c\u4f46 B \u662f 1 \u5206\u949f\u524d\u521a\u7528\uff0cA \u662f 2 \u5206\u949f\u524d\u7528\uff0cLRU \u4f1a\u4f18\u5148\u6dd8\u6c70 A\uff0c\u8fd9\u663e\u7136\u4e0d\u5408\u7406\uff08\u9ad8\u9891\u4f7f\u7528\u7684 A \u4e0d\u8be5\u88ab\u6dd8\u6c70\uff09\u3002<\/li>\n<\/ul>\n

      \u5b9e\u73b0 LRU \u4e24\u79cd\u65b9\u6848<\/h3>\n

      \u65b9\u6848 1\uff1a\u57fa\u4e8e LinkedHashMap<\/h4>\n

      Java \u7684LinkedHashMap<\/code>\u81ea\u5e26\u6309\u8bbf\u95ee\u987a\u5e8f\u6392\u5e8f\u7684\u529f\u80fd\uff0c\u53ea\u9700\u91cd\u5199removeEldestEntry<\/code>\u65b9\u6cd5\uff0c\u5c31\u80fd\u5b9e\u73b0 LRU \u7f13\u5b58\u3002\u8fd9\u662f\u6700\u7b80\u6d01\u7684\u5b9e\u73b0\u65b9\u5f0f\uff0c\u9002\u5408\u4e1a\u52a1\u4e2d\u4e0d\u9700\u8981\u6781\u81f4\u6027\u80fd\u7684\u573a\u666f\uff0c\u5feb\u901f\u5f00\u53d1\u3002<\/p>\n

      import java.util.LinkedHashMap;\nimport java.util.Map;\n\npublic class LRUCache<K, V> extends LinkedHashMap<K, V> {\n    \/\/ \u7f13\u5b58\u6700\u5927\u5bb9\u91cf\n    private final int maxCapacity;\n\n    \/\/ \u6784\u9020\u51fd\u6570\uff1aaccessOrder=true \u8868\u793a\u201c\u6309\u8bbf\u95ee\u987a\u5e8f\u6392\u5e8f\u201d\uff08\u6838\u5fc3\uff09\n    public LRUCache(int maxCapacity) {\n        super(maxCapacity, 0.75f, true);\n        this.maxCapacity = maxCapacity;\n    }\n\n    \/\/ \u6838\u5fc3\uff1a\u5f53\u7f13\u5b58\u5927\u5c0f\u8d85\u8fc7maxCapacity\u65f6\uff0c\u81ea\u52a8\u5220\u9664\u201c\u6700\u8001\u7684 entry\u201d\uff08\u6700\u8fd1\u6700\u5c11\u4f7f\u7528\u7684\uff09\n    @Override\n    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {\n        return size() > maxCapacity;\n    }\n\n    \/\/ \u6d4b\u8bd5\n    public static void main(String[] args) {\n        LRUCache<Integer, String> cache = new LRUCache<>(3);\n        cache.put(1, "A");\n        cache.put(2, "B");\n        cache.put(3, "C");\n        System.out.println(cache); \/\/ \u8f93\u51fa\uff1a{1=A, 2=B, 3=C}\uff08\u63d2\u5165\u987a\u5e8f\uff09\n\n        cache.get(1); \/\/ \u8bbf\u95ee1\uff0c1\u53d8\u6210\u6700\u8fd1\u4f7f\u7528\n        System.out.println(cache); \/\/ \u8f93\u51fa\uff1a{2=B, 3=C, 1=A}\uff08\u6309\u8bbf\u95ee\u987a\u5e8f\u6392\u5e8f\uff09\n\n        cache.put(4, "D"); \/\/ \u7f13\u5b58\u6ee1\u4e86\uff0c\u6dd8\u6c70\u6700\u8001\u76842\n        System.out.println(cache); \/\/ \u8f93\u51fa\uff1a{3=C, 1=A, 4=D}\n    }\n}<\/code><\/pre>\n
      \u65b9\u6848 2\uff1a\u57fa\u4e8e\u53cc\u5411\u94fe\u8868 + \u54c8\u5e0c\u8868<\/h4>\n
      LinkedHashMap<\/code>\u672c\u8d28\u662f\u54c8\u5e0c\u8868 + \u53cc\u5411\u94fe\u8868\uff0c\u4f46\u5982\u679c\u60f3\u6df1\u5165\u7406\u89e3 LRU \u7684\u5b9e\u73b0\u539f\u7406\uff0c\u5efa\u8bae\u81ea\u5df1\u624b\u5199\u4e00\u4e2a\u6838\u5fc3\u662f\u7528\u54c8\u5e0c\u8868\u4fdd\u8bc1 O (1) \u67e5\u8be2\uff0c\u7528\u53cc\u5411\u94fe\u8868\u4fdd\u8bc1 O (1) \u63d2\u5165\u3001\u5220\u9664\uff08\u7ef4\u62a4\u8bbf\u95ee\u987a\u5e8f\uff09\u3002\u9002\u7528\u4e8e\u9ad8\u5e76\u53d1\u573a\u666f\u548c\u9762\u8bd5\u3002<\/p>\n
      import java.util.HashMap;\nimport java.util.Map;\n\npublic class LRUCache2<K, V> {\n    \/\/ \u53cc\u5411\u94fe\u8868\u8282\u70b9\uff1a\u5b58\u50a8key\u3001value\uff0c\u4ee5\u53ca\u524d\u540e\u6307\u9488\n    static class Node<K, V> {\n        K key;\n        V value;\n        Node<K, V> prev;\n        Node<K, V> next;\n\n        public Node(K key, V value) {\n            this.key = key;\n            this.value = value;\n        }\n    }\n\n    private final int maxCapacity;\n    private final Map<K, Node<K, V>> map; \/\/ \u54c8\u5e0c\u8868\uff1akey\u2192Node\uff0cO(1)\u67e5\u8be2\n    private final Node<K, V> head; \/\/ \u865a\u62df\u5934\u8282\u70b9\uff08\u7b80\u5316\u94fe\u8868\u64cd\u4f5c\uff09\n    private final Node<K, V> tail; \/\/ \u865a\u62df\u5c3e\u8282\u70b9\n\n    public LRUCache2(int maxCapacity) {\n        this.maxCapacity = maxCapacity;\n        this.map = new HashMap<>();\n        \/\/ \u521d\u59cb\u5316\u865a\u62df\u5934\u5c3e\u8282\u70b9\uff0c\u907f\u514d\u5904\u7406null\u6307\u9488\n        this.head = new Node<>(null, null);\n        this.tail = new Node<>(null, null);\n        head.next = tail;\n        tail.prev = head;\n    }\n\n    \/\/ 1. \u83b7\u53d6\u7f13\u5b58\uff1a\u547d\u4e2d\u5219\u628a\u8282\u70b9\u79fb\u5230\u94fe\u8868\u5934\u90e8\uff08\u6807\u8bb0\u4e3a\u6700\u8fd1\u4f7f\u7528\uff09\n    public V get(K key) {\n        Node<K, V> node = map.get(key);\n        if (node == null) {\n            return null; \/\/ \u672a\u547d\u4e2d\n        }\n        \/\/ \u79fb\u9664\u5f53\u524d\u8282\u70b9\n        removeNode(node);\n        \/\/ \u79fb\u5230\u5934\u90e8\n        addToHead(node);\n        return node.value;\n    }\n\n    \/\/ 2. \u5b58\u5165\u7f13\u5b58\uff1a\u4e0d\u5b58\u5728\u5219\u65b0\u589e\uff0c\u5b58\u5728\u5219\u66f4\u65b0\u5e76\u79fb\u5230\u5934\u90e8\uff1b\u6ee1\u4e86\u5219\u5220\u9664\u5c3e\u90e8\u8282\u70b9\n    public void put(K key, V value) {\n        Node<K, V> node = map.get(key);\n        if (node == null) {\n            \/\/ \u65b0\u589e\u8282\u70b9\n            Node<K, V> newNode = new Node<>(key, value);\n            map.put(key, newNode);\n            addToHead(newNode);\n\n            \/\/ \u7f13\u5b58\u6ee1\u4e86\uff0c\u5220\u9664\u5c3e\u90e8\u8282\u70b9\uff08\u6700\u8fd1\u6700\u5c11\u4f7f\u7528\uff09\n            if (map.size() > maxCapacity) {\n                Node<K, V> tailNode = removeTail();\n                map.remove(tailNode.key); \/\/ \u540c\u6b65\u5220\u9664\u54c8\u5e0c\u8868\u4e2d\u7684key\n            }\n        } else {\n            \/\/ \u66f4\u65b0\u8282\u70b9\u503c\uff0c\u5e76\u79fb\u5230\u5934\u90e8\n            node.value = value;\n            removeNode(node);\n            addToHead(node);\n        }\n    }\n\n    \/\/ \u8f85\u52a9\uff1a\u628a\u8282\u70b9\u6dfb\u52a0\u5230\u94fe\u8868\u5934\u90e8\n    private void addToHead(Node<K, V> node) {\n        node.prev = head;\n        node.next = head.next;\n        head.next.prev = node;\n        head.next = node;\n    }\n\n    \/\/ \u8f85\u52a9\uff1a\u79fb\u9664\u6307\u5b9a\u8282\u70b9\n    private void removeNode(Node<K, V> node) {\n        node.prev.next = node.next;\n        node.next.prev = node.prev;\n    }\n\n    \/\/ \u8f85\u52a9\uff1a\u79fb\u9664\u5c3e\u90e8\u8282\u70b9\uff08\u6700\u8fd1\u6700\u5c11\u4f7f\u7528\uff09\n    private Node<K, V> removeTail() {\n        Node<K, V> tailNode = tail.prev;\n        removeNode(tailNode);\n        return tailNode;\n    }\n\n    \/\/ \u6d4b\u8bd5\n    public static void main(String[] args) {\n        LRUCache2<Integer, String> cache = new LRUCache2<>(3);\n        cache.put(1, "A");\n        cache.put(2, "B");\n        cache.put(3, "C");\n        System.out.println(cache.get(1)); \/\/ \u8f93\u51faA\uff0c\u6b64\u65f61\u79fb\u5230\u5934\u90e8\n        cache.put(4, "D"); \/\/ \u6dd8\u6c703\n        System.out.println(cache.get(3)); \/\/ \u8f93\u51fanull\uff08\u5df2\u88ab\u6dd8\u6c70\uff09\n    }\n}<\/code><\/pre>\n
      LRU \u7684\u4f7f\u7528\u573a\u666f<\/h3>\n
      LRU \u9002\u5408\u77ed\u671f\u9ad8\u9891\u573a\u666f\uff0c\u6bd4\u5982:<\/p>\n
        \n
      • \u6d4f\u89c8\u5668\u7f13\u5b58<\/strong>\uff1a\u6d4f\u89c8\u5668\u7f13\u5b58\u7f51\u9875\u65f6\uff0c\u4f1a\u4f18\u5148\u6dd8\u6c70\u6700\u8fd1\u6700\u5c11\u6253\u5f00\u201d\u7684\u9875\u9762\uff08\u6bd4\u5982\u4f60\u4e00\u5468\u6ca1\u6253\u5f00\u7684\u7f51\u9875\uff0c\u4f1a\u88ab\u4f18\u5148\u6e05\u7406\uff09\uff1b<\/li>\n
      • Redis \u9ed8\u8ba4\u5185\u5b58\u6dd8\u6c70\u7b56\u7565<\/strong>\uff1aRedis \u7684allkeys-lru<\/code>\u548cvolatile-lru<\/code>\u662f\u57fa\u4e8e LRU \u7684\uff08\u5b9e\u9645\u662f \u201c\u8fd1\u4f3c LRU\u201d\uff0c\u6027\u80fd\u66f4\u9ad8\uff09\uff0c\u9002\u5408 \u201c\u7f13\u5b58\u8bbf\u95ee\u5177\u6709\u77ed\u671f\u5c40\u90e8\u6027\u201d \u7684\u573a\u666f\uff08\u6bd4\u5982\u7535\u5546\u5546\u54c1\u8be6\u60c5\u9875\uff0c\u7528\u6237\u6253\u5f00\u540e\u77ed\u65f6\u95f4\u5185\u53ef\u80fd\u518d\u6b21\u5237\u65b0\uff09\uff1b<\/li>\n
      • \u672c\u5730\u7f13\u5b58\u57fa\u7840\u7248<\/strong>\uff1a\u5982\u679c\u4e1a\u52a1\u4e2d\u6ca1\u6709\u7a81\u53d1\u5927\u91cf\u4e00\u6b21\u6027\u8bbf\u95ee\uff0c\u7528 LRU \u5b9e\u73b0\u672c\u5730\u7f13\u5b58\u8db3\u591f\u6ee1\u8db3\u9700\u6c42\uff08\u6bd4\u5982\u7528 LinkedHashMap \u5feb\u901f\u5f00\u53d1\uff09\u3002<\/li>\n<\/ul>\n
        \u4e8c\u3001\u4ec0\u4e48\u662f LFU \u7b97\u6cd5\uff1f<\/h2>\n
        LFU<\/code> \u7684\u5168\u79f0\u662f Least Frequently Used\uff08\u6700\u4e0d\u7ecf\u5e38\u4f7f\u7528\uff09<\/strong>\uff0c\u6838\u5fc3\u903b\u8f91\u548c LRU \u5b8c\u5168\u4e0d\u540c\uff1a\u7528\u5f97\u5c11\u7684\uff0c\u4e0b\u6b21\u4e5f\u5927\u6982\u7387\u7528\u4e0d\u4e0a<\/strong>\uff0c\u5b83\u5173\u6ce8\u7684\u662f\u4f7f\u7528\u9891\u7387<\/code>\uff0c\u800c\u4e0d\u662f\u4f7f\u7528\u65f6\u95f4<\/code>\u3002<\/p>\n
        \u8fd8\u662f\u7528\u751f\u6d3b\u4f8b\u5b50\uff1a\u4f60\u624b\u673a\u91cc\u7684 APP\uff0c\u5fae\u4fe1\u3001\u6296\u97f3\u662f\u9ad8\u9891\u4f7f\u7528\u7684\uff08\u6bcf\u5929\u6253\u5f00\u51e0\u5341\u6b21\uff09\uff0c\u800c\u6307\u5357\u9488\u662f\u4f4e\u9891\u4f7f\u7528\u7684\uff08\u51e0\u4e2a\u6708\u6253\u5f00\u4e00\u6b21\uff09\u3002\u5f53\u624b\u673a\u5185\u5b58\u4e0d\u8db3\u65f6\uff0c\u7cfb\u7edf\u4f1a\u4f18\u5148\u5378\u8f7d\u6307\u5357\u9488\u8fd9\u7c7b\u4f4e\u9891 APP\uff0c\u8fd9\u5c31\u662f LFU \u7684\u601d\u8def\u3002<\/p>\n
        \n
        \u5047\u8bbe\u7f13\u5b58\u5bb9\u91cf 3\uff0c\u521d\u59cb\u5b58\u5165 A\uff08\u4f7f\u7528 1 \u6b21\uff09\u3001B\uff08\u4f7f\u7528 1 \u6b21\uff09\u3001C\uff08\u4f7f\u7528 1 \u6b21\uff09\uff0c\u9891\u7387\u90fd\u662f 1\uff1b<\/p>\n
        \u8bbf\u95ee A\uff08A \u9891\u7387\u53d8\u6210 2\uff09\uff0c\u6b64\u65f6\u9891\u7387\uff1aA=2\uff0cB=1\uff0cC=1\uff1b<\/p>\n
        \u8bbf\u95ee A\uff08A \u9891\u7387\u53d8\u6210 3\uff09\uff0c\u6b64\u65f6\u9891\u7387\uff1aA=3\uff0cB=1\uff0cC=1\uff1b<\/p>\n
        \u5b58\u5165 D\uff08\u7f13\u5b58\u6ee1\u4e86\uff09\uff0c\u9700\u8981\u6dd8\u6c70 \u201c\u9891\u7387\u6700\u4f4e\u201d \u7684 B \u6216 C\uff08\u82e5\u9891\u7387\u76f8\u540c\uff0c\u6dd8\u6c70 \u201c\u6700\u8fd1\u6700\u5c11\u4f7f\u7528\u201d \u7684\uff0c\u5373 LFU+LRU \u7ed3\u5408\uff09\uff0c\u6700\u7ec8\u7f13\u5b58\u662f A\u3001C\u3001D\uff08\u9891\u7387\u5206\u522b\u4e3a 3\u30011\u30011\uff09\u3002<\/p>\n<\/blockquote>\n
        LFU \u7684\u4f18\u7f3a\u70b9<\/h3>\n
        \u4f18\u70b9\uff1a<\/h4>\n
          \n
        • \u66f4\u8d34\u5408\u957f\u671f\u9ad8\u9891\u573a\u666f<\/strong>\uff1a\u80fd\u4fdd\u7559\u4f7f\u7528\u9891\u7387\u9ad8\u7684\u6570\u636e\uff0c\u5373\u4f7f\u5b83\u4e0d\u662f \u6700\u8fd1\u4f7f\u7528\u7684\uff08\u6bd4\u5982 A \u6bcf\u5929\u7528 100 \u6b21\uff0c\u5373\u4f7f 10 \u5206\u949f\u524d\u6ca1\u2f64\uff0c\u4e5f\u4e0d\u8be5\u88ab\u6dd8\u6c70\uff09\uff1b<\/li>\n
        • \u907f\u514d\u7a81\u53d1\u8bbf\u95ee\u8bef\u6dd8\u6c70<\/strong>\uff1a\u9762\u5bf9\u4e00\u6b21\u6027\u7a81\u53d1\u8bbf\u95ee\uff08\u6bd4\u5982\u8bbf\u95ee D\u3001E\u3001F\uff09\uff0c\u56e0\u4e3a\u8fd9\u4e9b\u6570\u636e\u7684\u9891\u7387\u4f4e\uff0c\u4e0d\u4f1a\u628a\u9ad8\u9891\u7684 A\u3001B\u3001C \u6324\u6389\uff0c\u7f13\u5b58\u547d\u4e2d\u7387\u66f4\u7a33\u5b9a\u3002<\/li>\n<\/ul>\n
          \u7f3a\u70b9\uff1a<\/h4>\n
            \n
          • \u5b9e\u73b0\u590d\u6742<\/strong>\uff1a\u9700\u8981\u7ef4\u62a4\u4f7f\u7528\u9891\u7387\uff0c\u8fd8\u9700\u8981\u5904\u7406\u9891\u7387\u76f8\u540c\u7684\u60c5\u51b5\uff08\u901a\u5e38\u7ed3\u5408 LRU\uff09\uff0c\u65f6\u95f4\u590d\u6742\u5ea6\u6bd4 LRU \u9ad8\uff08\u63d2\u5165\u3001\u5220\u9664\u7ea6 O (log n)\uff09\uff1b<\/li>\n
          • \u51b7\u542f\u52a8\u95ee\u9898<\/strong>\uff1a\u65b0\u5b58\u5165\u7684\u7f13\u5b58\u9891\u7387\u4f4e\uff0c\u5bb9\u6613\u88ab\u6dd8\u6c70\u3002\u6bd4\u5982\u4e00\u4e2a\u65b0\u529f\u80fd\u7684\u63a5\u53e3\uff0c\u521a\u5f00\u59cb\u8bbf\u95ee\u9891\u7387\u4f4e\uff0c\u4f1a\u88ab LFU \u4f18\u5148\u6dd8\u6c70\uff0c\u4f46\u5176\u5b9e\u540e\u7eed\u4f1a\u53d8\u6210\u9ad8\u9891\u63a5\u53e3\uff1b<\/li>\n
          • \u9891\u7387\u8001\u5316\u95ee\u9898<\/strong>\uff1a\u4e00\u4e2a\u6570\u636e\u8fc7\u53bb\u9ad8\u9891\uff0c\u4f46\u73b0\u5728\u4e0d\u518d\u4f7f\u7528\uff08\u6bd4\u5982\u6d3b\u52a8\u7ed3\u675f\u540e\u7684\u6d3b\u52a8\u9875\u9762\uff09\uff0c\u5b83\u7684\u9ad8\u9891\u7387\u4f1a\u4e00\u76f4\u5360\u7528\u7f13\u5b58\uff0c\u5bfc\u81f4\u65b0\u7684\u9ad8\u9891\u6570\u636e\u65e0\u6cd5\u8fdb\u5165\u3002<\/li>\n<\/ul>\n
            \u5b9e\u73b0 LFU\uff1a\u57fa\u4e8e\u54c8\u5e0c\u8868 + \u4f18\u5148\u7ea7\u961f\u5217<\/h3>\n
            LFU \u7684\u5b9e\u73b0\u6bd4 LRU \u590d\u6742\uff0c\u6838\u5fc3\u9700\u8981\u4e24\u4e2a\u54c8\u5e0c\u8868\uff1a<\/p>\n
              \n
            • cache<\/code>\uff1akey\u2192Node\uff08\u5b58\u50a8 value \u548c\u4f7f\u7528\u9891\u7387\u3001\u6700\u540e\u4f7f\u7528\u65f6\u95f4\uff09\uff1b<\/li>\n
            • \n
              freqMap<\/code>\uff1a\u9891\u7387\u2192LinkedHashSet\uff08\u5b58\u50a8\u8be5\u9891\u7387\u4e0b\u7684\u6240\u6709 key\uff0cLinkedHashSet \u4fdd\u8bc1\u63d2\u5165\u987a\u5e8f\uff0c\u7528\u4e8e\u5904\u7406\u9891\u7387\u76f8\u540c\u7684\u60c5\u51b5\uff09\uff1b<\/p>\n
              \u518d\u7528\u4e00\u4e2a\u53d8\u91cfminFreq<\/code>\u8bb0\u5f55\u5f53\u524d\u6700\u5c0f\u9891\u7387\uff0c\u5feb\u901f\u627e\u5230\u6700\u8be5\u6dd8\u6c70\u7684 key\u3002<\/p>\n<\/li>\n<\/ul>\n
              import java.util.*;\n\npublic class LFUCache<K, V> {\n    \/\/ \u7f13\u5b58\u8282\u70b9\uff1a\u5b58\u50a8key\u3001value\u3001\u4f7f\u7528\u9891\u7387\u3001\u6700\u540e\u4f7f\u7528\u65f6\u95f4\uff08\u5904\u7406\u9891\u7387\u76f8\u540c\u65f6\u7684\u6dd8\u6c70\uff09\n    static class Node<K, V> {\n        K key;\n        V value;\n        int freq; \/\/ \u4f7f\u7528\u9891\u7387\n        long lastUseTime; \/\/ \u6700\u540e\u4f7f\u7528\u65f6\u95f4\uff08\u6beb\u79d2\uff09\n\n        public Node(K key, V value) {\n            this.key = key;\n            this.value = value;\n            this.freq = 1; \/\/ \u521d\u59cb\u9891\u73871\n            this.lastUseTime = System.currentTimeMillis();\n        }\n    }\n\n    private final int maxCapacity;\n    private final Map<K, Node<K, V>> cache; \/\/ key\u2192Node\n    private final Map<Integer, LinkedHashSet<K>> freqMap; \/\/ \u9891\u7387\u2192key\u96c6\u5408\uff08LinkedHashSet\u4fdd\u8bc1\u987a\u5e8f\uff09\n    private int minFreq; \/\/ \u5f53\u524d\u6700\u5c0f\u9891\u7387\uff08\u5feb\u901f\u5b9a\u4f4d\u8981\u6dd8\u6c70\u7684key\uff09\n\n    public LFUCache(int maxCapacity) {\n        this.maxCapacity = maxCapacity;\n        this.cache = new HashMap<>();\n        this.freqMap = new HashMap<>();\n        this.minFreq = 1;\n    }\n\n    \/\/ 1. \u83b7\u53d6\u7f13\u5b58\uff1a\u547d\u4e2d\u5219\u66f4\u65b0\u9891\u7387\u548c\u6700\u540e\u4f7f\u7528\u65f6\u95f4\n    public V get(K key) {\n        Node<K, V> node = cache.get(key);\n        if (node == null) {\n            return null;\n        }\n        \/\/ \u66f4\u65b0\u8282\u70b9\u9891\u7387\n        updateNodeFreq(node);\n        return node.value;\n    }\n\n    \/\/ 2. \u5b58\u5165\u7f13\u5b58\uff1a\u4e0d\u5b58\u5728\u5219\u65b0\u589e\uff0c\u5b58\u5728\u5219\u66f4\u65b0\uff1b\u6ee1\u4e86\u5219\u6dd8\u6c70\u6700\u5c0f\u9891\u7387\u7684key\n    public void put(K key, V value) {\n        if (maxCapacity <= 0) {\n            return;\n        }\n\n        Node<K, V> node = cache.get(key);\n        if (node != null) {\n            \/\/ \u5b58\u5728\uff1a\u66f4\u65b0value\u3001\u9891\u7387\u3001\u6700\u540e\u4f7f\u7528\u65f6\u95f4\n            node.value = value;\n            node.lastUseTime = System.currentTimeMillis();\n            updateNodeFreq(node);\n        } else {\n            \/\/ \u4e0d\u5b58\u5728\uff1a\u68c0\u67e5\u7f13\u5b58\u662f\u5426\u6ee1\n            if (cache.size() >= maxCapacity) {\n                \/\/ \u6dd8\u6c70\u6700\u5c0f\u9891\u7387\u7684key\uff08\u9891\u7387\u76f8\u540c\u5219\u6dd8\u6c70\u6700\u65e9\u4f7f\u7528\u7684\uff09\n                evictMinFreqKey();\n            }\n            \/\/ \u65b0\u589e\u8282\u70b9\n            Node<K, V> newNode = new Node<>(key, value);\n            cache.put(key, newNode);\n            \/\/ \u52a0\u5165freqMap\uff1a\u9891\u73871\u7684\u96c6\u5408\n            freqMap.computeIfAbsent(1, k -> new LinkedHashSet<>()).add(key);\n            \/\/ \u65b0\u8282\u70b9\u9891\u7387\u662f1\uff0cminFreq\u91cd\u7f6e\u4e3a1\n            minFreq = 1;\n        }\n    }\n\n    \/\/ \u8f85\u52a9\uff1a\u66f4\u65b0\u8282\u70b9\u9891\u7387\n    private void updateNodeFreq(Node<K, V> node) {\n        K key = node.key;\n        int oldFreq = node.freq;\n        int newFreq = oldFreq + 1;\n\n        \/\/ 1. \u4ece\u65e7\u9891\u7387\u7684\u96c6\u5408\u4e2d\u79fb\u9664key\n        LinkedHashSet<K> oldFreqSet = freqMap.get(oldFreq);\n        oldFreqSet.remove(key);\n        \/\/ \u5982\u679c\u65e7\u9891\u7387\u662fminFreq\uff0c\u4e14\u96c6\u5408\u4e3a\u7a7a\uff0cminFreq+1\n        if (oldFreq == minFreq && oldFreqSet.isEmpty()) {\n            minFreq = newFreq;\n        }\n\n        \/\/ 2. \u52a0\u5165\u65b0\u9891\u7387\u7684\u96c6\u5408\n        freqMap.computeIfAbsent(newFreq, k -> new LinkedHashSet<>()).add(key);\n\n        \/\/ 3. \u66f4\u65b0\u8282\u70b9\u7684\u9891\u7387\u548c\u6700\u540e\u4f7f\u7528\u65f6\u95f4\n        node.freq = newFreq;\n        node.lastUseTime = System.currentTimeMillis();\n    }\n\n    \/\/ \u8f85\u52a9\uff1a\u6dd8\u6c70\u6700\u5c0f\u9891\u7387\u7684key\uff08\u9891\u7387\u76f8\u540c\u5219\u6dd8\u6c70\u6700\u65e9\u4f7f\u7528\u7684\uff09\n    private void evictMinFreqKey() {\n        \/\/ 1. \u83b7\u53d6\u6700\u5c0f\u9891\u7387\u7684key\u96c6\u5408\n        LinkedHashSet<K> minFreqSet = freqMap.get(minFreq);\n        \/\/ 2. \u6dd8\u6c70\u96c6\u5408\u4e2d\u7b2c\u4e00\u4e2akey\uff08LinkedHashSet\u6309\u63d2\u5165\u987a\u5e8f\uff0c\u5373\u6700\u65e9\u4f7f\u7528\u7684\uff09\n        K evictKey = minFreqSet.iterator().next();\n        minFreqSet.remove(evictKey);\n\n        \/\/ 3. \u540c\u6b65\u5220\u9664cache\u548cfreqMap\uff08\u5982\u679c\u96c6\u5408\u4e3a\u7a7a\uff09\n        cache.remove(evictKey);\n        if (minFreqSet.isEmpty()) {\n            freqMap.remove(minFreq);\n        }\n\n        System.out.println("\u6dd8\u6c70key\uff1a" + evictKey);\n    }\n\n    \/\/ \u6d4b\u8bd5\n    public static void main(String[] args) {\n        LFUCache<Integer, String> cache = new LFUCache<>(3);\n        cache.put(1, "A");\n        cache.put(2, "B");\n        cache.put(3, "C");\n        System.out.println(cache.get(1)); \/\/ \u8f93\u51faA\uff0c\u9891\u7387\u53d8\u62102\uff0cminFreq\u8fd8\u662f1\n        cache.put(4, "D"); \/\/ \u7f13\u5b58\u6ee1\uff0c\u6dd8\u6c70minFreq=1\u76842\uff08B\uff09\n        System.out.println(cache.get(2)); \/\/ \u8f93\u51fanull\uff08\u5df2\u6dd8\u6c70\uff09\n        cache.get(3); \/\/ 3\u9891\u7387\u53d8\u62102\uff0cminFreq\u53d8\u62102\n        cache.get(4); \/\/ 4\u9891\u7387\u53d8\u62102\n        cache.put(5, "E"); \/\/ \u7f13\u5b58\u6ee1\uff0c\u6dd8\u6c70minFreq=2\u76843\uff08C\uff0c\u6700\u65e9\u4f7f\u7528\uff09\n    }<\/code><\/pre>\n
              \u4e09\u3001Redis \u4e2d\u7684 LRU \u548c LFU\uff1a\u5b9e\u73b0\u4e0e\u533a\u522b<\/h2>\n
              Redis \u4f5c\u4e3a\u7f13\u5b58\u6570\u636e\u5e93\uff0c\u5f53\u5185\u5b58\u8fbe\u5230\u5185\u5b58maxmemory<\/code>\u9650\u5236\u65f6\uff0c\u4f1a\u89e6\u53d1\u5185\u5b58\u6dd8\u6c70\u7b56\u7565\uff0c\u5176\u4e2dLRU<\/code>\u548cLFU<\/code>\u662f\u6700\u5e38\u7528\u7684\u4e24\u79cd\u3002<\/p>\n
              \u4f46 Redis \u7684\u5b9e\u73b0\u5e76\u975e \u201c\u4e25\u683c\u7248\u201d\uff0c\u800c\u662f\u505a\u4e86\u6027\u80fd\u4f18\u5316\u7684 \u201c\u8fd1\u4f3c\u7248\u201d\uff0c<\/strong> \u8fd9\u4e00\u70b9\u5c24\u5176\u9700\u8981\u6ce8\u610f\u3002<\/p>\n
              Redis \u7684 LRU \u5b9e\u73b0<\/h3>\n
              Redis \u7684 LRU \u5b9e\u73b0\uff1a\u8fd1\u4f3c LRU\uff08\u6027\u80fd\u4f18\u5148\uff09<\/p>\n
              Redis \u6ca1\u6709\u91c7\u7528 \u201c\u53cc\u5411\u94fe\u8868 + \u54c8\u5e0c\u8868\u201d \u7684\u6807\u51c6 LRU \u5b9e\u73b0\uff0c\u56e0\u4e3a\u4f1a\u589e\u52a0\u5185\u5b58\u5f00\u9500\u548c\u64cd\u4f5c\u590d\u6742\u5ea6\uff0c\u800c\u662f\u7528\u968f\u673a\u91c7\u6837 + \u65f6\u95f4\u6233<\/strong>\u5b9e\u73b0\u8fd1\u4f3c LRU\uff1a<\/p>\n
                \n
              • \u6838\u5fc3\u539f\u7406<\/strong>\uff1a\u6bcf\u4e2a key \u5728\u5185\u5b58\u4e2d\u8bb0\u5f55lru<\/code>\u5b57\u6bb5\uff08\u6700\u540e\u4e00\u6b21\u8bbf\u95ee\u7684\u65f6\u95f4\u6233\uff09\uff0c\u5f53\u9700\u8981\u6dd8\u6c70 key \u65f6\uff0cRedis \u4f1a\u4ece\u6240\u6709\u5019\u9009 key \u4e2d\u968f\u673a\u91c7\u6837 N \u4e2a<\/strong>\uff08\u9ed8\u8ba4 5 \u4e2a\uff0c\u53ef\u901a\u8fc7maxmemory-samples<\/code>\u914d\u7f6e\uff09\uff0c\u7136\u540e\u6dd8\u6c70\u8fd9 N \u4e2a\u4e2dlru<\/code>\u503c\u6700\u5c0f\uff08\u6700\u4e45\u672a\u4f7f\u7528\uff09\u7684 key\u3002<\/li>\n
              • \u4e3a\u4ec0\u4e48\u8fd1\u4f3c<\/strong>\uff1a\u4e25\u683c LRU \u9700\u8981\u7ef4\u62a4\u5168\u91cf key \u7684\u8bbf\u95ee\u987a\u5e8f\uff0c\u5728 Redis \u9ad8\u5e76\u53d1\u573a\u666f\u4e0b\u4f1a\u6210\u4e3a\u6027\u80fd\u74f6\u9888\uff1b\u8fd1\u4f3c LRU \u901a\u8fc7\u63a7\u5236\u91c7\u6837\u6570\uff08N \u8d8a\u5927\u8d8a\u63a5\u8fd1\u4e25\u683c LRU\uff0c\u4f46\u6027\u80fd\u7a0d\u5dee\uff09\uff0c\u5728 \u201c\u547d\u4e2d\u7387\u201d \u548c \u201c\u6027\u80fd\u201d \u4e4b\u95f4\u505a\u4e86\u5e73\u8861\u3002<\/li>\n
              • \u76f8\u5173\u914d\u7f6e<\/strong>\uff1a<\/li>\n<\/ul>\n
                # \u6dd8\u6c70\u6240\u6709key\u4e2d\u6700\u4e45\u672a\u4f7f\u7528\u7684\nmaxmemory-policy allkeys-lru\n# \u53ea\u6dd8\u6c70\u8bbe\u7f6e\u4e86\u8fc7\u671f\u65f6\u95f4\u7684key\u4e2d\u6700\u4e45\u672a\u4f7f\u7528\u7684\nmaxmemory-policy volatile-lru\n# \u91c7\u6837\u6570\uff08\u9ed8\u8ba45\uff0c\u8303\u56f43-10\uff09\nmaxmemory-samples 5<\/code><\/pre>\n
                Redis \u7684 LFU \u5b9e\u73b0<\/h3>\n
                Redis \u7684 LFU \u5b9e\u73b0\uff0c\u7ed3\u5408\u9891\u7387\u4e0e\u65f6\u95f4\u8870\u51cf\u3002<\/p>\n
                Redis 4.0 \u5f15\u5165\u4e86 LFU \u7b56\u7565\uff0c\u89e3\u51b3\u4e86\u6807\u51c6 LFU \u7684\u9891\u7387\u8001\u5316\u95ee\u9898\uff0c\u5b9e\u73b0\u66f4\u8d34\u5408\u5b9e\u9645\u4e1a\u52a1\uff1a<\/p>\n
                \u6838\u5fc3\u6539\u8fdb<\/strong>\uff1a<\/p>\n