java - Hashmap比较运行时间

Question

我正在比较 2 个 HashMap，我试图找出比较循环的时间复杂度。 代码如下:

//map1 is a HashMap and contains m elements and keys
//map2 is a HashMap and contains n elements and keys 
List<myObject> myList = new ArrayList<myObject>()  
for (String key: map1.keySet()){ 
    if(!map2.containsKey(key)){
        myList.add(map.get(key));
   }
 }

第一个 for 循环将是 O(m)。我在其他一些论坛上发现 containsKey() 需要 lg(n) 时间。有人可以确认吗？我在 JavaDocs 中找不到它。
如果是这样，那么总时间复杂度将是 O(mlg{n})。
此外，关于如何以更好的方式进行这种比较的任何想法都会有所帮助。

Answer 1

取决于您的哈希码算法和冲突。

使用完美的哈希码，理论上映射查找是 O(1)，常数时间，如果有冲突，它可能高达 O(n)。 所以在你的情况下，如果你有好的散列算法，它将是 O(m)。

如果你看wiki ，您可以对这个概念有更多的了解。您也可以查看 map 源代码。