我试图理解下面给出的LRU实现。无法确定以下内容：addFirst()的用途是什么。从put和get方法都调用此方法。
双链列表如何帮助跟踪最早的条目？所有条目实际上都在地图中，其中一个条目不知道另一条目。
这些问题听起来很愚蠢，但我非常感谢您的解释。
码：
import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;
public class LRUDLL<K, V> {
private final Map<K, Entry<K,V>> map;
private Entry<K, V> oldest;
private final int lruSize;
public LRUDLL (int lruSize) {
if(lruSize <= 0){
throw new IllegalArgumentException("Size is inappropriate");
}
map = new HashMap<K, Entry<K, V>>();
this.lruSize = lruSize;
}
private static class Entry<K, V> {
Entry<K, V> left;
Entry<K, V> right;
K key;
V value;
Entry(Entry<K, V> left, K key, V value, Entry<K, V> right) {
this.left = left;
this.key = key;
this.value = value;
this.right = right;
}
};
private void addFirst(Entry<K, V> entry) {
remove(entry);
if(oldest == null) {
entry.left = entry.right = entry;
oldest = entry;
} else {
Entry<K, V> tail = entry;
tail.right = entry;
entry.left = tail;
//deal with circulating
oldest.left = entry;
entry.right = oldest;
}
}
private void remove (Entry<K, V> entry) {
assert entry != null;
if(entry.left != null) entry.left.right = entry.right;
if(entry.right != null) entry.right.left = entry.left;
if(entry == oldest) oldest = entry.right;
}
public synchronized void put (K key, V value) {
Entry<K, V> entry = new Entry<K, V>(null, key, value, null);
map.put(key, entry);
addFirst(entry);
if(removeOldestEntry()) {
remove(oldest);
}
}
public synchronized V get(K key) {
Entry<K, V> entry = map.get(key);
if(entry!= null) {
addFirst(entry);
return entry.value;
}
return null;
}
private boolean removeOldestEntry() {
return map.size() > lruSize;
}
}
最佳答案
我认为这里的关键是它不仅是一个双向链接列表，而且是一个循环双向链接列表。因此，oldest是最近最少使用的元素，oldest.right是最近最少使用的元素。 。 。 oldest.left是最近使用的元素。 （oldest.left.left是最近使用的第二个元素，依此类推。）
我不确定为什么要这样进行-似乎将oldest指向最近最少使用而将newest指向最近最近使用会更简单-但是它没有没关系。
addFirst()的用途是什么。从put和get方法都调用此方法。addFirst从列表中的当前位置删除指定的条目，并将其添加到oldest的左侧，从而将其标记为最近使用的元素。
双链列表如何帮助跟踪最早的条目？所有条目实际上都在地图中，其中一个条目不知道另一条目。
好吧，因此此实现中存在一个严重的错误：它实际上从未从map中删除任何元素，因此它实际上不是LRU缓存。更糟糕的是，它永远不会使应该“删除”的条目中的left和right无效，这意味着当随后从map检索这些条目并重新addFirst -ed时，列表序列最终完全错误。因此，实现是相当糟糕的。
但是，它应该如何工作的是：map仅具有所有条目，但是对于最近最少使用的条目一无所知。该列表按使用顺序将所有元素按顺序排列，因此在任何给定时间，oldest是最近使用最少的元素。
（该错误的根本原因是remove被用于两个不同的事物：addFirst只需要将其从列表中的位置移除某个元素，因此可以将其移至新位置，而实际上需要能够从put中删除oldest。可能将map的当前版本内联到remove中，并且应该创建一个新的addFirst来实际上删除最旧的元素。）