如何模拟实现一个“缓存”？

谁借莪１个温暖的怀抱￠ 2023-09-23 22:17 128阅读 0赞

**目录**

前言

一、LRU Cache是什么

二、模拟实现

2.1、通过继承 LinkedHashMap 模拟实现

2.2、自主模拟实现LRU Cache

2.2.1、LRU Cache的定义

2.2.2、存放结点

2.2.3、访问结点

2.2.4、LRU Cache 完整模拟代码

小结

--------------------

# 前言 #

这次主要实现一个类似缓存的一种数据结构，缓存（Cache）容量有限，当容量用完后有新的数据添加进来，就需要将原来不常用的数据清除掉，再加入新的数据；

--------------------

# 一、LRU Cache是什么 #

LRU Cache的**底层是**一个双向链表 + 哈希表的结构，这样做**是为了**要达到一个时间复杂度为O(1)的存放元素以及获取元素（双向链表插入删除元素和哈希表查找元素可以到达O(1)），**功能是**将经常使用的元素放在链表的尾部，不常使用的放在链表的头部，当容量用完了后再添加元素时，就会把头部不经常用的元素删除掉；

![ded24b6a5612492899354b57748db467.png][]

#  #

--------------------

# 二、模拟实现 #

## 2.1、通过继承 LinkedHashMap 模拟实现 ##

LinkedHashMap 底层也是双向链表 + 哈希表，其中有一个构造方法，若参数置为 false 时，会按照插入顺序进行排序，若参数置为 true 时，会按照访问顺序（也就是插入和访问都会将当前节点放置到尾部，尾部代表的是最近访问的数据），我们这里需要模拟实现 LRU Cache ，所以参数需要设置为 true ；

> 代码如下：

import java.util.LinkedHashMap;
    import java.util.Map;
    
    public class LRUCache extends LinkedHashMap<Integer, Integer> {
    
        public int capacity;//容量
        public LRUCache(int capacity) {
            //这里的true代表基于访问顺序
            super(capacity, 0.75F, true);
            this.capacity = capacity;//指定容量
        }
    
        @Override
        public Integer get(Object key) {
            return super.getOrDefault(key, -1);
        }
    
        public Integer put(Integer key, Integer value) {
            return super.put(key, value);
        }
    
        /**
         * 为什么要重写这个方法？
         * 因为达到某个条件为 true 就会删除头节点
         * @param eldest
         * @return
         */
        @Override
        protected  boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
            return size() > capacity;
        }
    
    }

## 2.2、自主模拟实现LRU Cache ##

### 2.2.1、LRU Cache的定义 ###

这里只需要顶一个双向链表和一个HashMap即可；

import java.util.HashMap;
    import java.util.Map;
    
    public class MyLRUCache {
        //双向链表
        static class DLinkNode {
            public int key;
            public int value;
            public DLinkNode prev;
            public DLinkNode next;
    
            public DLinkNode() {
    
            }
    
            public DLinkNode(int key, int value) {
                this.key = key;
                this.value = value;
            }
        }
    
        public DLinkNode head;//双向链表的头节点
        public DLinkNode tail;//双向链表的尾结点
        public int usedSize;//当前双向链表中有效数据的个数
        public Map<Integer, DLinkNode> map;
        public int capacity;//容量
    
        public MyLRUCache(int capacity) {
            this.head = new DLinkNode();
            this.tail = new DLinkNode();
            head.next = tail;
            tail.prev = head;
            this.cache = new HashMap<>();
            this.capacity = capacity;
        }
    
    
    }

### 2.2.2、存放结点 ###

首先检查当前结点是否之前存放过，若没有存放过，就将这个结点存储到尾巴的位置，若之前有存储过该节点，就把之前的结点移动到尾巴的位置即可；

/**
         * 存储元素
         * @param key
         * @param val
         */
        public void put(int key, int val) {
            //1.查找当前这个keu是不是存储过；
            DLinkNode node = cache.get(key);
            //2.如果没有存储过
            if(node == null) {
                //2.1需要实例化一个结点
                DLinkNode dLinkNode = new DLinkNode(key, val);
                //2.2存储到map中
                cache.put(key, dLinkNode);
                //2.3把该结点存储到链表尾巴
                addToTail(dLinkNode);
                usedSize++;
                //2.4检查当前双向链表的有效数据个数 是不是超过了capacity
                if(usedSize > capacity) {
                    //2.5超过了就要移除头部结点
                    DLinkNode remNode = removeHead();
                    //2.6清除cache中的元素
                    cache.remove(remNode.key);
                    //2.6usedSize--;
                    usedSize--;
                }
            } else {
                //3.如果存储过
                //3.1更新这个key对应的val
                node.val = val;
                //3.2然后将该结点移到尾部(因为这个是新插入的数据)
                moveToTail(node);
            }
        }
    
        /**
         * 移动当前结点到尾巴结点
         * @param node
         */
        private void moveToTail(DLinkNode node) {
            //1.先删除这个结点
            removeNode(node);
            //2.添加到尾部
            addToTail(node);
        }
    
        /**
         * 删除指定结点
         * @param node
         */
        private void removeNode(DLinkNode node) {
            node.prev.next = node.next;
            node.next.prev = node.prev;
        }
    
    
        /**
         * 添加结点到链表的尾部
         * @param node
         */
        private void addToTail(DLinkNode node) {
            tail.prev.next = node;
            node.prev = tail.prev;
            node.next = tail;
            tail.prev = node;
        }
    
        /**
         * 删除头部结点
         * @return
         */
        private DLinkNode removeHead() {
            DLinkNode del = head.next;
            head.next = del.next;
            del.next.prev = head;
            return del;
        }

### 2.2.3、访问结点 ###

实际上就是将访问到的结点放到尾巴结点处即可（经常使用的）

/**
         * 访问当前key
         * 逻辑：将访问的结点放到尾巴
         * @param key
         * @return
         */
        public int get(int key) {
            DLinkNode node = cache.get(key);
            if(node == null) {
                return -1;
            }
            //把最近经常使用的放到尾巴
            moveToTail(node);
            return node.val;
        }

### 2.2.4、LRU Cache 完整模拟代码 ###

import java.util.HashMap;
    import java.util.Map;
    
    public class MyLRUCache {
        //双向链表
        static class DLinkNode {
            public int key;
            public int val;
            public DLinkNode prev;
            public DLinkNode next;
    
            public DLinkNode() {
    
            }
    
            public DLinkNode(int key, int value) {
                this.key = key;
                this.val = value;
            }
    
            @Override
            public String toString() {
                return "key=" + key +
                        ", val=" + val;
            }
        }
    
        public DLinkNode head;//双向链表的头节点
        public DLinkNode tail;//双向链表的尾结点
        public int usedSize;//当前双向链表中有效数据的个数
        public Map<Integer, DLinkNode> cache;
        public int capacity;//容量
    
        public MyLRUCache(int capacity) {
            this.head = new DLinkNode();
            this.tail = new DLinkNode();
            head.next = tail;
            tail.prev = head;
            this.cache = new HashMap<>();
            this.capacity = capacity;
        }
    
        /**
         * 存储元素
         * @param key
         * @param val
         */
        public void put(int key, int val) {
            //1.查找当前这个keu是不是存储过；
            DLinkNode node = cache.get(key);
            //2.如果没有存储过
            if(node == null) {
                //2.1需要实例化一个结点
                DLinkNode dLinkNode = new DLinkNode(key, val);
                //2.2存储到map中
                cache.put(key, dLinkNode);
                //2.3把该结点存储到链表尾巴
                addToTail(dLinkNode);
                usedSize++;
                //2.4检查当前双向链表的有效数据个数 是不是超过了capacity
                if(usedSize > capacity) {
                    //2.5超过了就要移除头部结点
                    DLinkNode remNode = removeHead();
                    //2.6清除cache中的元素
                    cache.remove(remNode.key);
                    //2.6usedSize--;
                    usedSize--;
                }
            } else {
                //3.如果存储过
                //3.1更新这个key对应的val
                node.val = val;
                //3.2然后将该结点移到尾部(因为这个是新插入的数据)
                moveToTail(node);
            }
        }
    
        /**
         * 移动当前结点到尾巴结点
         * @param node
         */
        private void moveToTail(DLinkNode node) {
            //1.先删除这个结点
            removeNode(node);
            //2.添加到尾部
            addToTail(node);
        }
    
        /**
         * 删除指定结点
         * @param node
         */
        private void removeNode(DLinkNode node) {
            node.prev.next = node.next;
            node.next.prev = node.prev;
        }
    
    
        /**
         * 添加结点到链表的尾部
         * @param node
         */
        private void addToTail(DLinkNode node) {
            tail.prev.next = node;
            node.prev = tail.prev;
            node.next = tail;
            tail.prev = node;
        }
    
        /**
         * 删除头部结点
         * @return
         */
        private DLinkNode removeHead() {
            DLinkNode del = head.next;
            head.next = del.next;
            del.next.prev = head;
            return del;
        }
    
        /**
         * 访问当前key
         * 逻辑：将访问的结点放到尾巴
         * @param key
         * @return
         */
        public int get(int key) {
            DLinkNode node = cache.get(key);
            if(node == null) {
                return -1;
            }
            //把最近经常使用的放到尾巴
            moveToTail(node);
            return node.val;
        }
    
        public void printNode(String str) {
            DLinkNode cur = head.next;
            while( cur != tail) {
                System.out.println(cur);
                cur = cur.next;
            }
        }
    }

--------------------

# 小结 #

建议多写多练~

--------------------

![47554ee512f84de998acd3e9e15710d2.gif][]

[ded24b6a5612492899354b57748db467.png]: https://img-blog.csdnimg.cn/ded24b6a5612492899354b57748db467.png
[47554ee512f84de998acd3e9e15710d2.gif]: https://img-blog.csdnimg.cn/47554ee512f84de998acd3e9e15710d2.gif