手撕LRU缓存数据结构设计 校招高频的面试题 有多高频不用我多说 你也知道 手写——从0到1 看不懂 来找我

手撕LRU缓存数据结构设计 校招高频的面试题 有多高频不用我多说 你也知道 手写——从0到1 看不懂 来找我

本篇内容：手撕LRU缓存数据结构设计 校招高频的面试题 有多高频不用我多说 你也知道 手写——从0到1

 最近更新：2020年1月4日 这是第一篇关于面试设计数据结构的面试题 这也是个板块哦~

个人简介：一只二本院校在读的大三程序猿，本着注重基础，打卡算法，分享技术作为个人的经验总结性的博文博主，虽然可能有时会犯懒，但是还是会坚持下去的，如果你很喜欢博文的话，建议看下面一行~（疯狂暗示QwQ）

 点赞  收藏 ⭐留言  一键三连 关爱程序猿，从你我做起

本文目录

• 写在前面
• LRU（最近最少未使用算法）
• • LRU算法的代码实现
  • • 步骤1：先行自定义一个双向链表的节点数据结构
    • 步骤2：初始化LRU缓存设计结构
    • 步骤3：实现双向链表的部分方法 用于实现LRU算法的设计思想
    • 步骤4：通过上述的方法与结构 完成LRU算法的put与get方法
    • 步骤5：大工完成 进行整合
• 写在最后

写在前面

为什么要更新这个板块呢？因为在问了不少优秀的学长去面试的时候，比如去（百度、网易、亚马逊、腾讯）大厂面试的学长们，一般都在二面技术，设计数据结构的基础上遇到过很多常见，且 必须能够达到手撕地步的题，所以这个版块 也就出来了~今天来介绍最最最高频的如何实现 LRU缓存，因为缓存淘汰机制在 *** 作系统的线程调度问题以及redis数据的内存淘汰策略都出现过，所以今天咱们就来实现一个比较 简单 的LRU设计实现，话不多说，冲冲冲！！！

LRU（最近最少未使用算法）

LRU 是什么？它与其他的淘汰策略算法有什么特别之处？

LRU（Least recently used，最近最少使用）算法根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。

LRU缓存设计如何实现呢？

作者这里采用的是最简单的方式：

• 先自己造个双向链表（为的是使得时间复杂度为O(1)）便于将此时获得的数据进行移位、删除、添加等等。
• 自己实现双向链表中的部分 *** 作来控制LRU缓存的设计思想
• 利用一个HashMap来存储缓存数据，便于快速查找是否存在

LRU算法的代码实现 步骤1：先行自定义一个双向链表的节点数据结构

步骤1：先行自定义一个双向链表的节点数据结构

class Node{
	//记录key与val的同时记录当前节点的pre节点与next节点 双向链表
    public int key;
    public int val;
    public Node pre;
    public Node next;
    //初始化节点
    public Node(int key ,int val){
        this.key = key;
        this.val = val;
    }
}

步骤2：初始化LRU缓存设计结构

步骤2：初始化LRU缓存设计结构

class LRUCache {
	//缓存大小
    public int capacity;
    //头结点与尾结点的初始化
    public Node head;
    public Node tail;
    //用于记录缓存中存储的数据
    public HashMapmap;
    //LRU缓存的构造
    public LRUCache(int capacity) {
        map = new HashMap<>();
		
        head = new Node(-1,-1);
        tail = new Node(-1,-1);

        head.next = tail;
        tail.pre = head;

        this.capacity = capacity;
    }
}

步骤3：实现双向链表的部分方法 用于实现LRU算法的设计思想

步骤3：实现双向链表的部分方法 用于实现LRU算法的设计思想

1、需要一个 insertTail(Node node) 的方法 用于将节点数据插入到链表尾部

	public void insertTail(Node node){
        //当前节点的pre指针为尾结点的pre节点
        node.pre = tail.pre;
        //当前节点的next节点为node节点
        node.next = tail;
        //然后更改尾结点的位置，此时尾结点的pre节点的next节点应该指向node
        tail.pre.next = node;
        //尾结点的pre节点就是node节点
        tail.pre = node;
    }

2、需要一个 delete(Node node) 的方法 用于将节点数据移除

	public void delete(Node node){
        //要删除的节点的pre节点的next节点 为当前节点的next节点
        node.pre.next = node.next;
        //要删除节点的next节点的pre节点 为当前节点的pre节点
        node.next.pre = node.pre;
    }

3、通过前两个方法 设计一个 moveToTail(Node node ,int val)的方法 用于将该次访问的数据，移至链表链尾(表示此次数据访问之后，后面还有很大概率能访问到)

	public void moveToTail(Node node,int val){
		//先将此节点删去后移至链尾
        delete(node);
        insertTail(node);
        //为其赋值
        node.val = val;
    }

步骤4：通过上述的方法与结构 完成LRU算法的put与get方法

步骤4：通过上述的方法与结构 完成LRU算法的put与get方法

1、LRU缓存设计的get(int key)方法

	public int get(int key) {
		//先尝试从缓存map中获取对应key的节点
        Node node = map.get(key);
        //如果不存在就返回-1
        if (node == null){
            return -1;
        }
        //将其移至链尾 代表最近使用过
        moveToTail(node,node.val);
        //如果可以得到节点的话返回节点的val
        return node.val;
    }

2、LRU缓存设计的 put(int key,int val)方法

	public void put(int key, int value) {
		//如果当前map缓存中存在这个key,就直接去map中找到并且将其节点移至链尾 表示最近使用过
        if(map.containsKey(key)){
            Node node = map.get(key);
            moveToTail(node,value);
        }else {
        	//如果当前缓存数据已满 则需要删除最开始的节点数据 清除其在map缓存中的位置
            if (map.size() == this.capacity){
                Node node = head.next;
                delete(node);
                map.remove(node.key);
            }
			//然后创建新的节点数据，并且添加到链尾表示最近访问过的同时将其加入到map缓存中
            Node newNode = new Node(key,value);
            insertTail(newNode);
            map.put(key,newNode);
        }
    }

步骤5：大工完成 进行整合

步骤5：大工完成 进行整合

class LRUCache {
    //缓存大小
    public int capacity;
    //头结点与尾结点的初始化
    public Node head;
    public Node tail;
    //用于记录缓存中存储的数据
    public HashMapmap;
    //LRU缓存的构造
    public LRUCache(int capacity) {
        map = new HashMap<>();
		
        head = new Node(-1,-1);
        tail = new Node(-1,-1);

        head.next = tail;
        tail.pre = head;

        this.capacity = capacity;
    }
    
	public int get(int key) {
		//先尝试从缓存map中获取对应key的节点
        Node node = map.get(key);
        //如果不存在就返回-1
        if (node == null){
            return -1;
        }
        //将其移至链尾 代表最近使用过
        moveToTail(node,node.val);
        //如果可以得到节点的话返回节点的val
        return node.val;
    }
    
	public void put(int key, int value) {
		//如果当前map缓存中存在这个key,就直接去map中找到并且将其节点移至链尾 表示最近使用过
        if(map.containsKey(key)){
            Node node = map.get(key);
            moveToTail(node,value);
        }else {
        	//如果当前缓存数据已满 则需要删除最开始的节点数据 清除其在map缓存中的位置
            if (map.size() == this.capacity){
                Node node = head.next;
                delete(node);
                map.remove(node.key);
            }
			//然后创建新的节点数据，并且添加到链尾表示最近访问过的同时将其加入到map缓存中
            Node newNode = new Node(key,value);
            insertTail(newNode);
            map.put(key,newNode);
        }
    }

	public void moveToTail(Node node,int val){
		//先将此节点删去后移至链尾
        delete(node);
        insertTail(node);
        //为其赋值
        node.val = val;
    }

    public void delete(Node node){
        //要删除的节点的pre节点的next节点 为当前节点的next节点
        node.pre.next = node.next;
        //要删除节点的next节点的pre节点 为当前节点的pre节点
        node.next.pre = node.pre;
    }

    public void insertTail(Node node){
        //当前节点的pre指针为尾结点的pre节点
        node.pre = tail.pre;
        //当前节点的next节点为node节点
        node.next = tail;
        //然后更改尾结点的位置，此时尾结点的pre节点的next节点应该指向node
        tail.pre.next = node;
        //尾结点的pre节点就是node节点
        tail.pre = node;
    }
}
class Node{
	//记录key与val的同时记录当前节点的pre节点与next节点 双向链表
    public int key;
    public int val;
    public Node pre;
    public Node next;
    //初始化节点
    public Node(int key ,int val){
        this.key = key;
        this.val = val;
    }
}

写在最后

代码实现完成了哦~

是不是LRU的内存淘汰算法的结构设计也没想象中的那么难~

重点在于 如何利用数据结构和其实现的思想 进行设计

如果有空 小付建议 去刷下力扣 的 146. LRU 缓存

建议多写 能达到默写的程度 你见到大厂的面试题 或许就不会发慌了~

最后

每天进步点 每天收获点

愿诸君 事业有成 学有所获

如果觉得不错 别忘啦一键三连哦~