java - 获取 TreeMap 中最高键的更好方法？

Question

方式一:

TreeMap<Integer, String> map = new TreeMap<Integer, String>();
int highestKey = map.lastKey();

来自 JDK 的 TreeMap.lastKey() 源代码:

 Entry<K,V> p = root;
        if (p != null)
            while (p.right != null)
                p = p.right;
        return p;

方式2:

TreeMap<Integer, String> map = new TreeMap<Integer, String>();
Object[] keys = map.keySet().toArray();
int highestKey = keys[keys.length - 1]

当您查看 lastKey() 的实现时，我们会发现我们有一个 while 循环。我认为这个的时间复杂度是 O(n)。

这让我觉得 Way2 在时间复杂度方面是更好或更有效的实现方式。我的理解正确吗？哪种使用方式更好。

Answer 1

我认为您弄错了，lastKey() 的 JDK 实现具有 O(logn) 而不是 O(n) 的时间复杂度，并且没有额外的空间复杂度。它是一棵红黑树(即平衡树)。

在提到的方式 2 中，您使用 keyset().toArray() 获取所有 key ，这是 O(n)，并将它们存储在一个object [] 也有 O(n) 的额外空间复杂度。

通过这些，JDK 实现具有更好的时间和空间复杂度。