0

我已经使用哈希表+链表实现了 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 中删除。

从本质上讲，我要维护整个序列，如果有数百万个条目，那就不好了。除了使用优先级队列+哈希表之外，还有什么方法可以改善这一点

4

1 回答 1

0

你需要维护整个序列，如果有几百万个条目，只要你做对了，那也不错。

关键是像制作任何其他哈希表一样制作哈希表。然后，您只需使用哈希表中的引用，而不是遍历链表来定位这个最近使用的节点。您将其从中间断开并将其移至前面。

从链表中删除元素是一个恒定时间操作，前提是您可以找到要开始的节点。如果没有哈希表，则必须迭代（线性时间），但由于您确实有哈希表，因此您不必进行任何迭代。

于 2012-10-11T23:04:26.180 回答