hashmap containsKey复杂性 [英] hashmap containsKey complexity

问题描述

我有一个方法可以在列表中找到重复项。它工作正常，但我担心使用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 +）; 
 
 //这些数字肯定是重复的
 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）。

$ b 您的算法的复杂性因此是 O（N）。

但是，即使没有 containsKey（）调用，这实际上是不必要的。您只需测试 put（）是否返回非空值，即表示重复。

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

错了。我们计算搜索关键字的哈希值，并检查该关键字是否被相同的关键字占据。

O（n）？

否。

I have a method i wrote to find the duplicates in a List. It works fine but im concerned about the complexity of using containsKey. When we use containsKey we have to compute a hash function for every key and then compare against each with our search item, right ? So wouldn't the complexity be O(n) ?

Here is the function:

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++;
    }
}

and to call it i do this:

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

//output will be 3 and 6 clearly.

update: i re-wrote the function to just use a set which makes more sense:

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

        }
    }

解决方案

It is specified in the Javadoc as O(1).

The complexity of your algorithm is therefore O(N).

But it would be that even without the containsKey() call, which is actually unnecessary. All you have to do is test whether put() returns a non-null value, which indicates a duplicate.

When we use containsKey we have to compute a hash function for every key and then compare against each with our search item, right?

Wrong. We compute the hash value of the search key and check if that bucket is occupied by an equal key.

So wouldn't the complexity be O(n) ?

No.

这篇关于hashmap containsKey复杂性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！