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實現

回答

相關問題