算法设计与分析课件 60 LFU缓存算法

算法设计与分析本节要点CONTENTSLFU缓存算法LFU缓存算法LRU（LeastRecentlyUsed）是最近最少使用算法，每次淘汰使用时间最早的数据。LFU（LeastFrequentlyUsed）是最不经常使用算法，每次淘汰使用频率最低的数据。与LRU一样，LFU也是常用的缓存置换算法，在Redis内部实现了LFU算法。LFU缓存算法LFU算法有两个基本操作：get(key)：如果键key存在于缓存中，则返回key对应的值val，否则返回-1。put(key,value)：如果键key已存在，则变更其值为value；如果键不存在，则插入键值对(key,value)。当缓存达到其容量capacity时，则应该在插入新的键值对之前，删除使用频率freq最低的键值对。如果存在多个使用频率最低的键值对，则删除使用时间最早的那个。LFU缓存算法根据上述两个基本操作，分析得出：（1）节点应包含3个信息：键key，值val，频率freq。（2）get(key)方法，采用哈希表，建立key到节点的映射。（3）put(key,value)方法，当缓存达到其容量capacity时，需要删除使用频率freq最低的键值对。采用哈希链表，建立freq到链表的映射。（4）需要两个变量：最小频率minfreq，缓存容量capacity。LFU缓存算法哈希表key_table，建立key到节点的映射。LFU缓存算法哈希链表freq_table，建立freq到链表的映射。LFU缓存算法1.get(key)方法如果键key没有在缓存中，直接返回-1。如果key存在于缓存中，则通过哈希表key_table找到key对应的节点p，返回该节点对应的值val。访问后该节点的频率增1，而且访问的时间为最新，需要做以下4处修改。LFU缓存算法a）删除1：在freq_table中，删除freq对应链表中的节点p。如果删除节点p后，freq对应的链表为空，还需要执行删除2，删除该频率的哈希映射。b）删除2：在freq_table中，删除freq的哈希映射，如果最小频率正好为freq（被删除），则更新最小频率minfreq增1。c）插入1：在freq_table中，将新节点（值不变，频率增1）插入到freq+1对应的链表表头（时间最新）。d）插入2：在key_table中，建立key到新节点的映射。LFU缓存算法例如，LFU缓存如下图所示，执行get(2)操作。LFU缓存算法（1）首先通过哈希表key_table找到key对应的节点p，执行a)操作。在freq_table中，删除freq对应链表中的节点p。删除节点p后，频率1对应的链表为空，还需要执行b)操作，删除该频率的哈希映射，更新最小频率minfreq为2。LFU缓存算法（2）因为访问后该节点的频率增1，而且访问的时间为最新，执行c)操作。在freq_table中，将新节点（值不变，频率增1）插入到频率2对应的链表表头（时间最新）。执行d)操作，在key_table中，建立key到新节点的映射。LFU缓存算法2.put(key,value)方法如果key存在于缓存中，则通过哈希表key_table找到key对应的节点p，接下来除了将新节点值改为value之外，与get操作基本一致。如果键key没有在缓存中，需要执行插入操作。插入新节点之前，判断如果缓存已满，则删除使用频率freq最低的键值对。如果存在多个使用频率最低的键值对，则删除使用时间最早的那个。需要做以下5处修改（缓存已满时才需要执行删除）。LFU缓存算法a）删除1：在freq_table中，找到minfreq对应链表的末尾节点q，并删除minfreq对应链表的末尾节点。如果删除末尾节点后，minfreq对应的链表为空，还需要执行删除2，删除该频率的哈希映射。b）删除2：在freq_table中，删除minfreq的哈希映射。这里不需要更新最小频率minfreq，因为插入新节点的频率为1，最后更新minfreq为1即可。c）删除3：在key_table中，删除q节点的哈希映射。d）插入1：在freq_table中，将新节点（键为key，值为value，频率为1）插入到频率1对应的链表表头（时间最新）。e）插入2：在key_table中，建立key到新节点的映射。更新最小频率minfreq为1。LFU缓存算法例如，LFU缓存如图所示，执行put(3,8)操作。LFU缓存算法（1）键key没有在缓存中，需要执行插入操作。此时缓存已满，需要执行a)、c)操作。删除使用频率最低且使用时间最早的那个节点，删除后链表非空，不需要执行b)操作。LFU缓存算法（2）插入新节点，执行a)、c)操作。在freq_table中，将新节点（键为3，值为8，频率为1）插入到频率1对应的链表表头（时间最新）。在key_table中，建立key到新节点的映射。更新最小频率minfreq为1。LFU缓存算法算法实现LFU缓存算法算法分析时间复杂度：