LRU算法

1. package LRU缓存;
3. import java.util.Arrays;
4. import java.util.HashMap;
6. //建立一个双向队列
7. class MyQueueNode{
8.     int key;
9.     int value;
10.     MyQueueNode pre;
11.     MyQueueNode next;
12.     public MyQueueNode(int key,int value){
13.         this.key = key;
14.         this.value=value;
15.     }
16. }
17. class MyQueue{
18.     MyQueueNode head;
19.     MyQueueNode tail;
20.     public MyQueue(){
21.         head=new MyQueueNode(-1,-1);
22.         tail=new MyQueueNode(-1,-1);
23.         head.next=tail;
24.         tail.pre=head;
25.     }
26. }
27. //最近最少使用
28. public class LRUCache {
29.     int capacity;
30.     MyQueue myQueue;
31.     HashMap<Integer, MyQueueNode> hashMap;
32.     public LRUCache(int capacity) {
33.         this.capacity=capacity;
34.         myQueue=new MyQueue();
35.         hashMap = new HashMap<>();
36.     }
37.     public int get(int key) {
38.         if (!hashMap.containsKey(key)){
39.             return -1;
40.         }
41.         MyQueueNode node = hashMap.get(key);
42.         //已经使用了要将这个节点插入至队列的末尾
43.         removeNode(node);
44.         insertIntoTail(node);
45.         return node.value;
46.     }
47.     //更换至末尾
48.     public void insertIntoTail(MyQueueNode node) {
49.         node.pre=myQueue.tail.pre;
50.         myQueue.tail.pre.next=node;
52.         node.next=myQueue.tail;
53.         myQueue.tail.pre=node;
54.     }
55.     public void removeNode(MyQueueNode node){
56.         node.next.pre=node.pre;
57.         node.pre.next=node.next;
58.     }
59.     public void put(int key, int value) {
60.         if (get(key)!=-1){
61.             //存在
62.             hashMap.get(key).value=value;
63.         }else{
64.             //超过容量 移除头节点
65.             if (hashMap.size()>=capacity){
66.                 MyQueueNode node = myQueue.head.next;
67.                 hashMap.remove(node.key);
68.                 removeNode(myQueue.head.next);
69.             }
70.             //新增节点
71.             MyQueueNode newNode = new MyQueueNode(key,value);
72.             hashMap.put(key,newNode);
73.             insertIntoTail(newNode);
74.         }
75.     }
76. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。