要实现一个LRU缓存，可以使用双向链表和哈希表。双向链表用于存储缓存中的元素，按照访问顺序进行排序；哈希表用于快速查找元素在双向链表中的位置。
以下是Java代码实现：
import java.util.HashMap;
public class LRUCache {
private int capacity;
private HashMap<Integer, Node> map;
private Node head;
private Node tail;
public LRUCache(int capacity) {
this.capacity = capacity;
map = new HashMap<>();
head = new Node(-1, -1);
tail = new Node(-1, -1);
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;
}
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) {
map.remove(tail.prev.key);
remove(tail.prev);
}
Node newNode = new Node(key, value);
map.put(key, newNode);
add(newNode);
}
}
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;
}
class Node {
int key;
int value;
Node prev;
Node next;
public Node(int key, int value) {
this.key = key;
this.value = value;
}
}
}
在这个实现中，LRUCache类包含一个容量为capacity的哈希表map，以及两个指向双向链表头部和尾部的节点head和tail。get方法首先检查哈希表中是否存在指定的键，如果存在，则将对应的节点移动到双向链表的头部，并返回其值；否则返回-1。put方法首先检查哈希表中是否已存在指定的键，如果存在，则更新对应的节点的值，并将其移动到双向链表的头部；如果不存在，则创建一个新的节点，将其添加到哈希表和双向链表的头部。当添加新节点时，需要检查当前缓存的大小是否已达到容量上限，如果达到上限，则需要从双向链表的尾部移除最近最少使用的元素（即哈希表中对应的键），并从哈希表中删除该键。
