设计LFU缓存

设计LFU缓存

需求描述

这是一道来自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-&gt;Node 这种结构的字典
            __freqMap:freq-&gt;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]
                                                                                      
5 次阅读

发表评论

电子邮件地址不会被公开。