我該如何改進我的lru實現

Question

我已經使用散列表+鏈接列表實現了LRU。

哈希表已鏈接。代碼結構如下：

struct Node{ 
int value; 
struct Node *next; 
struct Node* head; 
struct Node* tail; 

}; 



struct Node* lruhashtable[10]; 
struct Node* trackHead; 
struct Node* trackTail; 

trackHead和trackTail指針用於跟蹤插入的順序。這用於刪除最近使用過的元素。我認爲有多個替代政策是使用而不是一個。因此，LRU與某些東西結合使用。因此，如果一個元素要從LRU中刪除，因爲我再次訪問該元素，那麼我需要將它從LRU中刪除。

固有我保持整個序列，如果有幾百萬的條目是壞的。有沒有什麼辦法來改善這個除了使用優先級隊列+哈希表

Answer 1

你需要保持整個序列，如果只要你這樣做是正確的有上百萬個條目的它不壞。

的關鍵是哈希表，就像您的任何其他哈希表。然後，不要遍歷鏈表來定位這個最近使用的節點，而只需在散列表中使用引用。您從中間取消鏈接並將其移到前面。

去除鏈表的元素是隻要你能找到開始與節點的恆定時間操作。如果沒有散列表，你將不得不迭代（線性時間），但由於你有散列表，你不必做任何迭代。