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

追求适度,才能走向成功;人在顶峰,迈步就是下坡;身在低谷,抬足既是登高;弦,绷得太紧会断;人,思虑过度会疯;水至清无鱼,人至真无友,山至高无树;适度,不是中庸,而是一种明智的生活态度。

导读:本篇文章讲解 如何模拟实现一个“缓存”?,希望对大家有帮助,欢迎收藏,转发!站点地址:www.bmabk.com,来源:原文

目录

前言

一、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)),功能是将经常使用的元素放在链表的尾部,不常使用的放在链表的头部,当容量用完了后再添加元素时,就会把头部不经常用的元素删除掉;

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


二、模拟实现

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;
        }
    }
}

小结

建议多写多练~


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

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

文章由半码博客整理,本文链接:https://www.bmabk.com/index.php/post/130386.html

(0)

相关推荐

发表回复

登录后才能评论
半码博客——专业性很强的中文编程技术网站,欢迎收藏到浏览器,订阅我们!