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

Question

我想实现一个 LRU cache ，其中最近最少使用的元素将被异步驱逐。我目前的想法是使用 Dictionary存储 <key,value> pairs ，并跟踪对象的访问时间，以保持 SortedDictionary <key, timestamp> .这个想法是让异步线程从 SortedDictionary 中获取 LRU 项。并从缓存中删除。但是为了让它起作用，SortedDictionary需要按值排序，而事实并非如此。

我本可以使用单独的 SortedList而不是 SortedDictionary用于保持 {key and timestamp} 在 timestamp 上排序，但随后我必须进行“线性”查找以从列表中查找 key (当我必须更新时间戳时，再次访问相同的 key 时) - 如果可能的话，我正在寻找一种比线性方式更好的方式。有人可以分享解决这个问题的想法吗？

所以，我的问题归结为:

我必须在 <= logn 时间内查找键以更新时间戳，同时能够根据时间戳对键进行排序。

想到的一种方法是保留一个 SortedDictionary的 <{key,timestamp},null>它根据 {key,timestamp} 的时间戳部分对键进行排序。虽然这很好，但问题是 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 字典。

Ofcource，在修剪时你必须记住还有另一个字典 keyedObject 引用了同一个对象。仅仅调用 Remove 是不够的。

您的删除代码必须是这样的:

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

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