【图解数据结构】如何设计一个LFU缓存？？

103 阅读 0 评论 68 点赞

我是靠谱客的博主哭泣钢笔，这篇文章主要介绍【图解数据结构】如何设计一个LFU缓存？？，现在分享给大家，希望可以做个参考。

需求描述

设计详解

LFU总体概览

细说get和put

代码部分

需求描述

这是一道来自LeetCode的设计题目，题目内容如下:
请你为最不经常使用（LFU） 缓存算法设计并实现数据结构。它应该支持以下操作：get 和 put。
get(key) - 如果键存在于缓存中，则获取键的值（总是正数），否则返回 -1。
put(key, value) - 如果键已存在，则变更其值；如果键不存在，请插入键值对。当缓存达到其容量时，则应该在插入新项之前，使最不经常使用的项无效。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，应该去除最近最少使用的键。
「项的使用次数」就是自插入该项以来对其调用 get 和 put 函数的次数之和。使用次数会在对应项被移除后置为 0 。
进阶：
你是否可以在 O(1) 时间复杂度内执行两项操作？
示例：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
LFUCache cache = new LFUCache( 2 /* capacity (缓存容量) */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // 返回 1
cache.put(3, 3);    // 去除 key 2
cache.get(2);       // 返回 -1 (未找到key 2)
cache.get(3);       // 返回 3
cache.put(4, 4);    // 去除 key 1
cache.get(1);       // 返回 -1 (未找到 key 1)
cache.get(3);       // 返回 3
cache.get(4);       // 返回 4

设计详解

LFU总体概览

缓存的大小是有限的，当缓存满了又有新元素需要添加时，就需要一种方式从缓存中删除一些元素，删除的策略对应的就是缓存的淘汰算法。LFU有个兄弟LRU，他们两都是常用的缓存淘汰算法。

LRU(Least Recently Used)最近最少使用算法，它是根据时间维度来选择将要淘汰的元素，即删除掉最长时间没被访问的元素。
LFU(Least Frequently Used)最不经常使用算法，它是根据频率维度来选择将要淘汰的元素，即删除访问频率最低的元素。如果两个元素的访问频率相同，则淘汰最久没被访问的元素。
也就是说LFU淘汰的时候会选择两个维度，先比较频率，选择访问频率最小的元素；如果频率相同，则按时间维度淘汰掉最久远的那个元素。

LRU的实现是一个哈希表加上一个双链表
而LFU则要复杂多了，需要用两个哈希表再加上N个双链表才能实现
我们先看看LFU的两个哈希表里面都存了什么

第一个哈希表是key-value的哈希表(以下简称k-v哈希表)

这里的key就是输入的key，没什么特别的。关键是value，它的value不是一个简单的value，而是一个节点对象。
节点对象Node包含了key，value，以及频率，这个Node又会出现在第二个哈希表的value中(等会我们再说)。
至于为什么Node中又重复包含了key，因为某些情况下我们不是通过k-v哈希表拿到Node的，而是通过其他方式获得了Node，之后需要用Node中的key反向去k-v哈希表中做一些操作，所以Node中包含了一些冗余信息。

第二张哈希表，频率哈希表，这个就要复杂多了

这张哈希表中的key是频率，也就是元素被访问的频率(被访问了1次，被访问了两次等等)，它的value是一个双向链表
刚才说的Node对象，现在又出现了，这里的Node其实是双向链表中的一个节点。
第一张图中我们说了Node中包含了一个冗余的key，其实它还包含了一个冗余的频率值，因为某些情况下，我们需要通过Node中的频率值，反向去频率哈希表中做查找，所以也需要一个冗余的频率值。

下面我们将两个哈希表整合起来看看完整的结构:

k-v哈希表中key1指向一个Node，这个Node的频率为1，位于频率哈希表中key=1下面的双链表中(处于第一个节点)。
我们通过Node中的key可以反向去k-v哈希表中做操作，也可以通过Node中的频率反向去频率哈希表中做操作。

细说get和put

下面我们来看看具体操作，get操作相对简单一些，我们就先说get操作吧。

get操作的具体逻辑大致是这样：

如果key不存在则返回-1
如果key存在，则返回对应的value，同时:
- 将元素的访问频率+1

元素访问频率+1又涉及下面一些操作

将元素从访问频率i的链表中移除，放到频率i+1的链表中
如果频率i的链表为空，则从频率哈希表中移除这个链表

上面的操作都是O(1)的时间复杂度，从访问频率i挪动到访问频率i+1这步只是删除一个链表节点(根据节点删除前后指向关系)，再插入到另一个双链表的头节点中，所以整体操作都是常数时间。
get的第一个操作很简单就不用说了，我们看下第二个操作的执行过程

假设某个元素的访问频率是3，现在又被访问了一次，那么就需要将这个元素移动到频率4的链表中。如果这个元素被移除后，频率3的那个链表变成空了(只剩下头结点和尾节点)就需要删除这个链表，同时删除对应的频率(也就是删除key=3)。但是k-v哈希表不动，因为我们只增加了频率，但key并没有动。

这个操作涉及到删除节点，再插入节点，最后从哈希表中删除指定的频率key，每步都是常数时间的操作，所以时间复杂度也是O(1)。

put操作大致包括下面几种情况

如果key已经存在，修改对应的value，并将访问频率+1
- 将元素从访问频率i的链表中移除，放到频率i+1的链表中
- 如果频率i的链表为空，则从频率哈希表中移除这个链表
如果key不存在
- 缓存超过最大容量，则先删除访问频率最低的元素，再插入新元素
- 缓存没有超过最大容量，则插入新元素

我们在代码实现中还需要维护一个minFreq的变量，用来记录LFU缓存中频率最小的元素，在缓存满的时候，可以快速定位到最小频繁的链表，以达到O(1)时间复杂度删除一个元素。
具体做法是:

更新/查找的时候，将元素频率+1，之后如果minFreq不在频率哈希表中了，说明频率哈希表中已经没有元素了，那么minFreq需要+1，否则minFreq不变。
插入的时候，这个简单，因为新元素的频率都是1，所以只需要将minFreq改为1即可。

我们重点看下缓存超过最大容量时是怎么处理的

每次新增元素时，我们都将这个元素插入到双链表的第一个位置，那么对于相同频率的元素来说，链表中最后一个位置的元素，就是最久没被访问过的。

代码部分

代码部分比较长，我对代码加了很多注释，也做了一些简单的封装。
这里自定义了一个双向链表，增加了一些自定义的函数，就当是复习下双链表吧。

java代码:

复制代码

import java.util.HashMap;
import java.util.Map;

/**
 *    自定义的LFU缓存类 
 */
public class LFUCache {
    /**
     *    双链表中的链表节点对象
    */
    protected static class Node{
        //对应输入的key
        private final int key;
  
        //对应输入的value
        private int value;
  
        //被访问的频率
        private int freq;
  
        //指向前一个节点的指针
        protected Node pre;
  
        //指向后一个节点的指针
        protected Node next;
  
        public Node(int key, int value, int freq) {
            this.key = key;
            this.value = value;
            this.freq = freq;
        }
  
        public Node(int key, int value, int freq, Node pre, Node next) {
            this.key = key;
            this.value = value;
            this.freq = freq;
            this.pre = null;
            this.next = null;
        }
  
        public void updateValue(int value) {
            this.value = value;
        }
  
        public void incrFreq() {
            ++this.freq;
        }
  
        public int getKey() {
            return this.key;
        }
  
        public int getValue() {
            return this.value;
        }
  
        public int getFreq() {
            return this.freq;
        }
  
        public static final Node createEmptyNode() {
            return new Node(-1,-1,-1,null,null);
        }
    }

/**
    *  自定义的双向链表类
    */
    protected static class LinkedList {
        //双向链表的头结点
        private final Node head;
  
        //双向链表的尾节点
        private final Node tail;
        public LinkedList() {
            this.head = Node.createEmptyNode();
            this.tail = Node.createEmptyNode();
            this.head.next = this.tail;
            this.tail.pre = this.head;
        }
  
        /**
         * 将指定的节点插入到链表的第一个位置
         * @param node 将要插入的节点
        */
        public void insertFirst(Node node) {
            if(node==null) {
                throw new IllegalArgumentException();
            }
            node.next = this.head.next;
            this.head.next.pre = node;
            node.pre = this.head;
            this.head.next = node;
        }
  
        /**
         * 从链表中删除指定的节点
         * @param node 将要删除的节点
        */
        public void deleteNode(Node node) {
            if(node==null) {
                throw new IllegalArgumentException();
            }
            node.pre.next = node.next;
            node.next.pre = node.pre;
            node.pre = null;
            node.next = null;
        }
  
        /**
         * 从链表中获取最后一个节点
         * @return 双向链表中的最后一个节点，如果是空链表则返回None
        */
        public Node getLastNode() {
            if(this.head.next==this.tail) {
                return Node.createEmptyNode();
            }
            return this.tail.pre;
        }
  
        /**
         * 判断链表是否为空，除了head和tail没有其他节点即为空链表
         * @return 链表不空返回True，否则返回False
        */
        public boolean isEmpty() {
            return this.head.next==this.tail;
        }
    } 
 
    //key->Node 这种结构的哈希表
    private final Map<Integer,Node> keyMap = new HashMap<Integer,Node>();
 
    //freq->LinkedList 这种结构的哈希表
    private final Map<Integer,LinkedList> freqMap = new HashMap<Integer,LinkedList>();
 
    //缓存的最大容量
    private final int capacity;
 
    //记录缓存中最低频率
    private int minFreq = 0;
 
    public LFUCache(int capacity) {
//  if(capacity<=0) {
//   throw new IllegalArgumentException();
//  }
        this.capacity = capacity;
    }
    
    /**
     * 获取一个元素，如果key不存在则返回-1，否则返回对应的value，同时更新被访问元素的频率
     * @param key 要查找的关键字
     * @return 如果没找到则返回-1，否则返回对应的value
     */
    public int get(int key) {
        if(!this.keyMap.containsKey(key)) {
            return -1;
        }
        Node node = this.keyMap.get(key);
        this.increment(node);
        return node.getValue();
    }
    
    /**
     * 插入指定的key和value，如果key存在则更新value，同时更新频率，
     * 如果key不存并且缓存满了，则删除频率最低的元素，并插入新元素。否则，直接插入新元素
     * @param key 要插入的关键字
     * @param value 要插入的值
     */
    public void put(int key, int value) {
        if(this.keyMap.containsKey(key)) {
            Node node = this.keyMap.get(key);
            node.updateValue(value);
            this.increment(node);
        }
        else {
            if(this.capacity==0) {
                return;
            }
            if(this.keyMap.size()==this.capacity) {
                this.remoteMinFreqNode();
            }
            Node node = new Node(key,value,1);
            this.increment(node,true);
            this.keyMap.put(key, node);
        }
    }

/**
     *  更新节点的访问频率
     * @param node 要更新的节点
     */
    private void increment(Node node) {
        increment(node,false);
    }
    
    /**
     * 更新节点的访问频率
     * @param node 要更新的节点
     * @param isNewNode 是否是新节点，新插入的节点和非新插入节点更新逻辑不同
     */
    private void increment(Node node,boolean isNewNode) {
        if(isNewNode) {
            this.minFreq = 1;
            this.insertToLinkedList(node);
        }
        else {
            this.deleteNode(node);
            node.incrFreq();
            this.insertToLinkedList(node);
            if(!this.freqMap.containsKey(this.minFreq)) {
                ++this.minFreq;
            }
        }
    }
    
    /**
     * 根据节点的频率，插入到对应的LinkedList中，如果LinkedList不存在则创建
     * @param node 将要插入到LinkedList的节点
     */
    private void insertToLinkedList(Node node) {
        if(!this.freqMap.containsKey(node.getFreq())) {
            this.freqMap.put(node.getFreq(), new LinkedList());
        }
        LinkedList linkedList = this.freqMap.get(node.getFreq());
        linkedList.insertFirst(node);
    }
    
    /**
     * 删除指定的节点，如果节点删除后，对应的双链表为空，则从__freqMap中删除这个链表
     * @param node 将要删除的节点
     */
    private void deleteNode(Node node) {
        LinkedList linkedList = this.freqMap.get(node.getFreq());
        linkedList.deleteNode(node);
        if(linkedList.isEmpty()) {
            this.freqMap.remove(node.getFreq());
        }
    }
    
    /**
     * 删除频率最低的元素，从freqMap和keyMap中都要删除这个节点，
     * 如果节点删除后对应的链表为空，则要从__freqMap中删除这个链表
     */
    private void remoteMinFreqNode() {
        LinkedList linkedList = this.freqMap.get(this.minFreq);
        Node node = linkedList.getLastNode();
        linkedList.deleteNode(node);
        this.keyMap.remove(node.getKey());
        if(linkedList.isEmpty()) {
            this.freqMap.remove(node.getFreq());
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
import java.util.HashMap;
import java.util.Map;

/**
 *    自定义的LFU缓存类 
 */
public class LFUCache {
    /**
     *    双链表中的链表节点对象
    */
    protected static class Node{
        //对应输入的key
        private final int key;
  
        //对应输入的value
        private int value;
  
        //被访问的频率
        private int freq;
  
        //指向前一个节点的指针
        protected Node pre;
  
        //指向后一个节点的指针
        protected Node next;
  
        public Node(int key, int value, int freq) {
            this.key = key;
            this.value = value;
            this.freq = freq;
        }
  
        public Node(int key, int value, int freq, Node pre, Node next) {
            this.key = key;
            this.value = value;
            this.freq = freq;
            this.pre = null;
            this.next = null;
        }
  
        public void updateValue(int value) {
            this.value = value;
        }
  
        public void incrFreq() {
            ++this.freq;
        }
  
        public int getKey() {
            return this.key;
        }
  
        public int getValue() {
            return this.value;
        }
  
        public int getFreq() {
            return this.freq;
        }
  
        public static final Node createEmptyNode() {
            return new Node(-1,-1,-1,null,null);
        }
    }

    /**
    *  自定义的双向链表类
    */
    protected static class LinkedList {
        //双向链表的头结点
        private final Node head;
  
        //双向链表的尾节点
        private final Node tail;
        public LinkedList() {
            this.head = Node.createEmptyNode();
            this.tail = Node.createEmptyNode();
            this.head.next = this.tail;
            this.tail.pre = this.head;
        }
  
        /**
         * 将指定的节点插入到链表的第一个位置
         * @param node 将要插入的节点
        */
        public void insertFirst(Node node) {
            if(node==null) {
                throw new IllegalArgumentException();
            }
            node.next = this.head.next;
            this.head.next.pre = node;
            node.pre = this.head;
            this.head.next = node;
        }
  
        /**
         * 从链表中删除指定的节点
         * @param node 将要删除的节点
        */
        public void deleteNode(Node node) {
            if(node==null) {
                throw new IllegalArgumentException();
            }
            node.pre.next = node.next;
            node.next.pre = node.pre;
            node.pre = null;
            node.next = null;
        }
  
        /**
         * 从链表中获取最后一个节点
         * @return 双向链表中的最后一个节点，如果是空链表则返回None
        */
        public Node getLastNode() {
            if(this.head.next==this.tail) {
                return Node.createEmptyNode();
            }
            return this.tail.pre;
        }
  
        /**
         * 判断链表是否为空，除了head和tail没有其他节点即为空链表
         * @return 链表不空返回True，否则返回False
        */
        public boolean isEmpty() {
            return this.head.next==this.tail;
        }
    } 
 
    //key->Node 这种结构的哈希表
    private final Map<Integer,Node> keyMap = new HashMap<Integer,Node>();
 
    //freq->LinkedList 这种结构的哈希表
    private final Map<Integer,LinkedList> freqMap = new HashMap<Integer,LinkedList>();
 
    //缓存的最大容量
    private final int capacity;
 
    //记录缓存中最低频率
    private int minFreq = 0;
 
    public LFUCache(int capacity) {
//  if(capacity<=0) {
//   throw new IllegalArgumentException();
//  }
        this.capacity = capacity;
    }
    
    /**
     * 获取一个元素，如果key不存在则返回-1，否则返回对应的value，同时更新被访问元素的频率
     * @param key 要查找的关键字
     * @return 如果没找到则返回-1，否则返回对应的value
     */
    public int get(int key) {
        if(!this.keyMap.containsKey(key)) {
            return -1;
        }
        Node node = this.keyMap.get(key);
        this.increment(node);
        return node.getValue();
    }
    
    /**
     * 插入指定的key和value，如果key存在则更新value，同时更新频率，
     * 如果key不存并且缓存满了，则删除频率最低的元素，并插入新元素。否则，直接插入新元素
     * @param key 要插入的关键字
     * @param value 要插入的值
     */
    public void put(int key, int value) {
        if(this.keyMap.containsKey(key)) {
            Node node = this.keyMap.get(key);
            node.updateValue(value);
            this.increment(node);
        }
        else {
            if(this.capacity==0) {
                return;
            }
            if(this.keyMap.size()==this.capacity) {
                this.remoteMinFreqNode();
            }
            Node node = new Node(key,value,1);
            this.increment(node,true);
            this.keyMap.put(key, node);
        }
    }
    

    /**
     *  更新节点的访问频率
     * @param node 要更新的节点
     */
    private void increment(Node node) {
        increment(node,false);
    }
    
    /**
     * 更新节点的访问频率
     * @param node 要更新的节点
     * @param isNewNode 是否是新节点，新插入的节点和非新插入节点更新逻辑不同
     */
    private void increment(Node node,boolean isNewNode) {
        if(isNewNode) {
            this.minFreq = 1;
            this.insertToLinkedList(node);
        }
        else {
            this.deleteNode(node);
            node.incrFreq();
            this.insertToLinkedList(node);
            if(!this.freqMap.containsKey(this.minFreq)) {
                ++this.minFreq;
            }
        }
    }
    
    /**
     * 根据节点的频率，插入到对应的LinkedList中，如果LinkedList不存在则创建
     * @param node 将要插入到LinkedList的节点
     */
    private void insertToLinkedList(Node node) {
        if(!this.freqMap.containsKey(node.getFreq())) {
            this.freqMap.put(node.getFreq(), new LinkedList());
        }
        LinkedList linkedList = this.freqMap.get(node.getFreq());
        linkedList.insertFirst(node);
    }
    
    /**
     * 删除指定的节点，如果节点删除后，对应的双链表为空，则从__freqMap中删除这个链表
     * @param node 将要删除的节点
     */
    private void deleteNode(Node node) {
        LinkedList linkedList = this.freqMap.get(node.getFreq());
        linkedList.deleteNode(node);
        if(linkedList.isEmpty()) {
            this.freqMap.remove(node.getFreq());
        }
    }
    
    /**
     * 删除频率最低的元素，从freqMap和keyMap中都要删除这个节点，
     * 如果节点删除后对应的链表为空，则要从__freqMap中删除这个链表
     */
    private void remoteMinFreqNode() {
        LinkedList linkedList = this.freqMap.get(this.minFreq);
        Node node = linkedList.getLastNode();
        linkedList.deleteNode(node);
        this.keyMap.remove(node.getKey());
        if(linkedList.isEmpty()) {
            this.freqMap.remove(node.getFreq());
        }
    }
}

python代码:

复制代码

class Node(object):
    """
    双链表中的链表节点对象
    """
    def __init__(self,key=None,value=None,freq=0):
        """
        Args:
            key:对应输入的key
            value:对应输入的value
            freq:被访问的频率
            pre:指向前一个节点的指针
            next:指向后一个节点的指针
        """
        self.key = key
        self.value = value
        self.freq = freq
        self.pre = None
        self.next = None
        
class LinkedList(object):
    """
    自定义的双向链表
    """
    def __init__(self):
        """
        Args:
            __head:双向链表的头结点
            __tail:双向链表的尾节点
        """
        self.__head = Node()
        self.__tail = Node()
        self.__head.next = self.__tail
        self.__tail.pre = self.__head
        
    def insertFirst(self,node):
        """
        将指定的节点插入到链表的第一个位置 
        Args:
            node:将要插入的节点    
        """
        node.next = self.__head.next
        self.__head.next.pre = node
        self.__head.next = node
        node.pre = self.__head
        
    def delete(self,node):
        """
        从链表中删除指定的节点 
        Args:
            node:将要删除的节点 
        """
        if self.__head.next==self.__tail:
            return
        node.pre.next = node.next
        node.next.pre = node.pre
        node.next = None
        node.pre = None
        
    def getLast(self):
        """
        从链表中获取最后一个节点
        Returns:
            双向链表中的最后一个节点，如果是空链表则返回None
        """        
        if self.__head.next==self.__tail:
            return None
        return self.__tail.pre
        
    def isEmpty(self):
        """
        判断链表是否为空，除了head和tail没有其他节点即为空链表
        Returns:
            链表不空返回True，否则返回False
        """  
        return self.__head.next==self.__tail

class LFUCache(object):
    """
    自定义的LFU缓存
    """
    def __init__(self, capacity):
        """
        Args:
            __capacity:缓存的最大容量
            __keyMap: key->Node 这种结构的字典
            __freqMap:freq->LinkedList 这种结构的字典
            __minFreq:记录缓存中最低频率
        """
        self.__capacity = capacity
        self.__keyMap = dict()
        self.__freqMap = dict()
        self.__minFreq = 0

def get(self, key):
        """
        获取一个元素，如果key不存在则返回-1，否则返回对应的value
        同时更新被访问元素的频率
        Args:
            key:要查找的关键字
        Returns:
            如果没找到则返回-1，否则返回对应的value
        """
        if key not in self.__keyMap:
            return -1
        node = self.__keyMap[key]
        self.__increment(node)
        return node.value

def put(self, key, value):
        """
        插入指定的key和value，如果key存在则更新value，同时更新频率
        如果key不存并且缓存满了，则删除频率最低的元素，并插入新元素
        否则，直接插入新元素
        Args:
            key:要插入的关键字
            value:要插入的值
        """
        if key in self.__keyMap:
            node = self.__keyMap[key]
            node.value = value
            self.__increment(node)
        else:
            if self.__capacity==0:
                return
            if len(self.__keyMap)==self.__capacity:
                self.__removeMinFreqElement()
            node = Node(key,value,1)
            self.__increment(node,True)
            self.__keyMap[key] = node
        
    def __increment(self,node,is_new_node=False):
        """
        更新节点的访问频率
        Args:
            node:要更新的节点
            is_new_node:是否是新节点，新插入的节点和非新插入节点更新逻辑不同
        """
        if is_new_node:
            self.__minFreq = 1
            self.__setDefaultLinkedList(node)
        else:
            self.__deleteNode(node)
            node.freq += 1
            self.__setDefaultLinkedList(node)
            if self.__minFreq not in self.__freqMap:
                self.__minFreq += 1
    
    def __setDefaultLinkedList(self,node):
        """
        根据节点的频率，插入到对应的LinkedList中，如果LinkedList不存在则创建
        Args:
            node:将要插入到LinkedList的节点
        """
        if node.freq not in self.__freqMap:
            self.__freqMap[node.freq] = LinkedList()
        linkedList = self.__freqMap[node.freq]
        linkedList.insertFirst(node)
        
    def __deleteNode(self,node):
        """
        删除指定的节点，如果节点删除后，对应的双链表为空，则从__freqMap中删除这个链表
        Args:
            node:将要删除的节点
        """
        if node.freq not in self.__freqMap:
            return
        linkedList = self.__freqMap[node.freq]
        freq = node.freq
        linkedList.delete(node)
        if linkedList.isEmpty():
            del self.__freqMap[freq]
        
    def __removeMinFreqElement(self):
        """
        删除频率最低的元素，从__freqMap和__keyMap中都要删除这个节点，如果节点删除后对应的链表为空，则要从__freqMap中删除这个链表
        """
        linkedList = self.__freqMap[self.__minFreq]
        node = linkedList.getLast()
        linkedList.delete(node)
        del self.__keyMap[node.key]
        if linkedList.isEmpty():
            del self.__freqMap[node.freq]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
class Node(object):
    """
    双链表中的链表节点对象
    """
    def __init__(self,key=None,value=None,freq=0):
        """
        Args:
            key:对应输入的key
            value:对应输入的value
            freq:被访问的频率
            pre:指向前一个节点的指针
            next:指向后一个节点的指针
        """
        self.key = key
        self.value = value
        self.freq = freq
        self.pre = None
        self.next = None
        
class LinkedList(object):
    """
    自定义的双向链表
    """
    def __init__(self):
        """
        Args:
            __head:双向链表的头结点
            __tail:双向链表的尾节点
        """
        self.__head = Node()
        self.__tail = Node()
        self.__head.next = self.__tail
        self.__tail.pre = self.__head
        
    def insertFirst(self,node):
        """
        将指定的节点插入到链表的第一个位置 
        Args:
            node:将要插入的节点    
        """
        node.next = self.__head.next
        self.__head.next.pre = node
        self.__head.next = node
        node.pre = self.__head
        
    def delete(self,node):
        """
        从链表中删除指定的节点 
        Args:
            node:将要删除的节点 
        """
        if self.__head.next==self.__tail:
            return
        node.pre.next = node.next
        node.next.pre = node.pre
        node.next = None
        node.pre = None
        
    def getLast(self):
        """
        从链表中获取最后一个节点
        Returns:
            双向链表中的最后一个节点，如果是空链表则返回None
        """        
        if self.__head.next==self.__tail:
            return None
        return self.__tail.pre
        
    def isEmpty(self):
        """
        判断链表是否为空，除了head和tail没有其他节点即为空链表
        Returns:
            链表不空返回True，否则返回False
        """  
        return self.__head.next==self.__tail

class LFUCache(object):
    """
    自定义的LFU缓存
    """
    def __init__(self, capacity):
        """
        Args:
            __capacity:缓存的最大容量
            __keyMap: key->Node 这种结构的字典
            __freqMap:freq->LinkedList 这种结构的字典
            __minFreq:记录缓存中最低频率
        """
        self.__capacity = capacity
        self.__keyMap = dict()
        self.__freqMap = dict()
        self.__minFreq = 0
        

    def get(self, key):
        """
        获取一个元素，如果key不存在则返回-1，否则返回对应的value
        同时更新被访问元素的频率
        Args:
            key:要查找的关键字
        Returns:
            如果没找到则返回-1，否则返回对应的value
        """
        if key not in self.__keyMap:
            return -1
        node = self.__keyMap[key]
        self.__increment(node)
        return node.value

    def put(self, key, value):
        """
        插入指定的key和value，如果key存在则更新value，同时更新频率
        如果key不存并且缓存满了，则删除频率最低的元素，并插入新元素
        否则，直接插入新元素
        Args:
            key:要插入的关键字
            value:要插入的值
        """
        if key in self.__keyMap:
            node = self.__keyMap[key]
            node.value = value
            self.__increment(node)
        else:
            if self.__capacity==0:
                return
            if len(self.__keyMap)==self.__capacity:
                self.__removeMinFreqElement()
            node = Node(key,value,1)
            self.__increment(node,True)
            self.__keyMap[key] = node
        
    def __increment(self,node,is_new_node=False):
        """
        更新节点的访问频率
        Args:
            node:要更新的节点
            is_new_node:是否是新节点，新插入的节点和非新插入节点更新逻辑不同
        """
        if is_new_node:
            self.__minFreq = 1
            self.__setDefaultLinkedList(node)
        else:
            self.__deleteNode(node)
            node.freq += 1
            self.__setDefaultLinkedList(node)
            if self.__minFreq not in self.__freqMap:
                self.__minFreq += 1
    
    def __setDefaultLinkedList(self,node):
        """
        根据节点的频率，插入到对应的LinkedList中，如果LinkedList不存在则创建
        Args:
            node:将要插入到LinkedList的节点
        """
        if node.freq not in self.__freqMap:
            self.__freqMap[node.freq] = LinkedList()
        linkedList = self.__freqMap[node.freq]
        linkedList.insertFirst(node)
        
    def __deleteNode(self,node):
        """
        删除指定的节点，如果节点删除后，对应的双链表为空，则从__freqMap中删除这个链表
        Args:
            node:将要删除的节点
        """
        if node.freq not in self.__freqMap:
            return
        linkedList = self.__freqMap[node.freq]
        freq = node.freq
        linkedList.delete(node)
        if linkedList.isEmpty():
            del self.__freqMap[freq]
        
    def __removeMinFreqElement(self):
        """
        删除频率最低的元素，从__freqMap和__keyMap中都要删除这个节点，如果节点删除后对应的链表为空，则要从__freqMap中删除这个链表
        """
        linkedList = self.__freqMap[self.__minFreq]
        node = linkedList.getLast()
        linkedList.delete(node)
        del self.__keyMap[node.key]
        if linkedList.isEmpty():
            del self.__freqMap[node.freq]