这是在面试中出现的一个问题.这个想法是定义一个数据结构,而不是使用
Java内置的LinkedHashMap.
LRU缓存删除最近最少使用的条目以插入新的条目.
因此,考虑到以下情况：
A - B - C - D - E
其中A是最近最少使用的项目,如果我们插入F,我们需要删除A.
如果我们使用(key,value)保存具有缓存条目的HashMap以及包含元素的键和使用时间的单独列表,则可以轻松实现.但是,我们需要查询列表以找到最近最少使用的项目,具有潜在的O(n)时间复杂度.
如何在Java中为Generic对象和O(1)操作实现此结构？
这与可能的重复不同,它侧重于效率(O(1)ops)和实现数据结构本身,而不是扩展Java.
解决方法
从问题本身,我们可以看到O(n)操作的问题在查询链表时出现.因此,我们需要一个替代的数据结构.我们需要能够从HashMap更新项目的最后访问时间,而无需搜索.
我们可以保留两个单独的数据结构.具有(键,指针)对的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);
mostRecentlyUsed = leastRecentlyUsed;
cache = new HashMap<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,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++;
}
}
}
