概述
目录
需求描述
设计详解
LFU总体概览
细说get和put
代码部分
需求描述
这是一道来自LeetCode的设计题目，题目内容如下:
请你为最不经常使用（LFU） 缓存算法设计并实现数据结构。它应该支持以下操作：get 和 put。get(key) - 如果键存在于缓存中，则获取键的值（总是正数），否则返回 -1。put(key, value) - 如果键已存在，则变更其值；如果键不存在，请插入键值对。当缓存达到其容量时，则应该在插入新项之前，使最不经常使用的项无效。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，应该去除 最近 最少使用的键。
「项的使用次数」就是自插入该项以来对其调用 get 和 put 函数的次数之和。使用次数会在对应项被移除后置为 0 。
进阶：
你是否可以在 O(1) 时间复杂度内执行两项操作？
示例：
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());
}
}
}
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]
欢迎扫描关注公众号 ，有更多图解的算法面试题等你哦~
最后
以上就是哭泣钢笔为你收集整理的【图解数据结构】如何设计一个LFU缓存？？的全部内容，希望文章能够帮你解决【图解数据结构】如何设计一个LFU缓存？？所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复