这是一个在求职面试中经常出现的问题。这个想法是定义一个数据结构，而不是使用Java内置的LinkedHashMap。
LRU 缓存删除最近最少使用的条目以插入新条目。因此，给定以下场景：
A - B - C - D - E
如果 A 是最近最少使用的项目，如果我们要插入 F，则需要删除 A。
如果我们保留一个HashMap，其中包含缓存条目（键，值）和一个包含元素的键和使用时间的单独列表，这可以很容易地实现。但是，我们需要查询列表以查找最近使用最少的项目，具有潜在的O（n）时间复杂度。
如何在 Java 中为通用对象和 O（1） 操作实现此结构？
这与可能的副本不同，因为它专注于效率（O（1）操作）和实现数据结构本身，而不是扩展Java。
从问题本身，我们可以看到，在查询链表时会出现O（n）操作的问题。因此，我们需要一个替代的数据结构。我们需要能够在不搜索的情况下从HashMap更新项目的上次访问时间。
我们可以保留两个独立的数据结构。具有（键，指针）对和双链表的哈希映射，该列表将用作删除的优先级队列并存储值。从HashMap中，我们可以指向双链表中的一个元素并更新其检索时间。因为我们直接从 HashMap 转到列表中的项目，所以我们的时间复杂度保持在 O（1）
例如，我们的双链表可以如下所示：
least_recently_used -> A <-> B <-> C <-> D <-> E <- most_recently_used
我们需要保留一个指向 LRU 和 MRU 项的指针。条目的值将存储在列表中，当我们查询HashMap时，我们将获得指向列表的指针。在 get（） 上，我们需要将项目放在列表的最右侧。在 put（key，value） 上，如果缓存已满，我们需要从列表和 HashMap 中删除列表最左侧的项目。
下面是 Java 中的一个示例实现：
public class LRUCache<K, V>{
// Define Node with pointers to the previous and next items and a key, value pair
class Node<T, U> {
Node<T, U> previous;
Node<T, U> next;
T key;
U value;
public Node(Node<T, U> previous, Node<T, U> next, T key, U value){
this.previous = previous;
this.next = next;
this.key = key;
this.value = value;
}
}
private HashMap<K, Node<K, V>> cache;
private Node<K, V> leastRecentlyUsed;
private Node<K, V> mostRecentlyUsed;
private int maxSize;
private int currentSize;
public LRUCache(int maxSize){
this.maxSize = maxSize;
this.currentSize = 0;
leastRecentlyUsed = new Node<K, V>(null, null, null, null);
mostRecentlyUsed = leastRecentlyUsed;
cache = new HashMap<K, Node<K, V>>();
}
public V get(K key){
Node<K, V> tempNode = cache.get(key);
if (tempNode == null){
return null;
}
// If MRU leave the list as it is
else if (tempNode.key == mostRecentlyUsed.key){
return mostRecentlyUsed.value;
}
// Get the next and previous nodes
Node<K, V> nextNode = tempNode.next;
Node<K, V> previousNode = tempNode.previous;
// If at the left-most, we update LRU
if (tempNode.key == leastRecentlyUsed.key){
nextNode.previous = null;
leastRecentlyUsed = nextNode;
}
// If we are in the middle, we need to update the items before and after our item
else if (tempNode.key != mostRecentlyUsed.key){
previousNode.next = nextNode;
nextNode.previous = previousNode;
}
// Finally move our item to the MRU
tempNode.previous = mostRecentlyUsed;
mostRecentlyUsed.next = tempNode;
mostRecentlyUsed = tempNode;
mostRecentlyUsed.next = null;
return tempNode.value;
}
public void put(K key, V value){
if (cache.containsKey(key)){
return;
}
// Put the new node at the right-most end of the linked-list
Node<K, V> myNode = new Node<K, V>(mostRecentlyUsed, null, key, value);
mostRecentlyUsed.next = myNode;
cache.put(key, myNode);
mostRecentlyUsed = myNode;
// Delete the left-most entry and update the LRU pointer
if (currentSize == maxSize){
cache.remove(leastRecentlyUsed.key);
leastRecentlyUsed = leastRecentlyUsed.next;
leastRecentlyUsed.previous = null;
}
// Update cache size, for the first added entry update the LRU pointer
else if (currentSize < maxSize){
if (currentSize == 0){
leastRecentlyUsed = myNode;
}
currentSize++;
}
}
}
通过简单的单元测试通过 leetcode 问题的测试的实现
我已经在以下位置提出了一个拉取请求：https://github.com/haoel/leetcode/pull/90/files 代码后来在答案中得到了改进，我没有费心再提出另一个拉取请求，所以这里的代码现在稍微好一些。accessOrder = true
LRUCache.java
import java.util.Iterator;
import java.util.LinkedHashMap;
public class LRUCache {
private int capacity;
private LinkedHashMap<Integer,Integer> map;
public LRUCache(int capacity) {
this.capacity = capacity;
this.map = new LinkedHashMap<>(16, 0.75f, true);
}
public int get(int key) {
Integer value = this.map.get(key);
if (value == null) {
value = -1;
}
return value;
}
public void put(int key, int value) {
if (
!this.map.containsKey(key) &&
this.map.size() == this.capacity
) {
Iterator<Integer> it = this.map.keySet().iterator();
it.next();
it.remove();
}
this.map.put(key, value);
}
}
LRUCacheTest.java
public class LRUCacheTest {
public static void main(String[] args) {
LRUCache c;
// Starts empty.
c = new LRUCache(2);
assert c.get(1) == -1;
// Below capcity.
c = new LRUCache(2);
c.put(1, 1);
assert c.get(1) == 1;
assert c.get(2) == -1;
c.put(2, 4);
assert c.get(1) == 1;
assert c.get(2) == 4;
// Above capacity, oldest is removed.
c = new LRUCache(2);
c.put(1, 1);
c.put(2, 4);
c.put(3, 9);
assert c.get(1) == -1;
assert c.get(2) == 4;
assert c.get(3) == 9;
// get renews entry
c = new LRUCache(2);
c.put(1, 1);
c.put(2, 4);
assert c.get(1) == 1;
c.put(3, 9);
assert c.get(1) == 1;
assert c.get(2) == -1;
assert c.get(3) == 9;
// Double put does not remove due to capacity.
c = new LRUCache(2);
assert c.get(2) == -1;
c.put(2, 6);
assert c.get(1) == -1;
c.put(1, 5);
c.put(1, 2);
assert c.get(1) == 2;
assert c.get(2) == 6;
}
}
removeEldestEntry（） alternative implementation
不确定它是否值得，因为它需要相同数量的行，但这里是为了完整性：
import java.util.LinkedHashMap;
import java.util.Iterator;
import java.util.Map;
import java.io.*;
class LinkedhashMapWithCapacity<K,V> extends LinkedHashMap<K,V> {
private int capacity;
public LinkedhashMapWithCapacity(int capacity) {
super(16, 0.75f, true);
this.capacity = capacity;
}
@Override
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return this.size() > this.capacity;
}
}
public class LRUCache {
private LinkedhashMapWithCapacity<Integer,Integer> map;
public LRUCache(int capacity) {
this.map = new LinkedhashMapWithCapacity<>(capacity);
}
public int get(int key) {
Integer value = this.map.get(key);
if (value == null) {
value = -1;
}
return value;
}
public void put(int key, int value) {
this.map.put(key, value);
}
}
在 Ubuntu 20.10、OpenJDK 11.0.10 上测试。
