排序字典按C#(LRU缓存)中的值排序

Question

我想实现一个LRU cache,其中最近最少使用的元素将被异步驱逐.我目前的想法是使用a Dictionary存储<key,value>对,并跟踪对象的访问次数,以保持对SortedDictionary <key, timestamp>.我们的想法是让异步线程SortedDictionary从缓存中获取LRU项并从缓存中删除.但要实现这一点,SortedDictionary需要按值排序,而不是按值排序.

我可以使用一个单独的SortedList而不是SortedDictionary保持{key和timestamp}按时间戳排序,但是然后我将不得不进行"线性"查找以从列表中查找键(当我必须更新时间戳时,当再次访问相同的密钥时) - 如果可能的话,我正在寻找比线性更好的方法.有人可以分享想法来处理这个问题吗？

所以,我的问题归结为:

我要在<= logn时间内查找键以更新时间戳,同时能够根据时间戳对键进行排序.

想到了一个办法是保持SortedDictionary的<{key,timestamp},null>哪些订单基于{键,时间戳}的时间戳部分的按键.虽然这很好,但问题是hashcode()只需要返回key.hashcode()(用于在更新时间戳时查找),同时equals()还应该使用时间戳.所以,equals()并且hashcode()发生冲突,所以觉得这不是一个好主意......

Answer 1

你应该做的是保留两本字典，一本按时间排序，一本按键排序。

请记住，字典仅保存对实际对象的引用，因此使用哪个字典来更新对象并不重要。

要更新对象，请创建一个将更新两个字典的函数

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

现在您可以通过时间和键来跟踪同一对象。

我只保留对 中某个对象的一个​​引用timedObjects。这有助于移除。

您可以根据需要不断修剪 timedObjects 字典。

当然，在修剪时，您必须记住，还有另一个字典keyedObject引用了同一对象。仅仅打电话Remove是不够的。

您的删除代码必须如下所示：

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

timeToRemove 主要来自 for 循环，您可以在其中决定要删除哪个对象