在字典中获取最大的键

Question

我有一个键为整数的字典，我想获取最大的键。我没有追踪过这些键，所以它们可能是连续的（例如1,2,3,4,5,6），但可能会跳过一些（1,3,4,5）。不过我认为这并不会产生任何影响。

我应该只使用二分查找还是还有其他方法？就我所看到的，对于这样一个简单的任务，你几乎无法打败二分查找 - 也许你可以把它减半。

- s5s

---

字典是无序的，因此二分查找对你没有什么帮助。 - Austin Salonen

@AustinSalonen Dictionary<K, V> 没有排序，但值得一提的是，有一些有序实现的 IDictionary<K, V> 存在。 - phoog

Answer 1

如果您有可用的LINQ，您应该能够执行以下操作：

myDictionary.Keys.Max();

- Ry-

---

对于任何想要使用此代码的人，您需要确保包含linq扩展方法Imports System.Linq并在.net 3.5+中编译 - 然后就可以愉快地工作了 :) - HeavenCore

这是O(n)还是O(1)的顺序？ - Pixel_95

@Pixel_95：O(n)。如果要达到O(1)，你可以在字典发生变化时跟踪最大值，就像Simon Mourier的回答中所示。 - Ry-

Answer 2

如果您使用的是普通字典，二分查找可能是最快的，但无法起作用，因为键不以任何特定顺序存储。如果您正在使用普通字典，则 @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

编辑：这个方法可能比一个普通的字典要慢。我想提一下这点应该是好的。那是因为字典中的条目以不同的方式存储（红黑树与哈希桶/哈希表）。

SortedDictionary比普通Dictionary更快确实存在一个点。然而，这可能需要大约100万项左右，但这只是猜测。当达到那么多项时，它大约快了10倍（但我们只谈论几百分之一秒，所以真的重要吗？）。在x64版本中，对于100000项，它差不多相等。考虑到添加项到字典的额外开销，这可能不值得。此外，我“作弊”了一下，通过重写比较器使其按相反的顺序排序，所以我实际上是使用dict.Keys.First()而不是最后一个来获取最大项。

SortedDictionary确实是为了按顺序迭代所有键值对而设计的。我认为@SimonMourier的回答可能是最好的。我保证这是最快的，开销最小。

- Christopher Currens

---

由于字典已排序，因此也可以使用以下代码：dict.Last().Key; - Jordan

Answer 3

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

    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...

- Simon Mourier

---

这是误导性的。你遗漏了MaxKey被减少的部分（假设希望删除一个条目，在大多数情况下是这样）。"Remove"方法在有效实现方面是非常棘手的。 - Dixtosa

@Dixtosa - 取决于您的上下文和需求。请自行撰写答案。 - Simon Mourier