我想实现一个LRU缓存,其中最近最少使用的元素将被异步驱逐.我目前的想法是使用Dictionary来存储< key,value>对,并跟踪对象的访问次数,以保持SortedDictionary< key,timestamp>.我们的想法是让异步线程从SortedDictionary获取LRU项并从缓存中删除.但要实现这一点,SortedDictionary需要按值排序,而不是.
我可以使用单独的SortedList而不是SortedDictionary来保持{key和timestamp}在时间戳上排序,但是我将不得不进行“线性”查找以从列表中查找键(当我必须更新时)时间戳,当再次访问相同的密钥时) – 如果可能的话,我正在寻找比线性更好的方法.有人可以分享想法来处理这个问题吗？
所以,我的问题归结为：
我要在< = logn time中查找键以更新时间戳,同时能够获得基于时间戳排序的键. 一种方法是保持SortedDictionary为< {key,timestamp},null>它根据{key,timestamp}的时间戳部分对键进行排序.虽然这很好,但问题是hashcode()只需要返回key.hashcode()(用于在更新时间戳时查找),而equals()也应该使用时间戳.所以,equals()和hashcode()是冲突的,所以觉得这不是一个好主意……
解决方法
你应该做的是保留两个词典,一个按时间排序,一个按键排序.
请记住,字典只保存对实际对象的引用,因此用于更新对象的字典无关紧要.
要更新对象,请创建一个将更新这两个词典的函数
var oldObj = keyedObject[key]; timedObjects.Remove(oldObj.LastUpdateTime); timedObjects.Add(myUpdatedObject.LastUpdateTime,myUpdatedObject); keyedObject[key] = myUpdatedObject;
现在,您可以通过时间和关键字跟踪同一个对象.
我只对timedObjects中的对象保留一个引用.这有助于删除.
您可以根据需要继续修剪timedObjects字典.
Ofcource,虽然修剪你必须记住,有另一个字典keyedObject引用同一个对象.仅仅呼叫删除是不够的.
removeObject = timedObjects[timeToRemove]; timedObjects.Remove(timeToRemove); keyedObject.Remove(removeObject.key);
timeToRemove主要来自for循环,您可以在其中决定要删除的对象
