java – hashmap containsKey复杂性
发布时间:2020-12-15 05:13:36 所属栏目:Java 来源:网络整理
导读:我有一个方法,我写了一个列表中的重复项.它工作正常,但我担心使用containsKey的复杂性.当我们使用containsKey时,我们必须为每个键计算一个哈希函数,然后将每个键与我们的搜索项进行比较,对吧?那复杂性不是O(n)吗? 这是功能: public void findDup(ListStri
我有一个方法,我写了一个列表中的重复项.它工作正常,但我担心使用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). 但即使没有containsKey()调用也是如此,这实际上是不必要的.您所要做的就是测试put()是否返回非空值,表示重复.
错误.我们计算搜索关键字的哈希值,并检查该桶是否被相等的密钥占用.
没有. (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |