这是工作面试中经常提到的一个问题。这个想法是定义一个数据结构,而不是使用Java在LinkedHashMap中内置的结构。
LRU缓存会删除 最近最少使用的 条目,以插入新的条目。因此,鉴于以下情况:
A - B - C - D - E
其中A是最近最少使用的项目,如果要插入F,则需要删除A。
如果我们保留一个HashMap,其中包含按(键,值)的缓存条目以及包含元素的键和使用时间的单独列表,则可以轻松实现这一点。但是,我们需要查询列表以查找最近使用最少的项目,其潜在的时间复杂度为O(n)。
如何在Java中为泛型html" target="_blank">对象和O(1)操作实现此结构?
这与可能的副本有所不同,因为它专注于效率(O(1)ops)和实现数据结构本身,而不是扩展Java。
从问题本身可以看出,查询链接列表时会出现O(n)操作问题。因此,我们需要替代的数据结构。我们需要能够从HashMap更新项目的上次访问时间,而无需进行搜索。
我们可以保留两个单独的数据结构。 具有(Key,Pointer) 对和 双链表 的 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++;
}
}
}
大多数LRU缓存教程强调组合使用双向链表和字典。字典保存该值和对链表上相应节点的引用。 当我们执行删除操作时,我们从字典中的链表中查找节点,我们必须将其删除。 现在这里是它变得奇怪的地方。大多数教程认为,我们需要前面的节点才能从链表中删除当前节点。这样做是为了获得O(1)时间。 但是,这里有一种方法可以在O(1)时间内从单链接列表中删除节点。我们将当前节点的值设置为下一个节点,然后杀死下一个节点。
问题内容: 我正在为我的PHP驱动的网站寻找内存缓存。它不是高流量的网站,我只想缓存数据和某些页面的某些部分以提高性能。数据大小从几字节到几kB不等。我目前正在使用xCache,并且没有问题。 切换到内存缓存或Redis更好吗?有没有更好的选择? 问题答案: 如果您没有任何明显的问题,为什么要立即切换?内存缓存或Redis可能更好,但是如果您现在不需要它们,最好保留它们。只要您的缓存策略是正确的,
问题内容: 所以我有一张地图: 我会像这样添加元素: 我有如下通用方法: 现在,这段代码可以很好地工作,并且没有编译器问题: 但是,当我尝试这样做时: 编译器向我显示以下警告:类型安全:通用方法verifyType(String,Class)的未经检查的调用verifyType(String,Class) 这让我感到困惑…请帮助… 问题答案: 更改: 至 通过仅将类型声明为“ Class”,就失去
问题内容: 我为缓存编写了一个函数来检索特定对象。这样我就不需要投了。 我正在这样使用 但是现在我的缓存中有一个字符串列表,我不能这样使用 问题是。我对Java非常陌生,我该怎么写? 问题答案: 您无法获得的类,在您的情况下,唯一的方法是:
问题内容: 我知道实现起来很简单,但是我想重用已经存在的东西。 我要解决的问题是,我为不同的页面,角色加载了配置(从XML,所以我想缓存它们),因此输入的组合可以增长很多(但99%的增长)。为了处理这一1%,我想在缓存中设置一些最大项目… 直到我在apache commons中找到了org.apache.commons.collections.map.LRUMap,它看起来还不错,但还想检查一下其
这个代码的大O是什么?我知道除了递归部分,所有的线都是O(1)。我不确定递归的大O是什么,我有一种感觉,它仍然是O(1),因为我们没有比O(1)更差的线,但通常递归是O(n)。 代码: 编辑:顺便说一句,这不是家庭作业,而是为面试做准备。