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源代码。