Java如何实现LRU缓存淘汰算法
时间: 2024-03-10 22:43:20 浏览: 33
Java实现LRU缓存淘汰算法的方法与Python类似,也可以使用哈希表和双向链表来实现。下面是一个Java实现的LRU缓存淘汰算法的代码示例:
```java
class LRUCache {
private Map<Integer, Node> map;
private int capacity;
private Node head;
private Node tail;
public LRUCache(int capacity) {
this.capacity = capacity;
map = new HashMap<>();
head = new Node(0, 0);
tail = new Node(0, 0);
head.next = tail;
tail.prev = head;
}
public int get(int key) {
if (map.containsKey(key)) {
Node node = map.get(key);
remove(node);
add(node);
return node.value;
} else {
return -1;
}
}
public void put(int key, int value) {
if (map.containsKey(key)) {
Node node = map.get(key);
node.value = value;
remove(node);
add(node);
} else {
if (map.size() == capacity) {
Node node = tail.prev;
remove(node);
map.remove(node.key);
}
Node node = new Node(key, value);
map.put(key, node);
add(node);
}
}
private void add(Node node) {
Node next = head.next;
head.next = node;
node.prev = head;
node.next = next;
next.prev = node;
}
private void remove(Node node) {
Node prev = node.prev;
Node next = node.next;
prev.next = next;
next.prev = prev;
}
private class Node {
int key;
int value;
Node prev;
Node next;
public Node(int key, int value) {
this.key = key;
this.value = value;
}
}
}
```
在这个实现中,我们同样使用了一个哈希表来查询节点是否存在以及快速删除节点,使用一个双向链表来维护缓存中节点的顺序。当有新的节点被访问时,我们将其移到链表头部,并且当缓存空间不足时,我们淘汰链表尾部的节点。同时,我们使用了一个Node内部类来封装节点的key和value,以及前驱和后继节点的指针。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)