手撕LRU和LFU缓存淘汰算法

2023-04-13

int key put

目录一.LRU缓存淘汰算法1.LRU基本介绍2.LRU算法描述3.LRU算法设计4.代码实现二.LFU缓存淘汰算法1.LFU基本介绍2.LFU算法描述3.LFU算法设计4.代码实现一.LRU缓存淘汰算法1.LRU基本介绍LRU（LeastRecentlyUsed，最近最少使用）算法是一种用于页面置换

一.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算法时，需要考虑以下几个方面：

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

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

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

2.LRU算法描述

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

请你设计并实现一个满足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博客

确定了这一种结构之后,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算法描述

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

请你为最不常使用(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);
 
    }
}