什么是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; } } publicStringtoString() { 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); } }
