java：了解LRU实现

我想了解下面给出的LRU实现。想不出以下几点：java：了解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; 
    } 
}

来源

2013-12-11 Himanshu Yadav

毫无疑问是愚蠢的人。没有你超载addfirst方法？ –

没有。我不这么认为。 –

我觉得这里的关键是它不只是一个双向链表，它是一个圆形双向链表。因此oldest是-最近使用的元素，oldest.right是-第二最小-最近使用的元素。。。 oldest.left是最为-最近使用的元素。（和oldest.left.left是秒最 -recently使用的元素，依此类推。）

我不知道为什么有人做过这样—看起来它会更简单有一个oldest指向最近最少使用的和指向最近使用的—但它并不重要。

addFirst()有什么用。该方法从put和get方法中都被调用。

addFirst删除从当前位置在列表中的指定条目，并将其添加到的oldest左侧，从而将其标记为最近使用最多的元素。

双向链表如何帮助跟踪最旧的条目？所有条目实际上都在地图中，其中一个条目不知道另一个条目。

好，所以有在此实现一个严重的错误：它从来没有真正从map删除任何元素，所以它并不是一个真正的LRU缓存。更糟糕的是，它永远不会在它所谓的“删除”的条目上将left和right置零，这意味着当这些条目随后从map和addFirst -ed中检索出来时，列表序列最终完全错误。所以这个实现很糟糕。

但它怎么样假设工作是这样的：map只是所有的条目，但它不知道哪一个是最近最少使用。该列表保留了所有元素的最近使用顺序，因此在任何给定时间，oldest是最近最少使用的元素。

（对于错误的根本原因是remove被用于两个不同的东西：addFirst只需要它从它在列表中的位置删除元素，因此它可以被移动到新位置，而put实际上需要能够除去来自map的oldest。大概remove当前版本应该内联成addFirst，和一个新的removeOldest应创建实际删除最早的元素。）

来源

2013-12-11 18:56:18 ruakh

感谢您详细解释它。你知道更简单的LRU实现而不使用'LinkedHashMap'吗？ –

@HimanshuYadav：这个实现是一个很好的开始，它只有一个严重的错误和一个不必要的复杂性。为了解决严重的错误，请参阅我的最后一段。为了简化复杂性，只需在'最古老'旁边添加一个'最新'字段。 'newest.right'和'oldest.left'将为'null'。 – ruakh

什么用addfirst仅的（）。这种方法被称为从放和得到的方法。

最近最少使用的数据结构需要在条目被访问时更新。当您put时，您希望将条目添加到前面，因为它是最近使用的条目。当你从LRU入口get时，它又是最近使用的，所以把它带到LRU的前面。

双向链表如何帮助跟踪最旧的条目？所有条目实际上都在地图上，其中一个条目不知道另一个条目。

查看LinkedHashMap的执行情况。双向链表清除访问命令。每个条目都知道在它之前和之后访问哪个条目。

来源

2013-12-11 18:55:04

java：了解LRU实现

回答

相关问题