IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 高频算法题之LRU -> 正文阅读

[数据结构与算法]高频算法题之LRU

前言

面试官:你了解过reids的内存淘汰策略么?
面试者:嗯,了解过,biubiu。。。
面试官:打断一下,如果让你去实现LRU算法,你该如何实现?
面试者:我就会用linkedHashMap实现。。。
面试官:好了,你的情况我大概知道了,你先回去等通知吧
面试者:就是又挂了呗。。

什么是LRU

LRU 缓存淘汰算法就是一种常用策略。LRU 的全称是 Least Recently Used,也就是说我们认为最近使用过的数据应该是是「有用的」,很久都没用过的数据应该是无用的,内存满了就优先删那些很久没用过的数据。
如redis的内存淘汰策略就有LRU

算法实现思路

  1. 假设定义一个哈希链表阈值为5来存放用户信息,目前缓存了4个用户信息(001,002,003,004),这4个用户按照被访问的时间顺序依次从链表右端插入(001,002,003,004)。
  2. 如果现在业务查询005用户,哈希链表中没有则从数据库获取,由于当前容量为超过阈值,可以直接插入到缓存链表中,此时005是最新被访问的用户,则存在哈希链表最右端,那么在最左端的001用户是最近最少访问。(001,002,003,004,005)
  3. 如果接下来访问的是002用户信息,则002为最新被访问的用户需要将002位置移动到最右端。(001,003,004,005,002)
  4. 如果当前业务查006用户信息,则由于哈希链表中没有需要先到数据库查询,然后再插入到哈希链表中,但由于当前容量为6超过了哈希链表的阈值,则需要先淘汰最近最少访问的用户,也就是要删除哈希链表最左端的001用户,然后才将006插入到哈希链表中最右端。(003,004,005,002,006)

LRU代码实现

/**
 * lru
 * @author winter
 */
public class LRUCache {
    /**
     * 最左端 也是最近最少访问的元素位置
     */
    private  Node head;
    /**
     * 最右端 也是最新被访问的元素位置
     */
    private  Node end;
    /**
     * 缓存的上限
     */
    private int limit;

    private HashMap<String,Node> hashMap;

    public LRUCache(int limit){
        this.limit =limit;
        hashMap = new HashMap<String,Node>();
    }

    /**
     * 获取缓存的内容
     * @param key key
     * @return
     */
    public String get (String key){
        //查询key是否存在,不存在直接返回
        Node node = hashMap.get(key);
        if (node == null){
            return null;
        }
        //存在则需要更新key位置到最右端
        refreshNode(node);
        return node.value;
    }

    /**
     * 添加元素
     * @param key key
     * @param value value
     */
    public void put(String key,String value){
        //获取到节点信息
        Node node = hashMap.get(key);
        //判断key是否存在
        if(node == null){
            //key不存在 则先判断哈希的容量是否有超过阈值
            if(hashMap.size()>=limit){
                //超过阈值先要删掉最左端的元素
                String oldKey=removeNode(head);
                hashMap.remove(oldKey);
            }
            //插入新节点
            node = new Node(key,value);
            addNode(node);
            hashMap.put(key,node);
        }else {
            //key存在,则更新值并刷新key的位置到最右端
            node.value = value;
            refreshNode(node);
        }
    }

    /**
     * 删除元素
     * @param key key
     */
    public void remove (String key){
        //获取到节点信息
        Node node = hashMap.get(key);
        //删除节点
        refreshNode(node);
        //删除元素
        hashMap.remove(key);
    }

    /**
     * 刷新被访问的位置
     * @param node
     */
    private void refreshNode(Node node){
        //如果访问就是最右端则,不需要移动节点
        if(node == end){
            return;
        }
        //不是最右端元素,则需要先删除该元素
        removeNode(node);
        //新增到哈希链表的最右端
        addNode(node);
    }

    /**
     * 删除节点
     * @param node
     * @return
     */
    private String removeNode(Node node){
        if(node == head && node == end){
            //只有一个节点,删除唯一节点
            head = null;
            end = null;
        }else if (node == end){
            //该节点是尾节点
            end = end .pre;
            end =null ;
        } else if(node == head){
            //该节点是头节点
            head = head.next;
            head.pre = null;
        }else {
            //该节点是中间节点
            node.pre.next =node.next;
            node.next.pre = node.pre;
        }

        return node.key;
    }

    /**
     * 插入尾节点
     * @param node
     */
    private void addNode(Node node){
        if (end!=null){
            end.next = node;
            node.pre = end;
            node.next =null;
        }
        end =node;
        if (head == null){
            head = node;
        }
    }

    /**
     * 链表
     */
    class Node {
        Node(String key, String value) {
            this.key = key;
            this.value = value;
        }

        public Node pre;
        public Node next;
        public String key;
        public String value;
    }
}

总结

按照上述的思路来实现LRU算法并不是太难,后续作者理解更深理解后会继续更新相关内容。

  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2021-07-05 20:27:23  更:2021-07-05 20:27:31 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年11日历 -2024/11/25 16:55:52-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码