LRU算法

简介: LRU是Least Recently Used的缩写,意思就是最近最少使用,常用于页面置换的一种算法。LRU算法的提出,是基于这样一个场景:在前面几条指令中使用频繁的页面很可能在后面的几条指令中频繁使用。反过来说,已经很久没有使用的页面很可能在未来较长的一段时间内不会被用到。这个,就是著名的局部性原理。此外,LRU算法也经常被用作缓存淘汰策略。本文将基于LRU算法的思想,使用Java语言实现一个我们自己的缓存工具类

什么是LRU算法

     LRU是Least Recently Used的缩写,意思就是最近最少使用,常用于页面置换的一种算法。LRU算法的提出,是基于这样一个场景:在前面几条指令中使用频繁的页面很可能在后面的几条指令中频繁使用。反过来说,已经很久没有使用的页面很可能在未来较长的一段时间内不会被用到。这个,就是著名的局部性原理。此外,LRU算法也经常被用作缓存淘汰策略。本文将基于LRU算法的思想,使用Java语言实现一个我们自己的缓存工具类

背景

     当我们想要实现一个搜索框搜索内容(想要把最近n小时搜索的内容显示出来方便我们直接选中),这里声明一下不是最多最近。那我们使用LRU算法的机制实现缓存淘汰策略就再好不过了

算法思想

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

数据结构

JAVA实现缓存淘汰demo


importjava.util.HashMap;
importjava.util.Map;
publicclassLRUCache {
// 双向链表节点定义classNode {
intkey;
intval;
Nodeprev;
Nodenext;
    }
//模拟缓存容量privateintcapacity;
//保存链表的头节点和尾节点privateNodefirst;
privateNodelast;
//从key到node映射的mapprivateMap<Integer, Node>map;
publicLRUCache(intcapacity) {
this.capacity=capacity;
map=newHashMap<>(capacity);
    }
publicintget(intkey) {
Nodenode=map.get(key);
//为空返回-1if (node==null) {
return-1;
        }
moveToHead(node);
returnnode.val;
    }
publicvoidput(intkey, intvalue) {
//先看看是否已经存在Nodenode=map.get(key);
if (node==null) {
//不存在创建节点,然后判断缓存是否满了,如果满了删除最后一个节点。然后将新节点放到链表头部,增加一个映射关系//存在则直接覆盖,然后移动到头部node=newNode();
node.key=key;
node.val=value;
if(map.size() ==capacity) {
removeLast();
            }
addToHead(node);
map.put(key, node);
        } else {
node.val=value;
moveToHead(node);
        }
    }
privatevoidmoveToHead(Nodenode) {
//要修改很多指针if (node==first) {
return;
        } elseif (node==last) {
//如果是最后一个节点,将最后一个节点的next指针置为空,然后last指向前一个节点last.prev.next=null;
last=last.prev;
        } else {
//如果是中间节点,中间节点的前节点的后指针  指向 中间节点的后节点//中间节点的后节点的前指针 指向 中间节点的前节点node.prev.next=node.next;
node.next.prev=node.prev;
        }
//把该节点作为头结点node.prev=first.prev;// 写成node.prev = null;更好理解node.next=first;
first.prev=node;
first=node;
    }
privatevoidaddToHead(Nodenode) {
if (map.isEmpty()) {
first=node;
last=node;
        } else {
//把新节点作为头结点node.next=first;
first.prev=node;
first=node;
        }
    }
privatevoidremoveLast() {
map.remove(last.key);
NodeprevNode=last.prev;
//修改last所指的位置if (prevNode!=null) {
prevNode.next=null;
last=prevNode;
        }
    }
@OverridepublicStringtoString() {
returnmap.keySet().toString();
    }
publicstaticvoidmain(String[] args) {
LRUCachecache=newLRUCache(3);
cache.put(1, 1);//【1】左边是最近使用的cache.put(2, 2);//【2,1】cache.put(3, 3);//【3,2,1】cache.get(1);//【1,3,2】cache.put(4, 3);//【4,1,3】System.out.println(cache);
    }
}


相关文章
|
6月前
|
存储 缓存 算法
LRU(Least Recently Used)算法原理
LRU(Least Recently Used)算法原理
86 0
|
缓存 算法
LRU算法详解
LRU算法详解
266 0
|
存储 NoSQL 算法
【LRU】一文让你弄清 Redis LRU 页面置换算法
【LRU】一文让你弄清 Redis LRU 页面置换算法
142 0
|
NoSQL 算法 Redis
其实吧,LRU也就那么回事。 (下)
其实吧,LRU也就那么回事。 (下)
140 0
其实吧,LRU也就那么回事。 (下)
|
存储 SQL NoSQL
其实吧,LRU也就那么回事。 (中)
其实吧,LRU也就那么回事。 (中)
144 0
其实吧,LRU也就那么回事。 (中)
|
存储 缓存 算法
其实吧,LRU也就那么回事。 (上)
其实吧,LRU也就那么回事。 (上)
129 0
其实吧,LRU也就那么回事。 (上)
|
存储 缓存 算法
最近最少使用(LRU)缓存淘汰算法
最近最少使用(LRU)缓存淘汰算法
最近最少使用(LRU)缓存淘汰算法
|
缓存 算法 Java
LRU算法
LRU是Least Recently Used的缩写,意思就是最近最少使用,常用于页面置换的一种算法。LRU算法的提出,是基于这样一个场景:在前面几条指令中使用频繁的页面很可能在后面的几条指令中频繁使用。反过来说,已经很久没有使用的页面很可能在未来较长的一段时间内不会被用到。这个,就是著名的局部性原理。此外,LRU算法也经常被用作缓存淘汰策略。本文将基于LRU算法的思想,使用Java语言实现一个我们自己的缓存工具类
|
缓存 算法
常用缓存淘汰算法(LFU、LRU、ARC、FIFO、MRU)
缓存算法是指令的一个明细表,用于决定缓存系统中哪些数据应该被删去。 常见类型包括LFU、LRU、ARC、FIFO、MRU。
584 0
常用缓存淘汰算法(LFU、LRU、ARC、FIFO、MRU)
|
存储 缓存 NoSQL
LRU(Least Recently Used)
Redis是基于内存存储的key-value数据库,我们知道内存虽然快但空间小,当物理内存达到上限时,系统就会跑的很慢,这是因为swap机制会将部分内存的数据转移到swap分区中,通过与swap的交换保证系统继续运行;但是swap属于硬盘存储,速度远远比不上内存,尤其是对于Redis这种QPS非常高的服务,发生这种情况是无法接收的。(注意如果swap分区内存也满了,系统就会发生错误!)
359 0
LRU(Least Recently Used)