LRU 算法简单实现

不念不忘少年蓝@ 2022-05-16 02:26 201阅读 0赞

最近看innoDb缓存池实现的时候，提到了LRU的算法，后面看了下memcached的实现也提到了LRU算法，正好leetcode146题，就是讲这个LRU算法的，所以就写个简单实现。

> 设计一个支持在*平均 *时间复杂度 **O(1)** 下，执行以下操作的数据结构。
> 
> 1.  `insert(val)`：当元素 val 不存在时，向集合中插入该项。
> 2.  `remove(val)`：元素 val 存在时，从集合中移除该项。
> 3.  `getRandom`：随机返回现有集合中的一项。每个元素应该有**相同的概率**被返回。
> 
> **示例 :**
> 
>     // 初始化一个空的集合。
>     RandomizedSet randomSet = new RandomizedSet();
>     
>     // 向集合中插入 1 。返回 true 表示 1 被成功地插入。
>     randomSet.insert(1);
>     
>     // 返回 false ，表示集合中不存在 2 。
>     randomSet.remove(2);
>     
>     // 向集合中插入 2 。返回 true 。集合现在包含 [1,2] 。
>     randomSet.insert(2);
>     
>     // getRandom 应随机返回 1 或 2 。
>     randomSet.getRandom();
>     
>     // 从集合中移除 1 ，返回 true 。集合现在包含 [2] 。
>     randomSet.remove(1);
>     
>     // 2 已在集合中，所以返回 false 。
>     randomSet.insert(2);
>     
>     // 由于 2 是集合中唯一的数字，getRandom 总是返回 2 。
>     randomSet.getRandom();

这里我选择使用hashmap和一个链表来实现。hashmap用来存储节点，链表来维护节点先后顺序。

LRU算法每次取数据时，先判断hashmap中是不是有这个节点，如果有就返回该节点维护的value，并且将该节点的顺序放到链表的最前面，所以最开始新增两个辅助节点，头节点和尾节点。

LRU算法每次存数据时，先判断hashmap中有没有该key的节点，如果有，就更新该key的值，同时将该节点的是顺序放到链表的最前面。

这里有个注意的点，链表的容量如果是限定的，那么就需要考虑这次添加新的节点，会不会导致hashmap的size会超过链表的容量。如果超过，那么就要去掉链表最后的节点，也就是该节点的key对应的hashmap中的内容。

假设，当前hashmap的size已经到达了链表的初始容量，那么这时候新插入值就会有三种情况：

1. 新值在hashmap中并没有

2. 新值在hashmap中有，并且是最后一个节点

3. 新值在hashmap中有，并且非最后一个节点

这三种情况，最主要的一个要设计的点就是如果再插入会导致hashmap的size大于链表的初始容量，什么时候去删掉链表最后一个节点。

import java.util.HashMap;
    
    /**
     * @author by csucoderlee
     * @created on 2018 08 14 16:08
     * @description LRU least recently used 最近最少使用, 如果数据最近被访问过，那么将来被访问的几率也会很高
     * 最常见的实现，维护一个链表，新数据都插入链表头，缓存命中的数据也会被移动到链表头，
     * 当链表满时，链表尾部的数据也会被丢弃
     * 缺点就是缓存命中后，需要遍历链表找到对应的数据，移动到链表头
     *
     */
    public class LruTest {
    
        public static void main(String[] args) {
    
        }
    }
    
    class LRUCache {
    
    
        private HashMap<Integer, Node> map;
    
        private int size;
    
        private int capacity;
    
        Node head;
    
        Node tail;
    
        public LRUCache(int capacity) {
            this.capacity = capacity;
            this.size = 0;
            this.head = new Node(0,0);
            this.tail = new Node(0,0);
            map = new HashMap<>();
            this.head.next = this.tail;
            this.tail.pre = this.head;
        }
    
        public int get(int key) {
            Node node = map.get(key);
            if (null == node) {
                return -1;
            }
            removeNode(node);
            addHeadNode(node);
            return node.value;
        }
    
        public void put(int key, int value) {
            if(map.containsKey(key)){
                Node target = map.get(key);
                target.value = value;
                removeNode(target);
                addHeadNode(target);
            }else {
                Node newNode = new Node(key,value);
                map.put(key,newNode);
                if(size>=capacity){
                    map.remove(this.tail.pre.key);
                    removeNode(this.tail.pre);
                    this.size--;
                }
                addHeadNode(newNode);
                this.size++;
            }
        }
    
        private void removeNode(Node node) {
            node.pre.next = node.next;
            node.next.pre = node.pre;
            node.pre = null;
            node.next = null;
        }
    
        private void addHeadNode(Node node) {
            node.next = this.head.next;
            node.next.pre = node;
            this.head.next = node;
            node.pre = this.head;
        }
    
        class Node {
    
            int key;
            int value;
            Node pre;
            Node next;
    
            public Node(int key, int value) {
                this.key = key;
                this.value = value;
                this.pre = null;
                this.next = null;
            }
    
        }
    }