从问题本身我们可以看出,查询链表时出现了O(n)操作的问题。因此,我们需要一种替代的数据结构。我们需要能够在不进行搜索的情况下从 HashMap 更新项目的上次访问时间。
我们可以保留两个独立的数据结构。 A带(键,指针)的 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++;
}
}
}