LRU算法
package LRU缓存;import java.util.Arrays;
import java.util.HashMap;
//建立一个双向队列
class MyQueueNode{
int key;
int value;
MyQueueNode pre;
MyQueueNode next;
public MyQueueNode(int key,int value){
this.key = key;
this.value=value;
}
}
class MyQueue{
MyQueueNode head;
MyQueueNode tail;
public MyQueue(){
head=new MyQueueNode(-1,-1);
tail=new MyQueueNode(-1,-1);
head.next=tail;
tail.pre=head;
}
}
//最近最少使用
public class LRUCache {
int capacity;
MyQueue myQueue;
HashMap<Integer, MyQueueNode> hashMap;
public LRUCache(int capacity) {
this.capacity=capacity;
myQueue=new MyQueue();
hashMap = new HashMap<>();
}
public int get(int key) {
if (!hashMap.containsKey(key)){
return -1;
}
MyQueueNode node = hashMap.get(key);
//已经使用了要将这个节点插入至队列的末尾
removeNode(node);
insertIntoTail(node);
return node.value;
}
//更换至末尾
public void insertIntoTail(MyQueueNode node) {
node.pre=myQueue.tail.pre;
myQueue.tail.pre.next=node;
node.next=myQueue.tail;
myQueue.tail.pre=node;
}
public void removeNode(MyQueueNode node){
node.next.pre=node.pre;
node.pre.next=node.next;
}
public void put(int key, int value) {
if (get(key)!=-1){
//存在
hashMap.get(key).value=value;
}else{
//超过容量 移除头节点
if (hashMap.size()>=capacity){
MyQueueNode node = myQueue.head.next;
hashMap.remove(node.key);
removeNode(myQueue.head.next);
}
//新增节点
MyQueueNode newNode = new MyQueueNode(key,value);
hashMap.put(key,newNode);
insertIntoTail(newNode);
}
}
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]