TreeMap values()方法和keySet()方法的时间复杂性

Question

我试图找到在TreeMap数据结构中实现的方法values((和keySet((的时间复杂性。

有人能告诉我这些方法的时间复杂性是多少吗？

非常感谢。

Tom

    public class SuperStruct<K,V> 
{
    private Map<K,V> mInternalKeyToValueMap;//all the keys and their values 
    public SuperStruct(){
            mInternalKeyToValueMap = new TreeMap<K,V>();
    }
    public Collection<V> values() {     
            return mInternalKeyToValueMap.values();
        }
    public Collection<K> keySet() {
            return mInternalKeyToValueMap.keySet();
        }
    }

Answer 1

我希望两者都是惰性结构，都是由实际映射支持的视图，所以创建它们将是O(1(。在整个集合中迭代将是O(n((就像在映射本身中迭代一样(。

但这只是基于keySet()和values()方法的契约的合理假设(特别是说返回的结构必须反映底层映射中的变化，反之亦然(，不能保证我知道它们会以这种方式表现。

(尽管记录在案，Oracle的实现正是这样做的，而且以任何其他方式实现它都会复杂得多。然而，这仍然不是铁板一块的保证。(

Answer 2

keySet几乎肯定会使用Collections.newSetFromMap(this(，因为这是一个非常有效的方法，所以O(1)。

通过一个简单的适配器从映射的entrySet创建Collection<V>应该很简单，所以我建议它与entrySet具有相同的复杂性，可以是O(1)或O(n)，但很可能是O(1)。一些浏览GrepCode上的源代码的人建议O(1)——它只是在创建一个新对象(如果必要的话(，而不是在增长一个结构。