获取字典中最大的键

本文关键字：字典 获取 | 更新日期: 2023-09-27 18:16:12

我有一个键为整型的字典。我想要得到最大的键。我不跟踪键，所以它们可能是连续的(例如1,2,3,4,5,6)，但可能会跳过(1,3,4,5)，尽管我怀疑这有什么区别。

我只是使用二分搜索还是有一个方法?在我看来，对于这样一个简单的任务，你几乎无法打败二分搜索——也许你可以把它减半。

获取字典中最大的键

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

myDictionary.Keys.Max();

二进制搜索将是最快的，但对普通字典不起作用，因为键没有按任何特定顺序存储。@Minitech的答案，使用Linq Max()，如果你使用普通字典，是最简单的。

如果这是一个必须多次执行的操作，您可以考虑转移到基于键对条目进行排序的SortedDictionary<TKey, TValue>。

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

编辑:这个可能比普通字典慢。我想应该提一下。这是因为字典中的条目以不同的方式存储(红/黑树vs哈希桶/哈希表)

是SortedDictionary比正常Dictionary变快的点。然而，这个数字可能会达到100万件左右，但这只是一个猜测。事实证明，在这么多的项目上，它的速度要快10倍(但我们说的是百分之一秒，所以真的很重要吗?)对于100,000个项目，它在x64版本上是相等的。考虑到向字典中添加项的额外开销，可能不值得这样做。此外，我通过重写比较器来"欺骗"一点，所以它会以相反的顺序排序，所以我实际上是在做dict.Keys.First()而不是最后一个来获得最大的项目。

SortedDictionary实际上是用于需要按顺序遍历所有键值对的情况。我认为@SimonMourier的答案可能是最好的。

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

    public class RememberMaxDictionary<K, V> : IDictionary<K, V> where K: IComparable<K>
    {
        private Dictionary<K, V> _inner;
        public RememberMaxDictionary()
        {
            _inner = new Dictionary<K, V>();
        }
        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...
相关文章：