Java HashSet的Removals()方法注意事项

2024-10-03 13:47:22

前言

我有一个集合，实际上是一个HashSet。我想从中删除一些item…其中许多item可能不存在。事实上，在我们的测试用例中，“removals”集合中的所有项都不在原始集合中。这听起来——实际上也是——非常容易编码。毕竟，我们已经准备好了。removeAll来帮助我们，对吗？

让我们把它变成一个小测试。我们在命令行上指定“source”set的大小和“removals”集合的大小，并构建它们。source set合只包含非负整数；删除集仅包含负整数。我们使用系统测量删除所有元素所需的时间System.currentTimeMillis()，它不是世界上最精确的秒表，但在这种情况下就足够了，正如您将看到的那样。

代码如下：

import java.util.*;
public class Test
{
    public static void main(String[] args)
    {
        int sourceSize = Integer.parseInt(args[0]);
        int <a href="https://javakk.com/tag/removals" rel="external nofollow"  rel="external nofollow"  target="_blank" >removals</a>Size = Integer.parseInt(args[1]);

        Set<Integer> source = new HashSet<Integer>();
        Collection<Integer> <a href="https://javakk.com/tag/removals" rel="external nofollow"  rel="external nofollow"  target="_blank" >removals</a> = new ArrayList<Integer>();

        for (int i = 0; i < sourceSize; i++)
        {
            source.add(i);
        }
        for (int i = 1; i <= removalsSize; i++)
        {
            removals.add(-i);
        }

        long start = System.currentTimeMillis();
        source.removeAll(removals);
        long end = System.currentTimeMillis();
        System.out.println("Time taken: " + (end – start) + "ms");
    }
}

首先，让我们给它一个简单的工作：一个包含100个items的source set，以及要删除的100个items：

c:UsersJonTest>java Test 100 100
Time taken: 1ms

好吧，所以我们没想到会很慢……很明显，我们可以把速度提高一点。一百万件items和300000件items的来源如何？

c:UsersJonTest>java Test 1000000 300000
Time taken: 38ms

嗯，看起来还是挺快的。现在我觉得我有点残忍，要求它做所有这些移除。让我们让它变得更简单一些–300000个source items和300000个删除：

c:UsersJonTest>java Test 300000 300000
Time taken: 178131ms

快三分钟了？哎呀！当然，从一个较小的集合中删除items应该比我们在38ms内管理的集合更容易？嗯，最终这一切都是有道理的。HashSet扩展了AbstractSet，它在removeAll方法的文档中包含此代码段：

https://docs.oracle.com/javase/6/docs/api/java/util/AbstractSet.html

此实现通过调用每个集合上的size方法来确定此集合和指定集合中的较小者。如果此集合的元素较少，则实现将迭代此集合，依次检查迭代器返回的每个元素，以查看它是否包含在指定的集合中。如果它是这样包含的，则使用迭代器的remove方法将其从该集中移除。如果指定集合的元素较少，那么实现将迭代指定集合，使用该集合的remove方法从该集合中删除迭代器返回的每个元素。

从表面上看，这听起来很合理——遍历较小的集合，检查较大集合中是否存在。然而，这就是抽象存在漏洞的地方。仅仅因为我们可以要求一个item出现在一个大的集合中，并不意味着它会很快出现。在我们的例子中，集合的大小是相同的，但是检查哈希集中是否存在项是O（1），而在ArrayList中检查是O（N）…而每个集合的迭代成本是相同的。基本上，通过选择遍历HashSet并检查ArrayList中是否存在，我们得到了一个O（M*N）解决方案，而不是O（N）解决方案。removeAll方法基于在这种情况下无效的假设进行“优化”。

那么如何解决？

有两种简单的方法可以解决这个问题。首先，只需更改要从中删除的集合的类型。只需将ArrayList<Integer>更改为HashSet<Integer>，我们就可以回到34ms的范围。我们甚至不需要更改声明的删除类型。

第二种方法是更改我们使用的API：如果我们知道要迭代删除并在源代码中执行查找，那么很容易做到：

for (Integer value : removals)
{
    source.remove(value);
}

事实上，在我的机器上，它的性能略优于removeAll–它不需要在每次迭代时检查remove的返回值，removeAll这样做是为了返回是否删除了任何项。以上运行时间约为28ms。（我已经用相当大的数据集对其进行了测试，它确实比双哈希集方法更快。）

然而，这两种方法都需要在源代码中添加注释，以解释为什么我们没有使用最明显的代码（列表和删除）。我不能抱怨这里的文档——它确切地说明了它将做什么。在你遇到这样的问题之前，你根本不需要担心它。

那么，实现应该做什么呢？可以说，它真的需要知道它所处理的每一个集合中什么是便宜的。在决定策略之前探索性能特征的想法对于清理我们喜欢在Java集合之类的框架中考虑的抽象是完全不可取的……但在这种情况下，这可能是一个好主意。

到此这篇关于Java HashSet的Removals()方法注意事项的文章就介绍到这了,更多相关Java HashSet 内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

JAVA HashSet和TreeSet 保证存入元素不会重复的操作

Set是一种数据集合.它与List同样继承与Collection接口. 它与Collection接口中的方法基本一致,并没有对Collection接口进行功能进行功能上的扩充,只是比Collection接口更严格了.与List不同的是,Set中的元素是无无需的,并且都以某种规则保证存入的元素不会出现重复. 它的特点也就是: 1. 元素不会出现重复. 2. 元素是无序的.(存取无序) 3. 元素可以为空. 每种类型的Set所使用的避免元素重复的规则都是不同的,今天我们主要还是看HashSet和Tr
Java多线程高并发中解决ArrayList与HashSet和HashMap不安全的方案

1.ArrayList的线程不安全解决方案将main方法的第一行注释打开,多执行几次,会看到如下图这样的异常信息:
Java基础之详解HashSet的使用方法

Java HashSet HashSet 基于 HashMap 来实现的,是一个不允许有重复元素的集合. HashSet 允许有 null 值. HashSet 是无序的,即不会记录插入的顺序. HashSet 不是线程安全的, 如果多个线程尝试同时修改 HashSet,则最终结果是不确定的. 您必须在多线程访问时显式同步对 HashSet 的并发访问. HashSet 实现了 Set 接口. HashSet 中的元素实际上是对象,一些常见的基本类型可以使用它的包装类. 添加元素 HashSet
简单的理解java集合中的HashSet和HashTree几个重写方法

Java中的set是无序的,但是是不可重复的 HashSet底层是哈希表,通过调用hashcode和equals方法实现去重当我们HashSet里面存的是字符串时,就能默认去重了,因为String已经重写了hashcode和euqals方法 public static void main(String[] args) { HashSet<String> set = new HashSet(); set.add("java"); set.add("c")
Java 详解Collection集合之ArrayList和HashSet

目录 Collection List ArrayList Set HashSet ArrayList和HashSet的区别泛型 Collection Collection接口被List接口和Set接口继承本章只介绍常用的集合 List ArrayList是List接口的实现类 ArrayList ArrayList 类是一个可以动态修改的数组,与普通数组的区别就是它是没有固定大小的限制,我们可以添加或删除元素. ArrayList 继承了 AbstractList ,并实现了 List 接口
Java HashSet(散列集),HashMap(散列映射)的简单介绍

简介本篇将简单讲解Java集合框架中的HashSet与HashMap. 散列集(HashSet) 快速入门底层原理:动态数组加单向链表或红黑树.JDK 1.8之后,当链表长度超过阈值8时,链表将转换为红黑树. 查阅HashSet的源码,可以看到HashSet的底层是HashMap,HashSet相当于只用了HashMap键Key的部分,当需要进行添加元素操作时,其值Value始终为常量PRESENT = new Object().以下为HashSet的代码片段: private transi
实例讲解Java HashSet

HashSet 基于 HashMap 来实现的,是一个不允许有重复元素的集合. HashSet 允许有 null 值. HashSet 是无序的,即不会记录插入的顺序. HashSet 不是线程安全的, 如果多个线程尝试同时修改 HashSet,则最终结果是不确定的. 您必须在多线程访问时显式同步对 HashSet 的并发访问. HashSet 实现来 Set 接口. HashSet 中的元素实际上是对象,一些常见的基本类型可以使用它的包装类. 基本类型对应的包装类表如下: 基本类型引用类型
java中HashSet的特点及实例用法

1.HashSet和TreeSet区别 HashSet底层使用Hash表. 确保元素唯一性的原理:判断元素的hashCode值是否相同.如果是一样的话,会继续判断元素的equals方法是否是true. TreeSet底层采用红黑树. 确保元素的唯一性是通过Comparable或Comparator接口实现的. 2.HashSet和HashMap区别事实上,HashSet的底层实现还是HashMap,只是它只使用了Key,具体如下: (1)在HashSet的add方法的底层,使用HashMap的
Java HashSet集合存储遍历学生对象代码实例

由于Set集合是不存储重复元素的,所以在做此案例时,如果我正常添加一个重复元素是什么结果呢? public class HashSetDemo { public static void main(String[] args) { //创建HashSet集合对象 HashSet<Student> hashSet = new HashSet<Student>(); //创建学生对象 Student s1 = new Student("爱学习", 21); Stude
Java HashSet的Removals()方法注意事项

目录前言那么如何解决? 前言我有一个集合,实际上是一个HashSet.我想从中删除一些item…其中许多item可能不存在.事实上,在我们的测试用例中,“removals”集合中的所有项都不在原始集合中.这听起来——实际上也是——非常容易编码.毕竟,我们已经准备好了.removeAll来帮助我们,对吗? 让我们把它变成一个小测试.我们在命令行上指定“source”set的大小和“removals”集合的大小,并构建它们.source set合只包含非负整数:删除集仅包含负整数.我们使用系统
Java HashSet添加遍历元素源码分析

目录 HashSet 类图 HashSet 简单说明 HashSet 底层机制说明模拟数组+链表的结构 HashSet 添加元素底层机制 HashSet 添加元素的底层实现 HashSet 扩容机制 HashSet 添加元素源码 HashSet 遍历元素底层机制 HashSet 遍历元素底层机制 HashSet 遍历元素源码 HashSet 类图 HashSet 简单说明 1.HashSet 实现了 Set 接口 2.HashSet 底层实际上是由 HashMap 实现的 public Has
java volatile关键字使用方法及注意事项

java volatile关键字使用方法及注意事项什么是volatile关键字 volatile 关键字在多线程程序中起着很重要的作用.当多个线程操作同一个变量时,每个线程将拥有对那个变量的本地缓存拷贝,因此,当某一个线程修改了这个变量的值时,实际上修改的是它本地缓存中的变量值,而不是主内存中的变量值,操作这个变量的其他线程并不知道这个变量的值被改变了.为了避免这种情况,我们可以用 valatile 关键字声明这个变量,用 valatile 声明了这个变量之后,变量将不在本地缓存中保存,而在主
Java list.remove( )方法注意事项

这篇文章给大家简单介绍了Java list.remove( )方法注意事项,具体内容如下: List<Integer> integerList = new ArrayList<>(); 当我们要移除某个Item的时候 remove(int position):移除某个位置的Item remove(object object):移除某个对象那么remove(12)到底是移除第12的item,还是移除内容为12的Item. 那就要看12到底是int类型还是Integer类型,如果是i
java中重写equals()方法的同时要重写hashcode()方法(详解)

object对象中的 public boolean equals(Object obj),对于任何非空引用值 x 和 y,当且仅当 x 和 y 引用同一个对象时,此方法才返回 true: 注意:当此方法被重写时,通常有必要重写 hashCode 方法,以维护 hashCode 方法的常规协定,该协定声明相等对象必须具有相等的哈希码.如下: (1) 当obj1.equals(obj2)为true时,obj1.hashCode() == obj2.hashCode()必须为true (2) 当obj
浅谈Java中的hashcode方法（推荐）

哈希表这个数据结构想必大多数人都不陌生,而且在很多地方都会利用到hash表来提高查找效率.在Java的Object类中有一个方法: public native int hashCode(); 根据这个方法的声明可知,该方法返回一个int类型的数值,并且是本地方法,因此在Object类中并没有给出具体的实现. 为何Object类需要这样一个方法?它有什么作用呢?今天我们就来具体探讨一下hashCode方法. 一.hashCode方法的作用对于包含容器类型的程序设计语言来说,基本上都会涉及到has
Java枚举的使用方法详解

Java枚举的使用方法详解前言你代码中的flag和status,都应该用枚举来替代很多人都说,枚举在实际开发中很少用到,甚至就没用到.因为,他们的代码往往是这样子的: public class Constant { /* * 以下几个变量表示英雄的状态 */ public final static int STATUS_WALKING = 0;//走 public final static int STATUS_RUNNINGING = 1;//跑 public final stati
Java中Equals使用方法汇总

这篇总结的形式是提出个问题,然后给出问题的答案.这是目前学习知识的一种尝试,可以让学习更有目的. Q1.什么时候应当重写对象的equals方法? 答:一般在我们需要进行值比较的时候,是需要重写对象的equals方法的.而例外情况在<effective java>的第7条"在改写equals的时候请遵守通用约定"中清楚描述了. 我们知道,在Java中,每个对象都继承于Object.如果不重写,则默认的equals代码如下所示: public boolean euqals(Ob
Java使用volatile关键字的注意事项

Volatile 变量具有 synchronized 的可见性特性,但是不具备原子特性.这就是说线程能够自动发现 volatile 变量的最新值.Volatile 变量可用于提供线程安全,但是只能应用于非常有限的一组用例:多个变量之间或者某个变量的当前值与修改后值之间没有约束.因此,单独使用 volatile 还不足以实现计数器.互斥锁或任何具有与多个变量相关的不变式. volatile关键字是Java中的一种稍弱的同步机制,为什么称之为弱机制. 在理解这个之前,我们先来看看java在进行同步时

Java HashSet的Removals()方法注意事项

目录

前言

那么如何解决？

相关推荐

随机推荐