算法:使用双向链表实现LRU算法
题目:
LRU是最近最少使用的淘汰算法,当执行set(),get()方法的时候,把节点加到LRU链表的最前方。当超过容量的时候,淘汰最近最少使用的数据。
分析
- 使用双向链表来存储顺序,从题目中可以看出,双向链表的头节点和尾节点,也会发生响应的操作,只要是头节点会发生改变的,统一使用一个哨兵节点。尾节点也会发生改变,尾节点也设置一个哨兵节点。
- 使用map数据结构去实现查询时间复杂度是O(1);
- 操作分为get() : 需要把节点从原链表删除,然后再添加到头节点位置
- set():第一种情况key存在,只需要修改值,然后把节点从原链表中删除,再添加到新链表中。 另外一种情况:key不存在,添加到头节点,然后判断缓存容量,大于容量的时候,要执行淘汰链表的最后一个节点
- 淘汰:删除链表的最后一个节点
package mianshi.LRU;
import java.util.HashMap;
import java.util.Map;
/**
* @program: Math
* @description: 实现一个LRU,淘汰最近最少使用数据,在get,set中LRU移到前面
**/
public class LRUCache {
/** 双向链表的头节点,头节点作为哨兵节点 **/
private ListNode head;
/** 双向链表的尾节点,尾节点作为哨兵节点 **/
private ListNode tail;
/** 为了保证查询的效率 **/
private Map<String, ListNode> cache;
/** 缓存容量 **/
private int capacity;
/** 初始化,这个初始化非常重要,我们在初始化双向链表的时候,头节点和尾节点都设置为null.
* 切记,只要是移动位置的,操作头尾节点的,都要在前面设置一个哨兵节点 **/
public LRUCache(int capacity){
this.capacity = capacity;
cache = new HashMap<>();
head = new ListNode(null, null);
tail = new ListNode(null, null);
/** 构造双向链表 **/
head.next = tail;
tail.pre = head;
}
/**
* 如果map中不存在返回null
* map中存在,则把该接节点移动到头部
* @param key
* @return
*/
public String get(String key){
ListNode listNode = cache.get(key);
if(listNode == null){return null;}
String val = listNode.val;
moveToHead(listNode);
return val;
}
/**
* 判断map中是否包含这个key
* 包含:替换原来的值,把当前节点在链表中删除,把该节点移动到头部
* 不包含:创建一个新的Node,把Node放到头部,在需要判断map的容量,如果不够实用,就把尾节点删除
* @param key
* @param val
*/
public void set(String key, String val){
if(cache.containsKey(key)){
ListNode listNode = cache.get(key);
listNode.val = val;
moveToHead(listNode);
} else {
/** 在链表中放一个值 **/
ListNode newNode = new ListNode(key, val);
/** 把该节点放到双向链表的头部节点 **/
addNewNode(newNode);
cache.put(key, newNode);
if(cache.size() > capacity){
popLast();
}
}
}
/** 添加一个新节点 **/
private void addNewNode(ListNode newNode) {
newNode.next = head.next;
head.next.pre = newNode;
newNode.pre = head;
head.next = newNode;
}
/** 淘汰不常用的节点 **/
private void popLast() {
tail.pre = tail.pre.pre;
tail.pre.next = tail;
}
private void moveToHead(ListNode newNode) {
/** 移动这个双向链表中的一个节点,需要做两件事情 **/
/** 1.把当前节点从原有链表中删除 **/
/** 2.把这个节点移动到头节点的位置 **/
/** 如果只是移动,会导致当前节点所在位置的前后节点不连续 **/
newNode.next.pre = newNode.pre;
newNode.pre.next = newNode.next;
newNode.next = head.next;
head.next.pre = newNode;
newNode.pre = head;
head.next = newNode;
}
/**定义一个双向链表 **/
public class ListNode{
private String key;
private String val ;
private ListNode next;
private ListNode pre;
public ListNode(String key, String val){
this.key = key;
this.val = val;
this.next = null;
this.pre = null;
}
}
public static void main(String[] args) {
LRUCache lruCache = new LRUCache(4);
lruCache.set("1", "许");
lruCache.set("2", "小");
lruCache.set("3", "朋");
lruCache.set("4", "有");
lruCache.print(lruCache.head);
lruCache.set("2", "大");
lruCache.print(lruCache.head);
lruCache.set("5", "yuan");
lruCache.print(lruCache.head);
}
public void print(ListNode node){
while(node != null){
String key = node.key;
System.out.print(key);
node = node.next;
}
}
}
原文地址:https://blog.csdn.net/xupengbo527/article/details/140734957
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!