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();
        }
    }

- Tom

Answer 1

我认为这两者都应该是惰性结构，是由实际映射支持的视图，因此创建它们将是O(1)。遍历整个集合将是O(n)（就像遍历映射本身一样）。

但这只是基于keySet()和values()方法合同的合理推断（特别是规定返回的结构必须反映底层映射中的更改，反之亦然）。据我所知，没有任何保证它们会以这种方式运作。

（虽然为了记录，Oracle实现正是这样做的，并且以其他方式实现它将会更加复杂。但这仍然不是绝对的保证。）

- biziclop

Answer 2

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

通过一个简单的适配器，从地图的 entrySet 创建一个 Collection<V> 应该很简单，所以我建议它的复杂度与 entrySet 相同，可能是 O(1) 或 O(n)，但最有可能是 O(1)。在 GrepCode 浏览源代码似乎表明是 O(1) - 它只是创建一个新对象（如果必要），而不是增加一个结构。

- OldCurmudgeon