获取字典中最大的密钥

我有一个包含整数键的字典。 我想得到最大的钥匙。 我不跟踪密钥，因此它们可能是连续的（例如1,2,3,4,5,6），但可能会跳过（1,3,4,5），尽管我怀疑这有什么不同。

我只是使用二进制搜索还是有方法？ 据我所知，你几乎无法击败二元搜索这么简单的任务 – 也许你可以把它减半。

Answer 1

如果您有LINQ可用，您应该能够：

 myDictionary.Keys.Max(); 

Answer 2

二进制搜索将是最快的，但不会对正常字典起作用，因为密钥不以任何特定顺序存储。 使用Linq Max() ，@ Minitech的答案是最简单的，如果您使用普通字典。

如果这是一项操作，您将需要多次执行，您可以考虑转移到SortedDictionary ，它根据键对条目进行排序。

 var dict = new SortedDictionary {{3, 0}, {12, 0}, {32, 0}, {2, 0}, {16, 0}, {20, 0}}; Console.WriteLine(dict.Keys.Last()); //prints 32 

编辑：这可能比普通字典慢 。 我想如果提到那就好了。 那是因为字典中的条目以不同的方式存储（红/黑树vs散列桶/散列表）

有一点是SortedDictionary比普通的Dictionary更快。 然而，这可能会出现大约100万件物品，但这只是猜测。 事实certificate它在那么多项目上快了大约10倍（但我们谈论的是100秒，所以它真的很重要吗？）。 对于100000个项目，它在x64版本上大致相同。 考虑到在字典中添加项目会产生额外的开销，这可能不值得。 另外，我通过重写比较器来“欺骗”一点，所以它会按相反的顺序排序，所以我实际上是在做dict.Keys.First()而不是last来获得最大的项目。

如果您需要按顺序迭代所有键值对，那么SortedDictionary真正意味着。 我认为@ SimonMourier的回答可能是最好的。 我保证你最快，最小的开销。

Answer 3

如果性能确实是一个问题，我会在现有的类之上创建一个新类，实现标准接口，如下所示：

  public class RememberMaxDictionary : IDictionary where K: IComparable { private Dictionary _inner; public RememberMaxDictionary() { _inner = new Dictionary(); } public K MaxKey { get; private set; } public void Add(K key, V value) { _inner.Add(key, value); if (key.CompareTo(MaxKey) > 0) // test null if needed { MaxKey = key; } } ... TODO implement the rest...