当前位置：首页 > article >正文

设计LFU缓存结构（美团面试算法题）

article 2025/1/11 22:50:19

美团一面算法题： LFU缓存结构实现 & 最长公共子序列。后者就不细说了，经典dp，属于秒杀题。
第一题在面试时只说了思路，面试官表示思路正确，但最终没实现出来（有点尴尬）
面试后总结了一下，该题总的来说不难，只是我很久没刷题有点荒于算法了（还是要勤刷题啊），遇到一个hard题可以想到大致思路，但动手实现时总是抓不住细节，另外，面试和平时还是不一样的，会有一些压力和紧迫感。一些经典的hard算法题还是要熟悉一下，该题显然就属于此。

前言

LRU 和LFU是两种著名的缓存淘汰算法。LRU 算法的淘汰策略是 Least Recently Used，也就是每次淘汰那些最久没被使用的数据；LFU 算法的淘汰策略是 Least Frequently Used，也就是每次淘汰那些使用次数最少的数据。

LRU 算法的核心数据结构是使用哈希链表 LinkedHashMap，首先借助链表的有序性使得链表元素维持插入顺序，同时借助哈希映射的快速访问能力使得我们可以在 O(1) 时间访问链表的任意元素。

从实现难度上来说，LFU 算法的难度大于 LRU 算法，因为 LRU 算法相当于把数据按照时间排序，这个需求借助链表很自然就能实现，你一直从链表头部加入元素的话，越靠近头部的元素就是新的数据，越靠近尾部的元素就是旧的数据，我们进行缓存淘汰的时候只要简单地将尾部的元素淘汰掉就行了。

而 LFU 算法相当于是把数据按照访问频次进行排序，这个需求恐怕没有那么简单，而且还有一种情况，如果多个数据拥有相同的访问频次，我们就得删除最早插入的那个数据。也就是说 LFU 算法是淘汰访问频次最低的数据，如果访问频次最低的数据有多条，需要淘汰最旧的数据。

所以说 LFU 算法是要复杂很多的，而且经常出现在面试中，因为 LFU 缓存淘汰算法在工程实践中经常使用。

LRU缓存结构

LRU缓存结构是LFU缓存结构的初级版，我们可以先实现一下LRU缓存，熟悉它的结构。
如上所述，LRU 算法的淘汰策略是 Least Recently Used，每次淘汰那些最久没被使用的数据。我们可以双向链表+哈希表，在双向链表中维护每一个插入的键值对，当插入新结点时始终采用头插，如果插入或查询已有结点，则将该结点移至链表头部。

双向链表+哈希表

public class LRUCache {

    static class DequeNode {
        int key;
        int val;
        DequeNode pre;
        DequeNode next;
        public DequeNode(){}
        public DequeNode(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }

    private int size; // 当前容量
    private final int capacity; // 限制大小
    private final Map<Integer, DequeNode> map; // 数据和链表中节点的映射
    private final DequeNode head; // 头结点 避免null检查
    private final DequeNode tail; // 尾结点 避免null检查


    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.map = new HashMap<>();
        this.head = new DequeNode();
        this.tail = new DequeNode();
        this.head.next = tail;
        this.tail.pre = head;
    }

    // 取key对应的值，如果不存在返回null
    public Integer get(Integer key) {
        if(!map.containsKey(key)) return null;
        // 数据在链表中，则移至链表头部
        DequeNode node=map.get(key);
        if(head.next!=node){
            remove(node);
            insert(head,node);
        }
        return node.val;
    }

    // 插入（key,value）
    public void set(Integer key, Integer value) {
        if(!map.containsKey(key)){
            eliminate();
            DequeNode newNode = new DequeNode(key, value);
            insert(head, newNode);
            map.put(key, newNode);
        }else{
            DequeNode node=map.get(key);
            node.val=value;
            if(head.next!=node){
                remove(node);
                insert(head,node);
            }
        }
    }

    // 在preNode后插入新结点
    private void insert(DequeNode preNode, DequeNode newNode){
        DequeNode tmp=preNode.next;
        preNode.next=newNode;
        newNode.pre=preNode;
        newNode.next=tmp;
        tmp.pre=newNode;
        size++;
    }

    // 删除结点
    private void remove(DequeNode node){
        DequeNode pre=node.pre, next=node.next;
        pre.next=next;
        next.pre=pre;
        size--;
        node=null;
    }

    // 删除尾部结点直至有空余容量
    private void eliminate() {
        while (size >= capacity){
            // 将链表中最后一个节点去除
            DequeNode last = tail.pre;
            map.remove(last.key);
            remove(last);
        }
    }

    public String toString(){
        StringBuilder str=new StringBuilder("");
        str.append("[");
        DequeNode node=head.next;
        while (node!=tail){
            str.append("[").append(node.key).append(",").append(node.val).append("]");
            if(node!=tail.pre) str.append(",");
            node=node.next;
        }
        str.append("]");
        return str.toString();
    }

    public static void main(String[] args){
        LRUCache lru=new LRUCache(3);
        System.out.println(lru);
        lru.set(1,1);
        System.out.println(lru);
        lru.set(2,2);
        System.out.println(lru);
        lru.set(3,2);
        System.out.println(lru);
        lru.set(2,4);
        System.out.println(lru);
        int val=lru.get(3);
        System.out.println(val);
        System.out.println(lru);
    }
}

输出：

[]
[[1,1]]
[[2,2],[1,1]]
[[3,2],[2,2],[1,1]]
[[2,4],[3,2],[1,1]]
2
[[3,2],[2,4],[1,1]]

时空复杂度分析：set()和get()的时间复杂度都是O(1)，空间复杂度为O(N)

LinkedHashMap

其实我们可以直接根据JDK给我们提供的LinkedHashMap直接实现LRU。因为LinkedHashMap的底层即为双向链表和哈希表的组合，所以可以直接拿来使用。

class LRUCache{
    private final int capacity;
    private final LinkedHashMap<Integer, Integer> mp;

    public LRUCache(int capacity) {
        // 注意这里将LinkedHashMap的accessOrder设为true
        mp=new LinkedHashMap<>(16,0.75f,true);
        this.capacity = capacity;
    }

    public Integer get(int key){
        return mp.get(key);
    }

    public void set(int key, int val){
        mp.put(key,val);
        eliminate();
    }

    private void eliminate() {
        while (mp.size() > capacity){
            // 将最后一个节点去除
            mp.remove(mp.entrySet().iterator().next().getKey());
        }
    }
}

更方便地，我们可以直接继承LinkedHashMap类

class LRUCache extends LinkedHashMap<Integer, Integer>{
    private final int capacity;

    public LRUCache(int capacity) {
        // 注意这里将LinkedHashMap的accessOrder设为true
        super(16, 0.75f, true);
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry eldest) {
        return super.size() > capacity;
    }
}

默认LinkedHashMap并不会淘汰数据，所以我们重写了它的removeEldestEntry()方法，当数据数量达到预设上限后，淘汰数据，accessOrder设为true意为按照访问的顺序排序。整个实现的代码量并不大，主要都是应用LinkedHashMap的特性。

LFU缓存结构

题目大意

一个缓存结构需要实现如下功能。

set(key, value)：将记录(key, value)插入该结构
get(key)：返回key对应的value值

但是缓存结构中最多放K条记录，如果新的第K+1条记录要加入，就需要根据策略删掉一条记录，然后才能把新记录加入。这个策略为：在缓存结构的K条记录中，哪一个key从进入缓存结构的时刻开始，被调用set或者get的次数最少，就删掉这个key的记录；
如果调用次数最少的key有多个，上次调用发生最早的key被删除
这就是LFU缓存替换算法。实现这个结构，K作为参数给出

数据范围： $\le 10^5 ，|val| \le 2 \times 10^9$
要求：get和set的时间复杂度都是 O(logn)，空间复杂度是 O(n)

若opt=1，接下来两个整数x, y，表示set(x, y)
若opt=2，接下来一个整数x，表示get(x)，若x未出现过或已被移除，则返回-1

对于每个操作2，返回一个答案

示例1

输入： [[1,1,1],[1,2,2],[1,3,2],[1,2,4],[1,3,5],[2,2],[1,4,4],[2,1]],3
输出： [4,-1]
说明：在执行"1 4 4"后，"1 1 1"被删除。因此第二次询问的答案为-1

优先队列、哈希表和LinkedHashSet

在面试时的第一直觉是使用优先队列维护（key，value），通过交流后，面试官也对我的思路予以认同。但可惜当时忽然忘记怎么重定义一个数据结构的排序规则（其实很简单，应该是面试时有点紧张，一直想不起来）。

具体思路是：

使用一个哈希表维护（key，value）的映射关系
使用一个哈希表维护（key，freq）的映射关系
自定义二叉堆（这里对优先队列和二叉堆不做区分）的结点值LfuNode，使每个结点保存对应频率和该频率下出现的所有key，其中该频率下出现的所有key用LinkedHashSet保存
使用一个哈希表维护（freq，LfuNode）的映射关系
后续的操作就非常简单了。插入（key，value）时，如果key已存在，则在原有频率结点中删除key，在新的频率结点中增加key；如果key不存在，则在频率为1的结点中增加key。取key对应的值时，如果key存在，则在原有频率结点中删除key，在新的频率结点中增加key，并返回对应的value；否则返回-1。如果有删除key的操作，我们需要判断对应结点是否还存有数据，若无数据，则从优先队列中删除该结点，剩余结点会根据优先队列的性质自动排序（我这里重写了二叉堆结点的比较函数）；如果有新增key的操作，需要判断当前缓存结构是否会超出容量，如果会超容，则删除优先队列中头部结点的第一个元素（同样需要判断删除后该结点是否还有效）。
值的注意的是，我们使用了三个哈希表、一个LinkedHashSet和一个优先队列，其中哈希表增删改查的时间复杂度都为O(1)，LinkedHashSet删除/新增头尾节点的时间复杂度为O(1)，优先队列插入和删除的时间复杂度为O(logn)。所有数据结构的空间复杂度均为O(n)。所以满足题目要求：get和set的时间复杂度都是 O(logn)，空间复杂度是 O(n)。

class LFUCache{

    private static class LfuNode implements Comparable<LfuNode>{
        int fre;
        LinkedHashSet<Integer> kSet =new LinkedHashSet<>();
        public LfuNode(){}
        public LfuNode(int fre){
            this.fre=fre;
        }

        @Override
        public int compareTo(LfuNode o) {
            return Integer.compare(this.fre, o.fre);
        }
    }

    private int size; // 当前容量
    private final int capacity; // 限制大小
    private final Map<Integer,Integer> k2v;
    private final Map<Integer,Integer> k2f;
    private final Map<Integer,LfuNode> f2L;
    private final PriorityQueue<LfuNode> pq;

    public LFUCache(int capacity){
        this.capacity=capacity;
        k2v=new HashMap<>();
        k2f=new HashMap<>();
        f2L=new HashMap<>();
        pq=new PriorityQueue<>();
    }

    public void set(int key, int val){
        if(k2v.containsKey(key)){
            k2v.put(key,val);//更新k2v
            int fre=k2f.get(key);
            k2f.put(key,fre+1);//更新k2f
            LfuNode lNode=f2L.get(fre);
            lNode.kSet.remove(key);//删除原有频率结点中的key
            check(lNode);
            addKey(fre+1,key);//将key插入到fre+1对应的结点中
        }else{
            eliminate();
            k2v.put(key,val);//更新k2v
            k2f.put(key,1);//更新k2f
            addKey(1,key);
            size++;
        }
    }

    public int get(int key){
        int val=-1;
        if(k2v.containsKey(key)){
            val=k2v.get(key);
            int fre=k2f.get(key);
            k2f.put(key,fre+1);//更新k2f
            LfuNode lNode=f2L.get(fre);
            lNode.kSet.remove(key);//删除原有频率结点中的key
            check(lNode);
            addKey(fre+1,key);//将key插入到fre+1对应的结点中
        }
        return val;
    }

    // 向对应的频率结点中插入key
    private void addKey(int fre, int key){
        if(f2L.containsKey(fre)){
            f2L.get(fre).kSet.add(key);
        }else{
            LfuNode ln=new LfuNode(fre);
            ln.kSet.add(key);
            f2L.put(fre,ln);
            pq.offer(ln);
        }
    }

    // 检查结点是否有效，如无效做出对应操作
    private void check(LfuNode ln){
        //如果该频率结点已无key，则从优先队列中删除，并更新f2L
        if(ln.kSet.size()==0){
            pq.remove(ln);
            f2L.remove(ln.fre);
        }
    }

    // 删除优先队列首部结点直至有空余容量
    private void eliminate() {
        while (size >= capacity && !pq.isEmpty()){
            LfuNode ln=pq.peek();
            int key=ln.kSet.iterator().next();
            ln.kSet.remove(key);
            check(ln);
            k2v.remove(key);
            k2f.remove(key);
            size--;
        }
    }

    public String toString(){
        StringBuilder str=new StringBuilder("");
        str.append("[");
        Iterator<LfuNode> iter=pq.iterator();
        while (iter.hasNext()){
            LfuNode ln=iter.next();
            for(int i:ln.kSet){
                str.append("[").append(i).append(",").append(k2v.get(i)).append("]");
            }
            if(iter.hasNext()) str.append(",");
        }
        str.append("]");
        return str.toString();
    }

}

public class Solution {
    /**
     * lfu design
     * @param operators int整型二维数组 ops
     * @param k int整型 the k
     * @return int整型一维数组
     */
    public int[] LFU (int[][] operators, int k) {
        // write code here
        int m=operators.length;
        LFUCache lfu=new LFUCache(k);
        List<Integer> resList=new ArrayList<>();
        for(int[] op:operators){
            if(op[0]==1){
                lfu.set(op[1],op[2]);
            }else{
                resList.add(lfu.get(op[1]));
            }
//             System.out.println(lfu.toString());
        }
        return resList.stream().mapToInt(Integer::intValue).toArray();
    }
    
}