hashmap包含键的复杂度

我写了一个方法来查找列表中的重复项。它工作正常，但我担心使用 containsKey 的复杂性。当我们使用 containsKey 时，我们必须为每个键计算一个哈希函数，然后将每个键与我们的搜索项进行比较，对吗？那么复杂度不是 O(n) 吗？

这是函数：

public void findDup(List<String> list){

    HashMap<String,Integer> map = new HashMap<>();
    int pos=0;
    for(String s: list){
        if(map.containsKey(s)){
            Log.v("myapp","duplicate found:"+s);
        }
        else
            map.put(s,pos);
        pos++;
    }
}

为了称呼它，我这样做：

List<String>list=new ArrayList<>();

    for(int i=0;i<12;i++)
        list.add(i+"");

    //these numbers should surely be duplicates
    list.add("3");list.add("6");

    findDup(list);

//输出显然是3和6。

更新：我重写了该函数，只使用一组更有意义的：

public void findDup(List<Integer> list){

        HashSet<Integer> set = new HashSet<>();
        for(Integer num: list){
            if(!set.add(num)){
                Log.v("myapp","duplicate found:"+num);
            }

        }
    }

它在 Javadoc 中指定为O(1).

复杂度你的算法因此O(N).

但即使如此without the containsKey()调用，这实际上是没有必要的。您所要做的就是测试是否put()返回一个非空值，表示重复。

当我们使用 containsKey 时，我们必须为每个键计算一个哈希函数，然后将每个键与我们的搜索项进行比较，对吗？

错误的。我们计算搜索键的哈希值并检查该存储桶是否被相等的键占用。

那么复杂度不是 O(n) 吗？

No.