hashmap containsKey复杂性

Question

我有一个方法,我写了一个列表中的重复项.它工作正常,但我担心使用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);
            }

        }
    }

Answer 1

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

在复杂的算法,因此为O(N).

不过,这将是,即使没有在containsKey()通话,这其实是不必要的.您所要做的就是测试是否put()返回非空值,表示重复.

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

错误.我们计算搜索关键字的哈希值,并检查该桶是否被相等的密钥占用.

那复杂性不是O(n)吗？

没有.