面试热题（LRU缓存）

逃离我推掉我的手 2023-10-14 15:39 36阅读 0赞

> 请你设计并实现一个满足 [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)` 的平均时间复杂度运行。

由于我们在维护key-value键值对的同时，还要注意它们的入队顺序，所以用普通的Map肯定是不行的（因为我亲身体验过）

![56851c9de7cd4c0eaa612434f8154816.png][]

所以我们需要一个可以自动的维护顺序的数据结构才能处理本题，所以LinikedHashMap肯定是最好的选择，在我们在刷题的时候，其实LinkedHashMap其实是不太常见的，先在这里给大家科普一下：

LinkedHashMap是一种集合类型，它实现了Map接口，并且通过双向链表维护了插入顺序或者访问顺序，与常规的HashMap相比，LinkedHashMap保持了键值对的插入顺序或访问顺序，这使得它非常适合在按需要按照顺序访问元素的场景中使用

所以要手动的去构建一个结构体，构造方法必不可少

LinkedHashMap<Integer,Integer> map=new LinkedHashMap<>();
        private int capacity;//容量
        public LRUCache(int capacity) {
            this.capacity=capacity;
        }

在我们使用的过程中，对于最新访问的key-value，我们无需对其顺序进行改变，但是如果我们去访问了一个比较使用时间过长的key-value，那么每次都要对其键值进行删除增加，这给代码带来非常差的可读性，所以我们应该重新声明一个方法（最近使用recently）

public void recently(int key){
            int val=map.get(key);
            map.remove(key);
            map.put(key,val);
        }

通过key值去获得value的值，如果没有的话直接返回-1，获取值也是一种操作，证明这个key是刚使用过的，所以直接调用函数recnetly()

public int get(int key) {
            if(!map.containsKey(key)){
                return -1;
            }
            recently(key);
            return map.get(key);
        }

如果往进put的时候，如果map的key的数量超过capacity,那就直接删除最早进来的key(很久没有使用的key值)，直接提升为最近使用，如果没有直接加入

public void put(int key, int value) {
            if(map.containsKey(key)){
                map.put(key,value);
                recently(key);
                return;
            }
            if(map.size()>=capacity){
                map.remove(map.keySet().iterator().next());
            }
            map.put(key,value);
        }

在这里给大家着重说明一下keySet().iterator().next()的功能：

> keySet():返回LinkedHashMap中的所有键的集合，该方法将返回一个Set的对象，其中包含所有的键
> 
> iterator():返回一个迭代器，用于遍历集合中的元素，在这种情况下，我们获取到的是键集合的迭代器，以便逐个访问键
> 
> next():迭代器的方法之一，用于获取下一个元素，由于我们希望获得第一个键，所以该操作将返回集合中的第一个元素

用迭代器遍历集合，当集合初始值不为空时，遍历的过程中是不会抛出异常的，因为集合遍历时用的fail-safe机制，每次遍历的时候，都是拿的原集合一个快照进行遍历，如果当遍历的时候有人对集合进行增删，结果可能就出现了问题

源码借鉴：

LinkedHashMap<Integer,Integer> map=new LinkedHashMap<>();
        private int capacity;
        public LRUCache(int capacity) {
            this.capacity=capacity;
        }
    
        public int get(int key) {
            if(!map.containsKey(key)){
                return -1;
            }
            recently(key);
            return map.get(key);
        }
    
        public void put(int key, int value) {
            if(map.containsKey(key)){
                map.put(key,value);
                recently(key);
                return;
            }
            if(map.size()>=capacity){
                map.remove(map.keySet().iterator().next());
            }
            map.put(key,value);
        }
        public void recently(int key){
            int val=map.get(key);
            map.remove(key);
            map.put(key,val);
        }

[LRU _]: https://baike.baidu.com/item/LRU
[56851c9de7cd4c0eaa612434f8154816.png]: https://img-blog.csdnimg.cn/56851c9de7cd4c0eaa612434f8154816.png