精华内容
下载资源
问答
  • LRU缓存淘汰算法

    2021-09-27 09:58:04
    LRU缓存淘汰算法 算法分析:LRU(Lest Recently Used):最近最少使用 扩展:FIFO(First In,First out),先进先出算法(可以用队列实现) LFU(List Frequently Used)最少使用. 1、如果数据存列表中,找到对应的节点...

    LRU缓存淘汰算法

    算法分析:LRU(Lest Recently Used):最近最少使用
    扩展:FIFO(First In,First out),先进先出算法(可以用队列实现)
    LFU(List Frequently Used)最少使用.
    1、如果数据存列表中,找到对应的节点,并删除。把这个节点插入到头部。
    2、如果没有缓存在列表中,则插在头部。
    3、如果这是的缓存的大小机制,还应该判断是否满,如果满应该删除最后一个节点。
    本次代利用的是单链表实现,下以篇引入哈希表降低时间复杂度
    降低时间复杂度的lru

    1、关键代码

    注意:我的代码没写缓存大小的限制

    	public void lur(int data) {
    		Node node=new Node();
    			 node.data=data;
    			 Node temp=head;//头指针永远指向头
    		while(temp!=null) {
    			if(temp.data==data) {
    				del(data);//删除该节点
    				node.next=head;//插在头部
    				head=node;//头指针永远指向头	
    				break;
    			}
    			if(temp.next==null) {
    				node.next=head;
    				head=node;
    				break;
    			}
    			else {
    				temp=temp.next;
    			}
    		
    		}	
    	}
    

    完整代码

    这是包含增删改遍历的链表解释请看
    JAVA手写链表实现增删改

    public class Chain {
    	/**
    	 * 
    	 * @author 远航小陈家
    	 * Node:定义node的结构
    	 *
    	 */
       class Node {
    		public  int data;
    		public   Node next;
    	}
       /**
        * 定义头节点和尾节点
        * 尾节点永远指向最后一个元素
        */
    	private Node head=null;
    	private Node tail=null;
    	/**
    	 * 
    	 * 向链表中添加元素
    	 * @param data :类型int类型
    	 * @return :插入成功返回ture
    	 */
    	public boolean add(int data) {
    		if(head==null) {
    			Node headNode=new Node();
    			headNode.data=data;
    			head=headNode;
    			tail=headNode;
    			return true;
    		}
    		else {
    			Node node=new Node();
    			node.data=data;
    			tail.next=node;
    			tail=node;
    			return true;
    		}
    		
    	}
    	/**
    	 * 更改链表中的所有元素
    	 * @param data:原链表中的元素
    	 * @param target:修改后的值
    	 * @return:修改成功返回true,失败返回false
    	 */
    	
    	public boolean update(int data,int target) {
    		Node node =new Node();
    		node.data=data;
    		Node temp=head;
    		while(temp!=null) {
    			if(temp.data==data) {
    				temp.data=target;
    				return true;
    			}
    			else {
    				temp=temp.next;
    			}
    			
    		}	
    		return false;
    	}
    	
    	/**
    	 * 
    	 * 删除链表中的元素
    	 * @param data
    	 * @return:删除成功返回true,失败返回false;
    	 */
    	
    	public boolean del(int data) {
    		
    		Node node=new Node();
    		node.data=data;
    		if(head.data==node.data) {
    			head=head.next;
    			return true; 
    		}
    		else {
    			Node pre=head;//记录删除节点的前驱节点
    			Node target=head.next;
    			while(target!=null) {
    				if(target.data==node.data) {
    					pre.next=target.next;
    					return true;
    				}
    				else {					
    					pre=pre.next;
    					target=target.next;
    				}
    			}
    		}
    		return false;
    	}
    	/**
    	 * 
    	 * @param data 需要缓存的数据
    	 */
    	
    	public void lur(int data) {
    		Node node=new Node();
    			 node.data=data;
    			 Node temp=head;//头指针永远指向头
    		while(temp!=null) {
    			if(temp.data==data) {
    				del(data);//删除该节点
    				node.next=head;//插在头部
    				head=node;//头指针永远指向头	
    				break;
    			}
    			if(temp.next==null) {
    				node.next=head;
    				head=node;
    				break;
    			}
    			else {
    				temp=temp.next;
    			}
    		
    		}	
    	}
    	
    	
    	
    	/**
    	 * 遍历链表的所有元素
    	 */
    	public void printNode() {
    		while(head!=null) {
    			int data=head.data;
    			head=head.next;
    			System.out.println(data);
    		}
    	}
    	
    	
    
    }
    

    算法分析

    因为需要遍历找到是否存在数据,最好的情况下,第一个就是,时间复杂度为O(1),
    最坏的情况是,缓存的数据在最后一个被找到,或者要缓存的数据没有存在链表中
    需要遍历完整个链表,所以时间复杂度是O(n),n是链表的长度。能否再降低时间复
    复杂度,答案是引入哈希表。下一次,将会手写哈希表,降低LRU的时间复杂度
    哈希表结合双向链表实现

    展开全文
  • LRU 缓存淘汰算法

    2020-10-18 15:20:07
    如何实现 LRU 缓存机制 1. 参考链接: 如何实现 LRU 缓存机制 https://mp.weixin.qq.com/s?__biz=MzAxODQxMDM0Mw==&mid=2247484500&idx=1&sn=83f4df1253f597898b2f74ea9dca9fd9&chksm=9bd7fa5caca...

    如何实现 LRU 缓存机制

    1. 场景与原理

    场景
    设计一种缓存,要求总是能够快速访问最新的数据,并且查找与删除时间和空间复杂度都是尽可能低;

    方法:哈希表 + 双向链表。
    时间复杂度:对于 put 和 get 都是 O(1)。
    空间复杂度:O(capacity),因为哈希表和双向链表最多存储 capacity+1 个元素。

    为什么要有LRU?

    • 在计算机存储层次结构中,低一层的存储器都可以看做是高一层的缓存。比如Cache是内存的缓存,内存是硬盘的缓存,硬盘是网络的缓存等等。
    • 缓存可以有效地解决存储器性能与容量的这对矛盾,但绝非看上去那么简单。如果缓存算法设计不当,非但不能提高访问速度,反而会使系统变得更慢。
    • 从本质上来说,缓存之所以有效是因为程序和数据的局部性(locality)。程序会按固定的顺序执行,数据会存放在连续的内存空间并反复读写。这些特点使得我们可以缓存那些经常用到的数据,从而提高读写速度。
    • 缓存的大小是固定的,它应该只保存最常被访问的那些数据。然而未来不可预知,我们只能从过去的访问序列做预测,于是就有了各种各样的缓存替换策略。本文介绍一种简单的缓存策略,称为最近最少使用(LRU,Least Recently Used)算法。

    总结来说:计算机读取文件(数据库)的速度相对于读取内存的数据来说,效率要低得多,因此常用缓存来提高访问效率,而内存相比较于硬盘要小的多,为了缓存更有价值的数据,淘汰算法就显得尤为重要。

    如何实现 LRU 缓存机制

    https://mp.weixin.qq.com/s?__biz=MzAxODQxMDM0Mw==&mid=2247484500&idx=1&sn=83f4df1253f597898b2f74ea9dca9fd9&chksm=9bd7fa5caca0734ad182ba67651882647a71264938eaa98e49c5ff43369b807a094ad16efcd4&scene=21#wechat_redirect

    详细代码实现:

    https://github.com/labuladong/yueduyuanwen/blob/master/LRUcache/lru-cache.java

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

    实现思路

    1. 新数据插入到链表头部;
    2. 每当缓存命中(即缓存数据被访问),则将数据移到链表头部;
    3. 当链表满的时候,将链表尾部的数据丢弃。

    提示:Java里面实现LRU缓存通常有两种选择,一种是使用LinkedHashMap,一种是自己设计数据结构,使用链表+HashMap;
    (其中LinkedHashMap改造查看链接:https://www.cnblogs.com/lzrabbit/p/3734850.html)

    如下是缓存淘汰过程示意图:
    在这里插入图片描述

    2. LRU机制的实现过程

    class Node {
        public int key, val;
        public Node next, prev;
        public Node(int k, int v) {
            this.key = k;
            this.val = v;
        }
    }
    
    class DoubleList {  
        // 头尾虚节点
        private Node head, tail;  
        // 链表元素数
        private int size;
        
        public DoubleList() {
            // 初始化双向链表的数据
            head = new Node(0, 0);
            tail = new Node(0, 0);
            head.next = tail;
            tail.prev = head;
            size = 0;
        }
        
        public void addFirst(Node x) {
            x.next = head.next;
            x.prev = head;
            head.next.prev = x;
            head.next = x;
            size++;
        }
        
        public void remove(Node x) {
            x.prev.next = x.next;
            x.next.prev = x.prev;
            size--;
        }
        
        public Node removeLast() {
            if (tail.prev == head)
                return null;
            Node last = tail.prev;
            remove(last);
            return last;
        }
        
        public int size() { return size; }
    }
    
    class LRUCache {
    
        private int cap;
        private HashMap<Integer, Node> map;
        private DoubleList cache;
        
        public LRUCache(int capacity) {
            // 初始化 LRU cache 的数据
            this.cap = capacity;
            map = new HashMap<>();
            cache = new DoubleList();
        }
        
        public int get(int key) {
            if (!map.containsKey(key))
                return -1;
            int val = map.get(key).val;
            put(key, val);
            return val;
        }
        
        public void put(int key, int val) {
            // 先把新节点 x 做出来
            Node x = new Node(key, val);
            
            if (map.containsKey(key)) {
                // 删除旧的,新的插到头部
                cache.remove(map.get(key));
                cache.addFirst(x);
                // 更新 map 中对应的数据
                map.put(key, x);
            } else {
                if (cap == cache.size()) {
                    // 删除链表最后一个
                    Node last = cache.removeLast();
                    map.remove(last.key);
                }
                // 直接添加到头部即可
                cache.addFirst(x);
                map.put(key, x);
            }
        }
    }
    
    /**
     * Your LRUCache object will be instantiated and called as such:
     * LRUCache obj = new LRUCache(capacity);
     * int param_1 = obj.get(key);
     * obj.put(key,value);
     */
    

    3.调用该LRU缓存的过程

    /**
     * Your LRUCache object will be instantiated and called as such:
     * LRUCache obj = new LRUCache(capacity);
     * int param_1 = obj.get(key);
     * obj.put(key,value);
     */
    public class LRUTestMain {
        public static void main(String[] args) {
            final LRUCache lruCache = new LRUCache(2);
            lruCache.put(1, 11);
            lruCache.put(2, 22);
            lruCache.put(3, 33);
            //容量为2,当插入3时候,1的结果被淘汰;因此此处返回结果为-1;
            System.out.println(lruCache.get(1));
            System.out.println(lruCache.get(2));
            System.out.println(lruCache.get(3));
        }
    }
    

    该算法的时间复杂度是O(1),空间复杂度是O(1)

    优缺点:

    【命中率】
    当存在热点数据时,LRU的效率很好,但偶发性的、周期性的批量操作会导致LRU命中率急剧下降,缓存污染情况比较严重。
    【复杂度】
    实现简单。
    【代价】
    命中时需要遍历链表,找到命中的数据块索引,然后需要将数据移到头部。

    改进:
    针对缓存污染问题,后期有对应的对LRU的改进:
    https://www.cnblogs.com/Dhouse/p/8615481.html

    • LRU-K
    • Two queues(2Q)
    • Multi Queue(MQ)
    展开全文
  • 手写LRU缓存淘汰算法

    2021-03-01 21:58:29
    手写LRU缓存淘汰算法 背景 在我们这个日益追求高效的世界,我们对任何事情的等待都显得十分的浮躁,网页页面刷新不出来,好烦,电脑打开运行程序慢,又是好烦!那怎么办,技术的产生不就是我们所服务么,今天我们就...

    手写LRU缓存淘汰算法

    背景

    在我们这个日益追求高效的世界,我们对任何事情的等待都显得十分的浮躁,网页页面刷新不出来,好烦,电脑打开运行程序慢,又是好烦!那怎么办,技术的产生不就是我们所服务么,今天我们就聊一聊缓存这个技术,并使用我们熟知的数据结构--用链表实现LRU缓存淘汰算法

    在学习如何使用链表实现LRU缓存淘汰算法前,我们先提出几个问题,大家好好思考下,问题如下:

    • 什么是缓存,缓存的作用?
    • 缓存的淘汰策略有哪些?
    • 如何使用链表实现LRU缓存淘汰算法,有什么特点,如何优化?

    好了,我们带着上面的问题来学进行下面的学习。

    1、什么是缓存,缓存的作用是什么?

    缓存可以简单的理解为保存数据的一个副本,以便于后续能够快速的进行访问。以计算机的使用场景为例,当cpu要访问内存中的一条数据时,它会先在缓存里查找,如果能够找到则直接使用,如果没找到,则需要去内存里查找;

    同样的,在数据库的访问场景中,当项目系统需要查询数据库中的某条数据时,可以先让请求查询缓存,如果命中,就直接返回缓存的结果,如果没有命中,就查询数据库, 并将查询结果放入缓存,下次请求时查询缓存命中,直接返回结果,就不用再次查询数据库。

    通过以上两个例子,我们发现无论在哪种场景下,都存在这样一个顺序:先缓存,后内存先缓存,后数据库。但是缓存的存在也占用了一部分内存空间,所以缓存是典型的以空间换时间,牺牲数据的实时性,却满足计算机运行的高效性

    仔细想一下,我们日常开发中遇到缓存的例子还挺多的。

    • 操作系统的缓存

    减少与磁盘的交互

    • 数据库缓存

    减少对数据库的查询

    • Web服务器缓存

    减少对应用服务器的请求

    • 客户浏览器的缓存

    减少对网站的访问

    2、缓存有哪些淘汰策略?

    缓存的本质是以空间换时间,那么缓存的容量大小肯定是有限的,当缓存被占满时,缓存中的那些数据应该被清理出去,那些数据应该被保留呢?这就需要缓存的淘汰策略来决定。

    事实上,常用的缓存的淘汰策略有三种:先进先出算法(First in First out FIFO);淘汰一定时期内被访问次数最少的页面(Least Frequently Used LFU);淘汰最长时间未被使用的页面(Least Recently Used LRU)

    这些算法在不同层次的缓存上执行时具有不同的效率,需要结合具体的场景来选择。

    2.1 FIFO算法

    FIFO算法即先进先出算法,常采用队列实现。在缓存中,它的设计原则是:如果一个数据最先进入缓存中,则应该最早淘汰掉

    image-20210227115124480

    • 新访问的数据插入FIFO队列的尾部,队列中数据由队到队头按顺序顺序移动
    • 队列满时,删除队头的数据

    2.2 LRU算法

    LRU算法是根据对数据的历史访问次数来进行淘汰数据的,通常使用链表来实现。在缓存中,它的设计原则是:如果数据最近被访问过,那么将来它被访问的几率也很高。

    image-20210227120433527

    • 新加入的数据插入到链表的头部
    • 每当缓存命中时(即缓存数据被访问),则将数据移到链表头部
    • 当来链表已满的时候,将链表尾部的数据丢弃

    2.3 LFU算法

    LFU算法是根据数据的历史访问频率来淘汰数据,因此,LFU算法中的每个数据块都有一个引用计数,所有数据块按照引用计数排序,具有相同引用计数的数据块则按照时间排序。在缓存中,它的设计原则是:如果数据被访问多次,那么将来它的访问频率也会更高

    image-20210227121952816

    • 新加入数据插入到队列尾部(引用计数为1;
    • 队列中的数据被访问后,引用计数增加,队列重新排序;
    • 当需要淘汰数据时,将已经排序的列表最后的数据块删除。

    3、如何使用链表实现缓存淘汰,有什么特点,如何优化?

    在上面的文章中我们理解了缓存的概念淘汰策略,其中LRU算法是笔试/面试中考察比较频繁的,我秋招的时候,很多公司都让我手写了这个算法,为了避免大家采坑,下面,我们就手写一个LRU缓存淘汰算法。

    我们都知道链表的形式不止一种,我们应该选择哪一种呢?

    思考三分钟........

    好了,公布答案!

    事实上,链表按照不同的连接结构可以划分为单链表循环链表双向链表

    • 单链表
    • 每个节点只包含一个指针,即后继指针。
    • 单链表有两个特殊的节点,即首节点和尾节点,用首节点地址表示整条链表,尾节点的后继指针指向空地址null。
    • 性能特点:插入和删除节点的时间复杂度为O(1),查找的时间复杂度为O(n)。
    • 循环链表
    • 除了尾节点的后继指针指向首节点的地址外均与单链表一致。
    • 适用于存储有循环特点的数据,比如约瑟夫问题。
    • 双向链表
    • 节点除了存储数据外,还有两个指针分别指向前一个节点地址(前驱指针prev)和下一个节点地址(后继指针next)

    • 首节点的前驱指针prev和尾节点的后继指针均指向空地址。

    双向链表相较于单链表的一大优势在于:找到前驱节点的时间复杂度为O(1),而单链表只能从头节点慢慢往下找,所以仍然是O(n).而且,对于插入和删除也是有优化的。

    我们可能会有问题:单链表的插入删除不是O(1)吗?

    是的,但是一般情况下,我们想要进行插入删除操作,很多时候还是得先进行查找,再插入或者删除,可见其实是先O(n),再O(1)。

    不熟悉链表解题的同学可以先看看我的上一篇算法解析文章刷了LeetCode链表专题,我发现了一个秘密

    因为我们需要删除操作,删除一个节点不仅要得到该节点本身的指针,也需要操作其它前驱节点的指针,而双向链表能够直接找到前驱,保证了操作时间复杂度为O(1),因此使用双向链表作为实现LRU缓存淘汰算法的结构会更高效。

    算法思路

    维护一个双向链表,保存所有缓存的值,并且最老的值放在链表最后面。

    • 当访问的值在链表中时: 将找到链表中值将其删除,并重新在链表头添加该值(保证链表中 数值的顺序是从新到旧)
    • 当访问的值不在链表中时: 当链表已满:删除链表最后一个值,将要添加的值放在链表头 当链表未满:直接在链表头添加

    3.1 LRU缓存淘汰算法

    极客时间王争的《数据结构与算法之美》给出了一个使用有序单链表实现LRU缓存淘汰算法,代码如下:

    public class LRUBaseLinkedList<T> {
    
        /**
         * 默认链表容量
         */
        private final static Integer DEFAULT_CAPACITY = 10;
    
        /**
         * 头结点
         */
        private SNode<T> headNode;
    
        /**
         * 链表长度
         */
        private Integer length;
    
        /**
         * 链表容量
         */
        private Integer capacity;
    
        public LRUBaseLinkedList() {
            this.headNode = new SNode<>();
            this.capacity = DEFAULT_CAPACITY;
            this.length = 0;
        }
    
        public LRUBaseLinkedList(Integer capacity) {
            this.headNode = new SNode<>();
            this.capacity = capacity;
            this.length = 0;
        }
    
        public void add(T data) {
            SNode preNode = findPreNode(data);
    
            // 链表中存在,删除原数据,再插入到链表的头部
            if (preNode != null) {
                deleteElemOptim(preNode);
                intsertElemAtBegin(data);
            } else {
                if (length >= this.capacity) {
                    //删除尾结点
                    deleteElemAtEnd();
                }
                intsertElemAtBegin(data);
            }
        }
    
        /**
         * 删除preNode结点下一个元素
         *
         * @param preNode
         */
        private void deleteElemOptim(SNode preNode) {
            SNode temp = preNode.getNext();
            preNode.setNext(temp.getNext());
            temp = null;
            length--;
        }
    
        /**
         * 链表头部插入节点
         *
         * @param data
         */
        private void intsertElemAtBegin(T data) {
            SNode next = headNode.getNext();
            headNode.setNext(new SNode(data, next));
            length++;
        }
    
        /**
         * 获取查找到元素的前一个结点
         *
         * @param data
         * @return
         */
        private SNode findPreNode(T data) {
            SNode node = headNode;
            while (node.getNext() != null) {
                if (data.equals(node.getNext().getElement())) {
                    return node;
                }
                node = node.getNext();
            }
            return null;
        }
    
        /**
         * 删除尾结点
         */
        private void deleteElemAtEnd() {
            SNode ptr = headNode;
            // 空链表直接返回
            if (ptr.getNext() == null) {
                return;
            }
    
            // 倒数第二个结点
            while (ptr.getNext().getNext() != null) {
                ptr = ptr.getNext();
            }
    
            SNode tmp = ptr.getNext();
            ptr.setNext(null);
            tmp = null;
            length--;
        }
    
        private void printAll() {
            SNode node = headNode.getNext();
            while (node != null) {
                System.out.print(node.getElement() + ",");
                node = node.getNext();
            }
            System.out.println();
        }
    
        public class SNode<T> {
    
            private T element;
    
            private SNode next;
    
            public SNode(T element) {
                this.element = element;
            }
    
            public SNode(T element, SNode next) {
                this.element = element;
                this.next = next;
            }
    
            public SNode() {
                this.next = null;
            }
    
            public T getElement() {
                return element;
            }
    
            public void setElement(T element) {
                this.element = element;
            }
    
            public SNode getNext() {
                return next;
            }
    
            public void setNext(SNode next) {
                this.next = next;
            }
        }
    
        public static void main(String[] args) {
            LRUBaseLinkedList list = new LRUBaseLinkedList();
            Scanner sc = new Scanner(System.in);
            while (true) {
                list.add(sc.nextInt());
                list.printAll();
            }
        }
    }

    这段代码不管缓存有没有满,都需要遍历一遍链表,所以这种基于链表的实现思路,缓存访问的时间复杂度为 O(n)。

    3.2使用哈希表优化LRU

    事实上,这个思路还可以继续优化,我们可以把单链表换成双向链表,并引入散列表

    • 双向链表支持查找前驱,保证操作的时间复杂度为O(1)
    • 引入散列表记录每个数据的位置,将缓存访问的时间复杂度降到O(1)

    哈希表查找较快,但是数据无固定的顺序;链表倒是有顺序之分。插入、删除较快,但是查找较慢。将它们结合,就可以形成一种新的数据结构--哈希链表(LinkedHashMap)

    image-20210227203448255

    力扣上146题-LRU缓存机制刚好可以拿来练手,题图如下:

    题目:

    运用你所掌握的数据结构,设计和实现一个 LRU (最近最少使用) 缓存机制 。

    • 实现 LRUCache 类:

    LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存 int get(int key) 如果关键字 key 存在于缓存中,则返回关键字的值,否则返回 -1 。 void put(int key, int value) 如果关键字已经存在,则变更其数据值;如果关键字不存在,则插入该组「关键字-值」。当缓存容量达到上限时,它应该在写入新数据之前删除最久未使用的数据值,从而为新的数据值留出空间。

    思路:

    我们的思路就是哈希表+双向链表

    • 哈希表用于满足题目时间复杂度O(1)的要求,双向链表用于存储顺序
    • 哈希表键值类型:<Integer, ListNode>,哈希表的键用于存储输入的key,哈希表的值用于存储双向链表的节点
    • 双向链表的节点中除了value外还需要包含key,因为在删除最久未使用的数据时,需要通过链表来定位hashmap中应当删除的键值对
    • 一些操作:双向链表中,在后面的节点表示被最近访问
    • 新加入的节点放在链表末尾,addNodeToLast(node)
    • 若容量达到上限,去除最久未使用的数据,removeNode(head.next)
    • 若数据新被访问过,比如被get了或被put了新值,把该节点挪到链表末尾,moveNodeToLast(node)
    • 为了操作的方便,在双向链表头和尾分别定义一个head和tail节点。

    代码

    class LRUCache {
        private int capacity;
        private HashMap<Integer, ListNode> hashmap; 
        private ListNode head;
        private ListNode tail;
    
        private class ListNode{
            int key;
            int val;
            ListNode prev;
            ListNode next;
            public ListNode(){  
            }
            public ListNode(int key, int val){
                this.key = key;
                this.val = val;
            }
        }
    
        public LRUCache(int capacity) {
            this.capacity = capacity;
            hashmap = new HashMap<>();
            head = new ListNode();
            tail = new ListNode();
            head.next = tail;
            tail.prev = head;
        }
    
        private void removeNode(ListNode node){
            node.prev.next = node.next;
            node.next.prev = node.prev;
        }
    
        private void addNodeToLast(ListNode node){
            node.prev = tail.prev;
            node.prev.next = node;
            node.next = tail;
            tail.prev= node;
        }
    
        private void moveNodeToLast(ListNode node){
            removeNode(node);
            addNodeToLast(node);
        }
    
        public int get(int key) {   
            if(hashmap.containsKey(key)){
                ListNode node = hashmap.get(key);
                moveNodeToLast(node);
                return node.val;
            }else{
                return -1;
            }
        }
    
        public void put(int key, int value) {
            if(hashmap.containsKey(key)){
                ListNode node = hashmap.get(key);
                node.val = value;
                moveNodeToLast(node);
                return;
            }
            if(hashmap.size() == capacity){
                hashmap.remove(head.next.key);
                removeNode(head.next);
            }
    
            ListNode node = new ListNode(key, value);
            hashmap.put(key, node);
            addNodeToLast(node);
        }
    }
    

    巨人的肩膀

    [1]数据结构与算法之美-王争

    [2]力扣-LRU缓存机制(146题)

    [3]https://blog.csdn.net/yangpl_tale/article/details/44998423

    [4]https://leetcode-cn.com/problems/lru-cache/solution/146-lru-huan-cun-ji-zhi-ha-xi-biao-shuan-l3um/

    本文由博客群发一文多发等运营工具平台 OpenWrite 发布

    展开全文
  • 主要介绍了golang实现LRU缓存淘汰算法的示例代码,小编觉得挺不错的,现在分享给大家,也给大家做个参考。一起跟随小编过来看看吧
  • LRU缓存淘汰算法,也就是最近最少使用缓存淘汰策略实现的算法。这里我们使用散列表和链表实现提高操作的时间复杂中度,达到O(1)

    LRU缓存淘汰算法,也就是最近最少使用缓存淘汰策略实现的算法。

    借助于链表,我们可以这样做:

    我们可以维护一个按照访问时间从大到小有序排列的链表。当然在这算法中这个链表有长度限制,以便于当链表容量达到时执行淘汰策略。

    无论是①在缓存中保存数据  ②从缓存中删除一个数据  ③在缓存中查到一个数据,这三种都要先进行缓存中数据的查找操作,即

    添加时:我们先要在缓存中查找这个数据是否存在。如果没有找到则直接将数据放到链表头部,如果找到的话,将这个数据移动到链表头部。

    删除时:我们先要在缓存中查找这个数据是否存在。如果找到则删除这个数据。

    查找时:我们先要在缓存中查找这个数据是否存在。如果找到则返回这个数据。

    所以,如果单纯使用链表去实现LRU缓存淘汰算法,时间复杂度是O(n).

    为了提高时间复杂度,我们可以借助于散列表,散列表查找数据时间复杂度O(1),这里使用散列表加双向链表来实现LRU缓存淘汰算法。

    添加时:我们首先根据key在散列表中找到要删除的节点,时间复杂度O(1)。找到后将这个数据移动到链表头部。找不到则添加到链表头部,如果链表满的话还要删除链表的尾结点。

    删除时:我们在时间复杂度O(1)内找到这个数据然后执行删除。

    查找时:直接根据key在时间复杂度为O(1)内就可以找到了。

     

    代码:

    package com.study.algorithm.hashtable;
    
    import java.util.HashMap;
    
    /**
     * @Auther: JeffSheng
     * @Date: 2019/8/30 11:23
     * @Description:
     * 基于散列表+双向链表 实现LRU算法
     *
     */
    public class LruBaseHashTable<K,V> {
    
        /**
         * 默认链表容量
         */
        private final static Integer DEFAULT_CAPACITY = 10;
    
    
        /**
         * 头结点
         */
        private DoubleNode<K,V> headNode;
    
    
        /**
         * 尾结点
         */
        private DoubleNode<K,V> tailNode;
    
        /**
        * 链表长度
        */
        private Integer length;
    
        /**
         * 链表容量
         */
        private Integer capacity;
    
    
        /**
         * 散列表存储key以及对应链表
         */
        private HashMap<K,DoubleNode<K,V>> table;
    
    
        static class DoubleNode<K,V>{
            private K key;
    
            private V value;
    
            private DoubleNode<K,V> prev;
    
            private DoubleNode<K,V> next;
    
            DoubleNode(){}
    
            DoubleNode(K key,V value){
                this.key=key;
                this.value=value;
            }
    
        }
    
        /**
         * 初始化散列表
         * @param capacity
         */
        public LruBaseHashTable(int capacity) {
            this.length = 0;
            this.capacity = capacity;
            headNode = new DoubleNode<>();
            tailNode = new DoubleNode<>();
    
            headNode.next = tailNode;
            tailNode.prev = headNode;
    
            table = new HashMap<>();
        }
    
        public LruBaseHashTable() {
            this(DEFAULT_CAPACITY);
        }
    
    
        /**
         * 新增节点
         * @param key
         * @param value
         */
        public void add(K key,V value){
            DoubleNode<K,V> node = table.get(key);
            if(node==null){
                DoubleNode<K,V> newNode=new DoubleNode<>(key,value);
                table.put(key,newNode);
                //将新结点插入到链表头部
                addNodeToHead(newNode);
    
                //如果链表容量已超
                if(++length >capacity){
                    //从散列表删除尾结点元素
                    DoubleNode<K,V> tail = popTail();
                    table.remove(tail.key);
                    length--;
                }
    
            }else{
                //添加的节点存在,则覆盖此节点值
                node.value = value;
                //然后将存在的节点移动到链表头部
                moveToHead(node);
            }
    
        }
    
    
        /**
         * 将节点移动到头部
         *
         * @param node
         */
        private void moveToHead(DoubleNode<K, V> node) {
            removeNode(node);
            addNodeToHead(node);
        }
    
    
    
        /**
         * 弹出尾部数据节点
         */
        private DoubleNode<K, V> popTail() {
            DoubleNode<K, V> node = tailNode.prev;
            removeNode(node);
            return node;
        }
    
        /**
         * 移除节点
         *
         * @param node
         */
        private void removeNode(DoubleNode<K, V> node) {
            node.prev.next = node.next;
            node.next.prev = node.prev;
        }
    
    
        /**
         * 将新节点添加到链表头部
         * @param newNode
         */
        public void addNodeToHead(DoubleNode<K,V> newNode){
    
            newNode.next = headNode.next;
            newNode.prev=headNode;
    
            headNode.next.prev=newNode;
            headNode.next = newNode;
        }
    
    
        /**
         * 从散列表获取节点值
         * @param key
         * @return
         */
        public V get(K key){
            DoubleNode<K,V> node = table.get(key);
            if (node == null) {
                return null;
            }
            //节点存在移动到头部
            moveToHead(node);
            return node.value;
        }
    
        /**
         * 从散列移除节点数据
         *
         * @param key
         */
        public void remove(K key) {
            DoubleNode<K, V> node = table.get(key);
            if (node == null) {
                return;
            }
            //节点存在则移除此节点
            removeNode(node);
            length--;
        }
    
        private void printAll() {
            DoubleNode<K, V> node = headNode.next;
            while (node.next != null) {
                System.out.print(node.value + ",");
                node = node.next;
            }
            System.out.println();
        }
    
    }
    

     

     

     

     

    展开全文
  • 链表(上):如何实现LRU缓存淘汰算法
  • 06|链表上如何实现LRU缓存淘汰算法? 06|链表上如何实现LRU缓存淘汰算法? Linked list LRU 今天我们来聊聊 链表 这个数据结构学习链表有什么用呢为了回答这个问题我们先来讨论一个经典的链表应用场景那就是 缓存淘汰...
  • 链表:如何实现LRU缓存淘汰算法 一个经典的链表应用场景,就是LRU缓存淘汰算法 缓存是一种提高数据读取性能的技术,比如CPU缓存、数据库缓存、浏览器缓存等等 缓存的大小有限,当缓存被用满的时候哪些数据该被清理...
  • LRU缓存淘汰算法优化

    千次阅读 2019-05-18 15:06:52
    上文中提到了LRU 缓存淘汰算法,可以帮助我们更好更合理的去使用缓存。但是它也有一个缺点就是如果有一些不满足“如果数据最近被访问过,那么将来被访问的几率也更高”的规律时,会破坏缓存,导致性能下降。如果缓存...
  • 工工程程师师必必须须了了解解的的LRU缓缓存存淘淘汰汰算算法法以以及及python实实现现过过程程 这篇文章主要介绍了工程师必须了解的LRU缓存淘汰算法以及python实现过程帮助大家更好的学习算法数据结 构感兴 的朋友...
  • golang--算法--LRU 缓存淘汰算法

    千次阅读 2020-02-29 09:54:03
    说到链表一个经典的应用场景,那就是 LRU 缓存淘汰算法。 缓存是一种提高数据读取性能的技术,在硬件设计、软件开发中都有着非常广泛的应用,比如常见的 CPU 缓存、数据库缓存、浏览器缓存等等。缓存的大小有限,当...
  • 记录一下LRU缓存淘汰算法的实现。 原理 LRU(Least recently used,最近最少使用)缓存算法根据数据最近被访问的情况来进行淘汰数据,其核心思想是“如果数据最近被访问过,那么将来被访问的几率也更高”。 ...
  • 常用的机制里面包括 LRU 缓存淘汰算法。 二、设计原则 全称:LeastRecently Used 如果一个数据在最近一段时间没有被访问到,那么在将来它被访问的可能性也很小。所以淘汰的数据应该是许久没有访问到的数据。 三...
  • 链表实现的LRU缓存淘汰算法的时间复杂度是O(n),当时我也提到了,通过散列表可以将这个时间复杂度降低到O(1)。 Redis的有序集合是使用跳表来实现的,跳表可以看作一种改进版的链表。Redis有序集合不仅使用了跳表,还...
  • 缓存:是一种提高数据读取性能的技术,在硬件设计、软件开发中都有着非常...LRU缓存淘汰算法:我们维护一个有序单链表,越靠近链表尾部的结点是越早之前访问的。当有一个新的数据被访问时,我们从链表头开始顺序遍历...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 17,902
精华内容 7,160
关键字:

lru缓存淘汰算法