按C＃中的值排序的字典（LRU緩存）

我想實現一個LRU cache，其中最近最少使用的元素將被異步驅逐。我目前的想法是使用Dictionary來存儲<key,value>對，並跟蹤訪問對象的時間，以保留SortedDictionary <key, timestamp>。這個想法是讓異步線程從SortedDictionary獲取LRU項並從緩存中移除。但爲了這個工作，SortedDictionary需要按價值排序，而不是。按C＃中的值排序的字典（LRU緩存）

我本來可以使用單獨的SortedList而不是SortedDictionary來保持時間戳上的{key和timestamp}排序，但是我必須做一個「線性」查找來查找列表中的鍵（當我必須更新時間戳，當再次訪問同一個鍵時） - 如果可能，我正在尋找比線性更好的方法。有人可以分享想法來處理這個問題嗎？

所以，我的問題歸結爲：

我已經查找在< = LOGN時間鍵，而在同一時間能夠拿到鑰匙排序基於時間戳更新時間戳。

想到的一種方法是保留的<{key,timestamp},null>，它根據{key，timestamp}的時間戳部分對鍵進行排序。雖然這很好，但問題是hashcode()只需要返回key.hashcode（）（用於在更新時間戳時查找），而equals()也應該使用時間戳。所以，equals()和hashcode()是衝突的，所以覺得這不是一個好主意......

來源

2012-07-26 hari_sree

換句話說，您希望SortedDic像優先級隊列一樣工作，其中優先級由時間戳定義？ SortedDictionary 有什麼問題？順便說一句，它不是O（1）它是O（logn） - 它可能被實現爲紅黑樹。 – 2012-07-26 12:17:06

你應該做的是保持兩個字典，一個按時間排序，一個按鍵。

請記住，字典只保存對您的實際對象的引用，所以用哪個字典更新對象並不重要。

更新對象創建將同時更新字典

var oldObj = keyedObject[key]; 
timedObjects.Remove(oldObj.LastUpdateTime); 
timedObjects.Add(myUpdatedObject.LastUpdateTime,myUpdatedObject); 
keyedObject[key] = myUpdatedObject;

現在你有跟蹤同一對象的通過時間和鍵的功能。

我只保留一個對象的引用timedObjects。這有助於消除。

您可以根據需要繼續修剪timedObjects詞典。

Ofcource，雖然修剪你必須記住，有另一個字典keyedObject引用到同一個對象。僅僅撥打Remove將是不夠的。

你刪除的代碼將是這樣的：

removeObject = timedObjects[timeToRemove]; 
timedObjects.Remove(timeToRemove); 
keyedObject.Remove(removeObject.key);

timeToRemove將主要來自一個for循環，在那裏你決定哪些對象以移除

來源

2012-07-26 12:17:19 nunespascal

+1，兩本字典。請注意，紅黑樹木相當緩慢，但它們的表現非常一致。對於速度來說，回合更好，但回合的運作持續時間有很高的標準偏差。 – user1277476 2012-07-26 17:11:20

好主意..但是，我不認爲有必要計算timeToRemove。可以通過timedObjects.first找到要移除的元素（時間戳最少的元素或timedObjects sortedmap中的第一個元素）。禮拜？ – 2012-07-27 11:34:59

是的，如果您一次只移除一個對象，那將起作用。但是您提到想要使用單獨的線程刪除項目。這意味着您的timedObject字典可能會變得比LRU所需的大小更大，並且您將不得不刪除多個項目。 – nunespascal 2012-07-27 11:45:04

你的類型的地圖尋找是（至少在Java中）稱爲LinkedHashMap。

根據JavaDoc：

的哈希表和鏈接列表實現Map接口，具有預知的迭代順序。該實施方式與HashMap 的不同之處在於其保持通過其所有條目運行的雙向鏈表。此鏈接列表定義了迭代排序，通常是鍵被插入到映射中的順序（插入順序）。

一個特殊的構造提供創建鏈接哈希映射，其爲了迭代是其條目上次訪問，從最近最少訪問與最近（存取順序）的順序。這種地圖是非常適合構建LRU 緩存。

Source for LinkedHashMap from the OpenJDK

AFAIK，有LinkedHashMap在C＃沒有現有的實現。話雖如此，編寫一個應該不是很難。

來源

2012-07-26 12:28:12

代替sorteddictionary，編寫自己的鏈接列表，並將Dictionary指向它的節點作爲值。它將總是按時間戳排序，更新時間戳，並刪除最少使用的元素將是O（1）。

來源

2012-07-26 12:35:34 user1096188

按C＃中的值排序的字典（LRU緩存）

回答

相關問題