用Java语言编程运行LRU算法或CLOCK/改进算法等置换算法
时间: 2023-07-16 13:13:14 浏览: 113
LRU页面置换算法(Java)
以下是Java语言实现LRU算法的示例代码:
```java
import java.util.HashMap;
import java.util.Map;
public class LRUCache<K, V> {
private int capacity;
private Map<K, Node<K, V>> map;
private Node<K, V> head;
private Node<K, V> tail;
public LRUCache(int capacity) {
this.capacity = capacity;
map = new HashMap<>();
head = new Node<>(null, null);
tail = new Node<>(null, null);
head.next = tail;
tail.prev = head;
}
public V get(K key) {
Node<K, V> node = map.get(key);
if (node == null) {
return null;
}
remove(node);
addFirst(node);
return node.value;
}
public void put(K key, V value) {
Node<K, V> node = map.get(key);
if (node != null) {
node.value = value;
remove(node);
addFirst(node);
} else {
if (map.size() == capacity) {
map.remove(tail.prev.key);
remove(tail.prev);
}
node = new Node<>(key, value);
map.put(key, node);
addFirst(node);
}
}
private void remove(Node<K, V> node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
private void addFirst(Node<K, V> node) {
node.next = head.next;
node.prev = head;
head.next.prev = node;
head.next = node;
}
private static class Node<K, V> {
K key;
V value;
Node<K, V> prev;
Node<K, V> next;
Node(K key, V value) {
this.key = key;
this.value = value;
}
}
}
```
以下是Java语言实现CLOCK/改进算法的示例代码:
```java
import java.util.HashMap;
import java.util.Map;
public class ClockCache<K, V> {
private int capacity;
private Map<K, Node<K, V>> map;
private Node<K, V> head;
private Node<K, V> tail;
private int pointer;
public ClockCache(int capacity) {
this.capacity = capacity;
map = new HashMap<>();
head = new Node<>(null, null);
tail = new Node<>(null, null);
head.next = tail;
tail.prev = head;
pointer = 0;
}
public V get(K key) {
Node<K, V> node = map.get(key);
if (node == null) {
return null;
}
node.referenced = true;
return node.value;
}
public void put(K key, V value) {
Node<K, V> node = map.get(key);
if (node != null) {
node.value = value;
node.referenced = true;
} else {
if (map.size() == capacity) {
while (true) {
if (pointer == 0) {
pointer = 1;
} else {
Node<K, V> p = head.next;
while (p != tail) {
if (!p.referenced) {
break;
}
p.referenced = false;
p = p.next;
}
if (p == tail) {
p = head.next;
while (p != tail) {
p.referenced = false;
p = p.next;
}
}
pointer = 0;
remove(p);
map.remove(p.key);
break;
}
}
}
node = new Node<>(key, value);
map.put(key, node);
addFirst(node);
}
}
private void remove(Node<K, V> node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
private void addFirst(Node<K, V> node) {
node.next = head.next;
node.prev = head;
head.next.prev = node;
head.next = node;
}
private static class Node<K, V> {
K key;
V value;
boolean referenced;
Node<K, V> prev;
Node<K, V> next;
Node(K key, V value) {
this.key = key;
this.value = value;
this.referenced = true;
}
}
}
```
阅读全文