我该如何改进我的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

你需要保持整个序列，如果只要你这样做是正确的有上百万个条目的它不坏。

的关键是哈希表，就像您的任何其他哈希表。然后，不要遍历链表来定位这个最近使用的节点，而只需在散列表中使用引用。您从中间取消链接并将其移到前面。

去除链表的元素是只要你能找到开始与节点的恒定时间操作。如果没有散列表，你将不得不迭代（线性时间），但由于你有散列表，你不必做任何迭代。