按C＃中的值排序的排序字典（LRU缓存）
我想实现一个LRU cache ，其中最近使用最少的元素将被异步驱逐。 我目前的想法是使用Dictionary存储<key,value>对，并跟踪访问对象的次数，以保持SortedDictionary <key, timestamp> 。 这个想法是让异步线程从SortedDictionary获取LRU项并从缓存中移除。 但是为了这个工作， SortedDictionary需要按价值排序，而不是。
我可以使用单独的SortedList而不是SortedDictionary来保持时间戳上的{key和timestamp}排序，但是我必须做一个“线性”查找来查找列表中的键值（当我必须更新时时间戳，当再次访问相同的密钥时） - 如果可能，我正在寻找一种比线性更好的方法。 有人可以分享想法来处理这个问题吗？
所以，我的问题归结为：
我必须在<= logn时间内查找密钥才能更新时间戳，同时能够根据时间戳获取密钥。
一种想法是保持一个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 。 这有助于消除。
您可以根据需要继续修剪timedObjects字典。
Ofcource，在修剪时必须记住有另一个字典keyedObject引用了同一个对象。 仅仅调用Remove就不够。
你的移除代码必须是这样的：
removeObject = timedObjects[timeToRemove];
timedObjects.Remove(timeToRemove);
keyedObject.Remove(removeObject.key);
timeToRemove将主要来自for循环，您可以在其中决定要删除哪个对象
您正在寻找的地图类型（至少在Java中）称为LinkedHashMap 。
从javadoc：
哈希表和Map接口的链表实现，具有可预测的迭代顺序。 这个实现与HashMap的不同之处在于它保持了一个双向链表，它贯穿其所有条目。 这个链表定义了迭代排序，这通常是键被插入映射的顺序（插入顺序）。
提供了一个特殊的构造函数来创建一个链接哈希映射，其迭代顺序是最后访问它的条目的顺序，从最近访问到最近（访问顺序）。 这种地图非常适合构建LRU缓存 。
来自OpenJDK的LinkedHashMap
AFAIK，C＃中没有LinkedHashMap现有实现。 尽管如此，编写一个应该不是非常困难。
而不是sorteddictionary，写你自己的链表，并让Dictionary指向它的节点作为值。 它将总是按时间戳排序，更新时间戳，并删除最少使用的元素将是O（1）。
链接地址: http://www.djcxy.com/p/61801.html