自己动手来实现一下Redis的LRU缓存机制

刺骨的言语ヽ痛彻心扉 2023-01-12 15:55 26阅读 0赞

![2091d87a978d9768e1ea07610a782349.png][]

*来源：blog.csdn.net/Grady00/article/details/115168822*

## 前言 ##

最近在逛博客的时候看到了有关Redis方面的面试题，其中提到了Redis在内存达到最大限制的时候会使用LRU等淘汰机制，然后找了这方面的一些资料与大家分享一下。

LRU总体大概是这样的，最近使用的放在前面，最近没用的放在后面，如果来了一个新的数，此时内存满了，就需要把旧的数淘汰，那为了方便移动数据，肯定就得使用链表类似的数据结构，再加上要判断这条数据是不是最新的或者最旧的那么应该也要使用hashmap等key-value形式的数据结构。

## 第一种实现(使用LinkedHashMap) ##

public class LRUCache {
    
        int capacity;
        Map<Integer,Integer> map;
    
        public LRUCache(int capacity){
            this.capacity = capacity;
            map = new LinkedHashMap<>();
        }
    
        public int get(int key){
            //如果没有找到
            if (!map.containsKey(key)){
                return -1;
            }
            //找到了就刷新数据
            Integer value = map.remove(key);
            map.put(key,value);
            return value;
        }
    
        public void put(int key,int value){
            if (map.containsKey(key)){
                map.remove(key);
                map.put(key,value);
                return;
            }
            map.put(key,value);
            //超出capacity，删除最久没用的即第一个,或者可以复写removeEldestEntry方法
            if (map.size() > capacity){
                map.remove(map.entrySet().iterator().next().getKey());
            }
        }
    
        public static void main(String[] args) {
            LRUCache lruCache = new LRUCache(10);
            for (int i = 0; i < 10; i++) {
                lruCache.map.put(i,i);
                System.out.println(lruCache.map.size());
            }
            System.out.println(lruCache.map);
            lruCache.put(10,200);
            System.out.println(lruCache.map);
        }

![41f832aad2ce49d6a9fc9db769861c5c.png][]

## 第二种实现(双链表+hashmap) ##

public class LRUCache {
    
        private int capacity;
        private Map<Integer,ListNode>map;
        private ListNode head;
        private ListNode tail;
    
        public LRUCache2(int capacity){
            this.capacity = capacity;
            map = new HashMap<>();
            head = new ListNode(-1,-1);
            tail = new ListNode(-1,-1);
            head.next = tail;
            tail.pre = head;
        }
    
        public int get(int key){
            if (!map.containsKey(key)){
                return -1;
            }
            ListNode node = map.get(key);
            node.pre.next = node.next;
            node.next.pre = node.pre;
            return node.val;
        }
    
        public void put(int key,int value){
            if (get(key)!=-1){
                map.get(key).val = value;
                return;
            }
            ListNode node = new ListNode(key,value);
            map.put(key,node);
            moveToTail(node);
    
            if (map.size() > capacity){
                map.remove(head.next.key);
                head.next = head.next.next;
                head.next.pre = head;
            }
        }
    
        //把节点移动到尾巴
        private void moveToTail(ListNode node) {
            node.pre = tail.pre;
            tail.pre = node;
            node.pre.next = node;
            node.next = tail;
        }
    
        //定义双向链表节点
        private class ListNode{
            int key;
            int val;
            ListNode pre;
            ListNode next;
    
            //初始化双向链表
            public ListNode(int key,int val){
                this.key = key;
                this.val = val;
                pre = null;
                next = null;
            }
        }
    }

像第一种方式，如果复写removeEldestEntry会更简单，这里简单的展示一下

public class LRUCache extends LinkedHashMap<Integer,Integer> {
        private int capacity;
        
        @Override
        protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
            return size() > capacity;
        }
    }

推荐好文

[强大，10k+点赞的 SpringBoot 后台管理系统竟然出了详细教程！][10k_ SpringBoot]

[分享一套基于SpringBoot和Vue的企业级中后台开源项目，代码很规范！][SpringBoot_Vue]

[能挣钱的，开源 SpringBoot 商城系统，功能超全，超漂亮][SpringBoot]![f25d5aa3aa06529c976676601f5fbd20.png][]

[2091d87a978d9768e1ea07610a782349.png]: /images/20221022/c3c47d47ada848baae9442a77d011392.png
[41f832aad2ce49d6a9fc9db769861c5c.png]: /images/20221022/d7b997dc58e44e9b8c700bc724723d14.png
[10k_ SpringBoot]: http://mp.weixin.qq.com/s?__biz=MzI4Njc5NjM1NQ%3D%3D&chksm=ebd5c411dca24d07446a4f22772cd12d2cc1143b62eb922a14500ae981cd57fb850ef74ca257&idx=2&mid=2247498557&scene=21&sn=84902d7030e174e152615d8fae3755cc#wechat_redirect
[SpringBoot_Vue]: http://mp.weixin.qq.com/s?__biz=MzU2MTI4MjI0MQ%3D%3D&chksm=fc799be6cb0e12f0b58479f8b031bc5ae79efdca1880ff9b19f0a107c3a88c37b9596dc73203&idx=2&mid=2247497288&scene=21&sn=65d7111a19e920df1e9416959594b2f4#wechat_redirect
[SpringBoot]: http://mp.weixin.qq.com/s?__biz=MzU2MTI4MjI0MQ%3D%3D&chksm=fc799a9ccb0e138a64a2671f31b8d4be1b3c061a288f7b0d1d4af02a60c45a72231446b91e00&idx=2&mid=2247497522&scene=21&sn=c5b4e596be4ac7d7f293e7e2f0ea0769#wechat_redirect
[f25d5aa3aa06529c976676601f5fbd20.png]: /images/20221022/e816d0b49eb24ae58200d5a8be5478f6.png