Dictionary<>总是按值排序，通过键查找索引

Question

我需要一个字典（或其他集合），它可以始终按值排序，并且可以通过键进行索引。我的目的是实现一个缓存，其中对象具有唯一的键和与之关联的度量标准。当需要进行缓存替换时，将删除度量最小的对象。为了尽可能快速，因此每次进行替换时进行完整排序并不是一个好选择。有任何想法吗？谢谢

- Ricardo

---

一个 KeyedCollection<TKey TItem> 是否适合您的需求？http://msdn.microsoft.com/en-us/library/ms132438.aspx 是该项的关键部分吗？ - Russ Cam

如何按值对 C# 字典进行排序 - https://dev59.com/93VD5IYBdhLWcg3wXaid - sll

可能是重复的问题：.NET SortedDictionary But Sorted By Values - nawfal

Answer 1

这样的代码应该可以很好地运行（未经过太多测试）：

http://pastebin.com/eYeE33F5

- digEmAll

Answer 2

为什么不直接使用普通的字典呢？每当需要进行缓存替换时，只需选择具有“最小”值的元素并将其替换即可。

编辑 - 这是如何获取具有最小值的KeyPair。只需在此之后使用Key和Value属性：

var minValuePair = myDictionary.OrderBy(p => p .Value).First();

- Vladimir

---

感谢您的回答。现在我正在做类似这样的事情：myDictionary.Min(x => x.Value)，但速度非常慢。我希望字典总是能够排序，也就是说，当一个新对象被插入到字典中时，它应该根据其指标放置在正确的位置上。 - Ricardo

@Ricardo 是的，实际上我提供了另一种解决方案。你说你需要排序后的字典以便在需要更新缓存时删除最小值对。这意味着你并不总是需要排序后的字典，你只需要有时获取最小值即可。 - Vladimir

Answer 3

看起来优先队列是你正在寻找的。使用二叉堆有很好的这个类的实现。例如：http://www.codeproject.com/Articles/126751/Priority-queue-in-Csharp-with-help-of-heap-data-st.aspx

- alexm

Answer 4

您可以将任何类型的快速优先队列与标准字典组合成一个新集合（请参见：.Net中的优先队列）。插入新元素时，将元素的引用插入两个容器。当按“键”查找元素时，请使用字典。当要删除具有最低“度量”的元素时，请使用优先队列进行查找，从元素本身获取键，然后轻松地从两个容器中删除元素引用。

- Doc Brown

---

谢谢@Doc，这是个好主意。然而，当用户请求一个已经存储在缓存中的对象时，它必须被更新，以便其度量值发生变化，并且队列中的顺序也应该被更新。例如，如果使用LFU（最不经常使用）策略，每次请求对象时，其频率计数器（用作指标）都会增加一。 - Ricardo

@Ricardo：使用“C5通用集合库”（http://www.itu.dk/research/c5/）来实现你的优先队列，它具有在队列中删除元素的操作，这使得你能够在指标发生变化时删除和重新插入元素。为了使其工作，你需要在字典中存储IPriorityQueueHandle元素而不是元素本身，但这不应该变得太复杂。 - Doc Brown

Answer 5

你想要一个按值排序并且可以通过键索引的字典。数据不能同时以两种方式排列，因此你需要有两个集合：基本的键值字典和一个反向查找字典。第一个是标准字典，第二个是具有相同数据但键和值交换的SortedDictionary。你需要保持这两个字典同步。

你也可以编写自己的字典实现，将这两个集合封装成一个。

- Tim Rogers

---

谢谢。问题在于可能会有多个具有相同值（度量）的对象。 - Ricardo

digEmAll的链接基本上就是我想到的解决方案。请调查一下。 - Tim Rogers