首页 / JAVA / 在Java中使用HashSets时,方法retainAll的时间和空间复杂度是多少？

在Java中使用HashSets时,方法retainAll的时间和空间复杂度是多少？

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了在Java中使用HashSets时,方法retainAll的时间和空间复杂度是多少？，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1471字，纯文字阅读大概需要3分钟。

内容图文

例如,在下面的代码中：

public int commonTwo(String[] a, String[] b)
{
    Set common = new HashSet<String>(Arrays.asList(a));
    common.retainAll(new HashSet<String>(Arrays.asList(b)));
    return common.size();
}

解决方法:

让我们在the code处进行细读.方法retainAll继承自AbstractCollection,并且(至少在OpenJDK中)如下所示：

public boolean retainAll(Collection<?> c) {
    boolean modified = false;
    Iterator<E> it = iterator();
    while (it.hasNext()) {
        if (!c.contains(it.next())) {
            it.remove();
            modified = true;
        }
    }
    return modified;
}

这里有一个很重要的注意事项,我们遍历this.iterator()并调用c.contains.所以时间复杂度是n次调用c.contains,其中n = this.size(),最多n次调用it.remove().

这个重要的是在另一个Collection上调用contains方法,因此复杂性取决于其他Collection包含的复杂性.

所以,同时：

Set<String> common = new HashSet<>(Arrays.asList(a));
common.retainAll(new HashSet<>(Arrays.asList(b)));

将是O(a.length),因为HashSet.contains和HashSet.remove都是O(1)(摊销).

如果你打电话

common.retainAll(Arrays.asList(b));

然后由于Arrays.ArrayList上的O(n)包含,这将变为O(a.length * b.length) – 即通过花费O(n)将数组复制到HashSet,您实际上更快地调用retainAll.

就空间复杂性而言,retainAll不需要额外的空间(超出Iterator),但是你的调用实际上是非常昂贵的,因为你分配了两个新的HashSet实现,它们实际上是完全成熟的HashMap.

还可以注意到另外两件事：

>没有理由从 – 中的元素中分配HashSet – 也可以使用从中间删除O(1)的更便宜的集合,例如LinkedList. (内存更便宜,也可以构建时间 – 不构建哈希表)
>在创建新的集合实例时,您的修改将丢失,并且仅返回b.size().

内容总结

以上是互联网集市为您收集整理的在Java中使用HashSets时,方法retainAll的时间和空间复杂度是多少？全部内容，希望文章能够帮你解决在Java中使用HashSets时,方法retainAll的时间和空间复杂度是多少？所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/708642.html

来源：【匿名】