手撕LRU和LFU缓存淘汰算法

女爷i 2024-03-24 10:22 77阅读 0赞

**目录**

一.LRU缓存淘汰算法

1.LRU基本介绍

2.LRU算法描述

3.LRU算法设计

4.代码实现

二.LFU缓存淘汰算法

1.LFU基本介绍

2.LFU算法描述

3.LFU算法设计

4.代码实现

--------------------

## 一.LRU缓存淘汰算法 ##

### 1.LRU基本介绍 ###

LRU（**Least Recently Used**，最近最少使用）算法是一种用于**页面置换**的算法，通常应用于操作系统的虚拟内存管理中。其原理是，当**内存不足时，系统会将最久未被使用的页面（也就是最近最少使用的页面）替换出内存，从而腾出空间供新的页面使用**。

LRU算法维护了一个页面使用的时间戳队列，每当一个页面被访问时，就将其对应的时间戳更新为当前时间，并将该页面移到队列的末尾。当内存不足时，系统就会将队列头部的页面替换出内存，因为这些页面的时间戳最早，即它们是最久未被使用的页面。

在实现LRU算法时，需要考虑以下几个方面：

1.  数据结构：需要维护一个访问页面先后的队列，可以选择链表实现的哈希表实现。
2.  页面访问：每当一个页面被访问时，需要将其对应的时间戳更新为当前时间，并将该页面移到队列的末尾。
3.  页面替换：当内存不足时，需要将队列头部的页面替换出内存，即将时间戳最早的页面移除队列。

LRU算法的优点是**相对简单，容易实现**，并且可以有效地利用缓存，提高系统的性能。但其缺点也显而易见，即需要维护一个时间戳队列，因此其空间复杂度较高，且在某些特殊情况下，可能会出现“抖动”现象，即同一页面频繁被访问(LFU可以解决这个问题)，但仍然被频繁替换出内存的情况。

我们在实现的时候,一般直接在链表的先后表示页面最后访问时间的先后,在链表的头部(队列的头部)表示最久未被使用过,链表的尾部(队列的尾部)表示最近被使用过.

### 2.LRU算法描述 ###

力扣上:[力扣][Link 1] 给出了描述我们需要实现的功能

> 请你设计并实现一个满足LRU(最近最少使用)约束的数据结构。
> 
> 实现 `LRUCache` 类：
> 
>  *  `LRUCache(int capacity)` 以 **正整数** 作为容量 `capacity` 初始化 LRU 缓存
>  *  `int get(int key)` 如果关键字 `key` 存在于缓存中，则返回关键字的值，否则返回 `-1` 。
>  *  `void put(int key, int value)` 如果关键字 `key` 已经存在，则变更其数据值 `value` ；如果不存在，则向缓存中插入该组 `key-value` 。如果插入操作导致关键字数量超过 `capacity` ，则应该 **逐出** 最久未使用的关键字。
> 
> 函数 `get` 和 `put` 必须以 `O(1)` 的平均时间复杂度运行。

class LRUCache {
    
        public LRUCache(int capacity) {
    
        }
        
        public int get(int key) {
    
        }
        
        public void put(int key, int value) {
    
        }
    }

### 3.LRU算法设计 ###

题目要求我们函数 `get` 和 `put` 必须以 `O(1)` 的平均时间复杂度运行,因此我们第一想到的就是哈希.但是我们使用什么哈希结构呢?有人可能会想到使用HashMap,但是有一个问题,我们需要删除最久未使用的,而HashMap是根据hashcode存储的,也就是说它的**存储顺序和遍历顺序不一致**,因此我们不能考虑使用HashMap,有没有一种结构存储顺序和遍历顺序一致,并且还含有哈希结构呢?有的,就是LinkedHashMap,不理解这种哈希结构的建议看一下这篇博客:[详解LinkedHashSet和LinkedHashMap\_允歆辰丶的博客-CSDN博客][LinkedHashSet_LinkedHashMap_-CSDN]

确定了这一种结构之后,LRU算法实现起来就很简单了,在get()方法中,我们只需要把访问的结点(key-val)放到队列的尾端(抽象为一个方法:makeRecently),然后获取key对应的value即可,没有包含key就返回-1;

对于put()方法,需要考虑三种情况:

①:当已经包含了key对应的value,我们只需要修改key对应的value,然后将其置为队尾(makeRecently),然后结束即可

②:当已经达到了最大容量的时候,我们需要删除最久未使用的元素(队首元素),然后添加key-val

③:未包含key对应的value并且未达到最大容量,直接添加到队尾即可

### 4.代码实现 ###

public class LRUCache {
        LinkedHashMap<Integer, Integer> map = new LinkedHashMap<>();
        int size = 0;
    
        public LRUCache(int capacity) {
            size = capacity;
    
        }
    
        //将key对应的value放在LinkedHashMap的最后
        public void makeRecently(int key) {
            Integer remove = map.remove(key);
            map.put(key, remove);
    
        }
    
        //如果不存在key对应的value,返回-1,否则将key对应的value放到队尾,并获取值
        public int get(int key) {
            if (map.containsKey(key)) {
                makeRecently(key);
                return map.get(key);
            }
            return -1;
    
    
        }
    
        public void put(int key, int value) {
            //已经存在值了,修改key对应的value,并将key对应的value放到队尾
            if (map.containsKey(key)) {
                map.put(key, value);
                makeRecently(key);
                return;
            }
            //超过最大容量,将队首的key对应的value删除
            if (map.size() >= size) {
                Integer next = map.keySet().iterator().next();
                map.remove(next);
            }
            //将新的key对应的value加入到队尾
            map.put(key, value);
    
    
        }
    }

## 二.LFU缓存淘汰算法 ##

### 1.LFU基本介绍 ###

LFU（**Least Frequently Used**）算法是一种用于**缓存替换**的算法，其思想是**淘汰最少被使用的缓存数据**。它的基本原理是根据每个数据块的**使用频率来决定其是否被淘汰**。LFU算法主要用于高速缓存中，以保证缓存空间的高效利用。

LFU算法的实现需要一个**计数器来记录每个数据块被使用的次数**，当缓存空间满了时，选择使用频率最低的数据块进行替换。如果多个数据块的使用**频率相同**，则选择**最早**使用的**数据块**进行**替换**。

LFU算法的优点在于它能够较好地适应不同访问模式下的缓存需求，并且能够保证缓存空间的高效利用。但是，LFU算法的实现比较复杂，需要维护一个计数器来记录每个数据块的使用频率，并且容易受到访问热点的影响。

### 2.LFU算法描述 ###

力扣上:[力扣][Link 2] 给出了描述我们需要实现的功能

> 请你为最不常使用(LFU)缓存算法设计并实现数据结构。
> 
> 实现 `LFUCache` 类：
> 
>  *  `LFUCache(int capacity)` \- 用数据结构的容量 `capacity` 初始化对象
>  *  `int get(int key)` \- 如果键 `key` 存在于缓存中，则获取键的值，否则返回 `-1` 。
>  *  `void put(int key, int value)` \- 如果键 `key` 已存在，则变更其值；如果键不存在，请插入键值对。当缓存达到其容量 `capacity` 时，则应该在插入新项之前，移除最不经常使用的项。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，应该去除 **最近最久未使用** 的键。
> 
> 为了确定最不常使用的键，可以为缓存中的每个键维护一个 **使用计数器** 。使用计数最小的键是最久未使用的键。
> 
> 当一个键首次插入到缓存中时，它的使用计数器被设置为 `1` (由于 put 操作)。对缓存中的键执行 `get` 或 `put` 操作，使用计数器的值将会递增。
> 
> 函数 `get` 和 `put` 必须以 `O(1)` 的平均时间复杂度运行。

class LFUCache {
    
        public LFUCache(int capacity) {
    
        }
        
        public int get(int key) {
    
        }
        
        public void put(int key, int value) {
    
        }
    }

### 3.LFU算法设计 ###

LFU相关实现十分复杂,我们首先需要确定三个基本的参数 ①:一个HashMap存储keyToValue(KV表)②:一个HashMap存储keyToFreq(KF表)③:一个HashMap存储freqToKeys(FK表) 同时我们还需要参数minFreq来记录最小的频次,因为最小频次对应的key可能不止一个,所以freqToKeys的值应该用一个集合来存储

这个集合需要满足三个条件

**1.**因为调用get()方法的时候,需要增加key对应的频次,因此能够在freqToKeys的key集合中快速找到对应的key删除,增加到freq+1键对应的keys集合中,因此这个集合最好为**哈希集合**

**2.**又因为题目中描述删除最小的频次的元素,可能存在多了,此时要删除**最近最久未使用,**根据上一题的经验我们可知,我们最好用**LinkedHashSet集合,**这样才能保证**添加顺序和遍历顺序一致**

**确定了数据结构之后我们开始实现对应的方法**

**get()方法,当不存在key对应的value时候,我们还是返回-1,当存在时:增加key所对应的频次(抽象成一个方法increaseFrequent)**

**put()方法,当key存在时候,更新key对应的value,增加频次(increaseFrequent),返回即可 判断是否达到最大容量,如果达到,删除最小频次的key-value(抽象为方法removeMinFrequentKey) 然后进行添加操作,将key-value对添加到KV表,对应的频次1添加到KF表,将1对应的key添加到keys集合中,如果不存在,新建集合加入.**

**接下来我们分析两个最关键的方法:increaseFrequent 和 removeMinFrequentKey**

**increaseFrequent** :**我们需要把key对应的频次进行改变,所以我们要修改KF表和FK表,KF表容易修改,只需要修改key对应的频次修改为+1的值即可,再来修改FK表,此时将频次freq对应的keys集合的key进行删除,然后将freq+1的keys集合中加入key(如果不存在keys集合,新建keys集合加入),此时我们其实还是有瑕疵的,当我们删除freq对应的keys集合的key是,如果删除之后keys集合为空,我们应该将freq-keys键值对进行删除,并且如果freq为最小频次的话,我们此时应该更新minFreq为freq+1;**

**removeMinFrequentKey:我们需要删除最小频次对应的keys集合中的队首元素(也就是最小频次中最近最久未使用的key),同样的:如果删除keys集合的key之后keys集合为空,我们应该将minFreq-keys键值对进行删除,但是此时是否要更新minFreq呢?答案是不需要,因为我们删除最小频次的元素一定之后对应着添加元素,我们在put方法中已经更新过最小频次了.之后我们更新KF表和KV表即可**

### 4.代码实现 ###

class LFUCache {
        //KV表
        HashMap<Integer, Integer> keyToValue = new HashMap<>();
        //KF表
        HashMap<Integer, Integer> keyToFreq = new HashMap<>();
        //FK表
        HashMap<Integer, LinkedHashSet<Integer>> freqToKeys = new HashMap<>();
        int minFreq = 0;
        int capacity;
    
        public LFUCache(int capacity) {
            this.capacity = capacity;
    
        }
    
        //不存在返回-1,存在增加频次,然后返回value
        public int get(int key) {
            if (!keyToValue.containsKey(key)) {
                return -1;
            }
            increaseFrequent(key);
            return keyToValue.get(key);
    
        }
    
        private void increaseFrequent(int key) {
            int freq = keyToFreq.get(key);
            //更新KF表
            keyToFreq.put(key, freq + 1);
            //更新FK表
            //删除freq对应的key值
            freqToKeys.get(freq).remove(key);
            //如果freq对应的LinkedHashSet空了,直接删除
            if (freqToKeys.get(freq).isEmpty()) {
                freqToKeys.remove(freq);
                //如果此时正好减少的为minFreq对应的,更新minFreq
                if (minFreq == freq) {
                    this.minFreq++;
                }
    
            }
            //将入到freq加1的表(不存在新建一个)
            LinkedHashSet<Integer> set = freqToKeys.getOrDefault(freq + 1, new LinkedHashSet<>());
            set.add(key);
            freqToKeys.put(freq + 1, set);
    
        }
    
        public void put(int key, int value) {
            if (this.capacity <= 0)
                return;
            //已经存在key了,这个时候修改值,并且增加频次
            if (keyToValue.containsKey(key)) {
                keyToValue.put(key, value);
                increaseFrequent(key);
                return;
            }
            //已经达到最大容量,删除最小频次的
            if (capacity <= keyToValue.size()) {
                removeMinFrequentKey();
            }
            //存入key,value
            keyToValue.put(key, value);
            //将此key对应的频次加入KF表
            keyToFreq.put(key, 1);
            //获取频次1对应的LinkedHashSet表,将对应的key加入
            LinkedHashSet<Integer> set = freqToKeys.getOrDefault(1, new LinkedHashSet<>());
            set.add(key);
            freqToKeys.put(1, set);
            //因为是新添加的,最新的频次(也就时最小频次)是1
            this.minFreq = 1;
    
    
        }
    
        private void removeMinFrequentKey() {
            //更新FK表
            LinkedHashSet<Integer> set = freqToKeys.get(minFreq);
            //最小频次的最近最久未使用的key
            int deleteKey = set.iterator().next();
            set.remove(deleteKey);
            if (set.isEmpty()) {
                freqToKeys.remove(this.minFreq);
                //此时没必要更新minFreq,因此此操作一定伴随着添加新的key,value,在put()方法中更新了minFreq
            }
            //更新KV表
            keyToValue.remove(deleteKey);
            //更新KF表
            keyToFreq.remove(deleteKey);
    
        }
    }

[Link 1]: https://leetcode.cn/problems/lru-cache/
[LinkedHashSet_LinkedHashMap_-CSDN]: https://blog.csdn.net/qq_64580912/article/details/129797848
[Link 2]: https://leetcode.cn/problems/lfu-cache/