设计实现一个LRU Cache

短命女 2022-05-13 04:28 139阅读 0赞

## 什么是LRU Cache ##

在LeetCode上有一个LRU Cache实现的题目

> Design and implement a data structure for Least Recently Used (LRU)  
> cache. It should support the following operations: get and set.  
> get(key) - Get the value (will always be positive) of the key if the  
> key exists in the cache, otherwise return -1. set(key, value) - Set or  
> insert the value if the key is not already present. When the cache  
> reached its capacity, it should invalidate the least recently used  
> item before inserting a new item.

*  解题思路：题目让设计一个LRU Cache，即根据LRU算法设计一个缓存。在这之前需要弄清楚LRU算法的核心思想，LRU全称是Least  
    Recently Used，即最近最久未使用。

在操作系统的内存管理中，有一类很重要的算法就是内存页面置换算法（包括FIFO，LRU,LFU等几种常见页面置换算法）。  
事实上，Cache算法和内存页面置换算法的核心思想是一样的：都是在给定一个限定大小的空间的前提下，设计一个原则如何来更新和访问其中的元素。

*  LRU算法的设计原则

如果一个数据在最近一段时间没有被访问到，那么在将来它被访问的可能性也很小  
也就是说，当限定的空间已存满数据时，应当把最久没有被访问到的数据淘汰

*  而用什么数据结构来实现LRU算法呢？

可能大多数人都会想到：用一个数组来存储数据，给每一个数据项标记一个访问时间戳，每次插入新数据项的时候，先把数组中存在的数据项的时间戳自增，并将新数据项的时间戳置为0并插入到数组中。每次访问数组中的数据项的时候，将被访问的数据项的时间戳置为0。当数组空间已满时，将时间戳最大的数据项淘汰。  
这种实现思路很简单，但是有什么缺陷呢？需要不停地维护数据项的访问时间戳，另外，在插入数据、删除数据以及访问数据时，时间复杂度都是O(n),数组的缺陷凸显无疑

*  那么有没有更好的实现办法呢？

那就是利用链表和HashMap。当需要插入新数据项，在链表中

> 命中，则把该节点移到链表头部  
> 不存在，则新建一个节点，放在链表头部，若缓存满，则把链表最后一个节点删除即可。  
> 在访问数据时，若数据项在链表中存在，则把该节点移到链表头部，否则返回-1  
> 这样一来在链表尾部的节点就是最近最久未访问的数据项。

1）set(key,value)

若key在hashmap中存在，则先重置value，然后获取对应节点cur，将其从链表删除，并移到链表头  
不存在，则新建一个节点，并将节点放到链表的头部。  
当Cache满，删除链表最后一个节点

2）get(key)

若key在hashmap中存在，把对应的节点放到链表头，并返回对应value  
若不存在，则返回-1  
即保证基本的get/set同时，还要保证最近访问(get或put)的节点保持在限定容量的Cache中，如果超过容量则应该把LRU(近期最少使用)的节点删除掉。

当我们在get/set一个节点时都会把操作的这个节点移动到tail节点处，代表最新操作的节点，head节点永远指向最老的节点，当超过设定的容量时，我们就删除head节点指向的最老节点

就像是个LinkedHashMap，这样做的好处是，get/set在不冲突情况下可保证O(1)复杂度  
也可通过双向链表保证LRU的删除/更新O(1)复杂度

当然可简化head和tail变成一个head节点，成环，这样head的next指向最旧的节点，prev指向最新的节点。

## 实现思路 ##

在学习了HashMap和LinkedHashMap后，是不是觉得这俩数据结构简直太适合做LRU Cache了！那么动手实现一下：

## 基于HashMap和双向链表的实现 ##

/** LRU Cache 题目描述： Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put. get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1. put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item. Follow up: Could you do both operations in O(1) time complexity? 思路： 双向链表和hashmap。 1.当需要插入新的数据项的时候，如果新数据项在链表中存在（一般称为命中），则把该节点移到链表头部， 如果不存在，则新建一个节点，放到链表头部 若缓存满了，则把链表最后一个节点删除即可。 2.在访问数据的时候，如果数据项在链表中存在，则把该节点移到链表头部，否则返回-1。 这样一来在链表尾部的节点就是最近最久未访问的数据项。 */
    public class LRUCache<K , V> {
    
        class Node<K,V> {
            Node pre;
            Node next;
            private final K key;
            V val;
    
            Node(K k, V v) {
                key = k;
                val = v;
            }
        }
    
        Map<K, Node> map = new HashMap<K, Node>();
    
        // The head (eldest) of the doubly linked list.
        Node head;
        // The tail (youngest) of the doubly linked list.
        Node tail;
    
        int cap;
    
        public LRUCache(int capacity) {
            cap = capacity;
            head = new Node(null, null);
            tail = new Node(null, null);
            head.next = tail;
            tail.pre = head;
        }
    
        public V get(K key) {
            Node n = map.get(key);
            if(n!=null) {
                removeNode(n);
                appendTail(n);
                return (V) n.val;
            }
            return null;
        }
    
        public void set(K key, V value) {
            Node n = map.get(key);
            // existed
            if(n!=null) {
                n.val = value;
                map.put(key, n);
                removeNode(n);
                appendTail(n);
                return;
            }
    
            if(map.size() == cap) {
               removeLast();
            }
            n = new Node(key, value);
            // youngest node append tail
            appendTail(n);
            map.put(key, n);
        }
    
        //移除最近最少使用的节点，注意此节点就是head.next指向的节点
        public void removeLast() {
            Node tmp = head.next;
            removeNode(tmp);
            map.remove(tmp.key);
        }
    
        //移除某个节点，并将此节点的前后节点连接起来
        private void removeNode(Node n){
            n.pre.next = n.next;
            n.next.pre = n.pre;
        }
    
        //将节点加入到队列的尾部，尾部代表最近使用的节点
        private void appendTail(Node n) {
            n.next = tail;
            n.pre = tail.pre;
            tail.pre.next = n;
            tail.pre = n;
        }
    }

基于LinkedHashMap的实现

public class LRUCache<K , V> {
    
        private int capacity;
        private Map<K, V> cache;
    
        public LRUCache(final int capacity) {
            this.capacity = capacity;
            this.cache = new java.util.LinkedHashMap<K, V> (capacity, 0.75f, true) {
                // 定义put后的移除规则，大于容量就删除eldest
                protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
                    return size() > capacity;
                }
            };
        }
    
        public V get(K key) {
            if (cache.containsKey(key)) {
                return cache.get(key);
            } else
                return null;
        }
    
        public void set(K key, V value) {
            cache.put(key, value);
        }
    }