Java集合(二)-Set集合


Set集合

Set集合和Collection基本相同,没有提供额外的方法,主要是行为上的不同,Set不允许包含重复元素,否则add()方法会返回false。接下来将主要介绍四种Set类,HashSetTreeSetLinkedHashSetEnumSet四种。

HashSet类

HashSet使用hash算法来储存集合中的元素,具有很好的查找和存取性能,它的特点如下:

  1. 不能保证元素的顺序,可能变化
  2. HashSet不是同步的,如果多个线程同时访问并修改一个HashSet,则必须保证其同步。
  3. 集合的元素可以是null

当向HashSet集合中存入一个元素时,HashSet会调用对象的hashCode()方法来得到该对象的hashCode值,然后根据该hashCode值决定该对象在HashSet中的位置。但是如果两个元素通过equals()方法返回true,而它们的hahCode()方法返回值不相等,HashSet将会把他们储存在不同的位置,依然可以添加成功。也就是说,HashSet集合判断元素相等的标准是通过equals方法比较相等,并且两个对象的hashCode值一样。

Class A{
    public boolean equals(Object obj){
        return true;
    }
}
Class B{
    public int hashCode(){
        return 1;
    }
}
Class C{
    public int hashCode(){
        return 2;
    }
    public boolean equals(Object obj){
        return true;
    }
}
public Class HashSet{
    public static void main(String[] args){
        HashSet books = new HashSet();
        books.add(new A());
        books.add(new A());
        books.add(new B());
        books.add(new B());
        books.add(new C());
        books.add(new C());
    }
}//添加两A,B,C对象
[B@1 ,B@1 ,C@2 ,A@54d ,A@8773f2]

从上面看出,即使A对象equals方法返回true,依然被当作两个对象;即使两个B对象hashCode方法返回值一样,但HashSet集合储存了两个hash值一样的对象。如果equals返回true,但是会放在不同的地方,不太好。如果hash值一样,但equals返回的false也麻烦了,集合会尝试保存把对象保存在同一个位置,并采用链式结构来保存多个对象,这样会导致利用哈希值查找的时候,性能下降。

所以总结一句:如果需要把对象保存到HashSet集合中去,重写类的equalshashCode方法,保证equals返回true时,hashCode返回值一样。

HashSet中每个能储存元素的位置通常称为桶(bucket),如果有多个元素的哈希值相同,但它们通过equals方法返回false,就需要在一个桶内放多个元素,然而这样会导致性能下降。

重写hashCode方法步骤
  1. 把对象内的每个参与equals方法比较的实例变量计算处一个int类型的哈希值
实例变量类型 计算方式 实例变量类型 计算方式
boolean hashCode = (f ? 0 : 1) float hashCode = Float.floatToIntBits(f)
整型byte、char、short、int hashCode = (int)f double long L = Double.doubleToLongBits(f);
hashCode = (int)(L^(L>>>32));
Long hashCode = (int)(f^(f>>>32)); 引用 hashCode = f.hashCode();

2.用第一步计算出的多个哈希值组合计算出一个哈希值返回,例如:

return f1.hashCode() + (int)f2;//f1,f2为实例变量

为避免直接相加产生的偶然,可以为各实例变量的哈希值乘以任意质数后再相加。但还有一点需要了解的是,这样并不能完全保证之后就不会产生两个相同的对象,向HashSet中添加可变对象后,后面修改了可变对象的实例变量,可能导致它和集合中其他元素相同,甚至不能正确访问(储存在不同位置,hash值不一样)。

LinkedHashSet

HashSet还有一个子类LinkedHashSet,同样也是根据元素的hashCode值来决定元素的储存位置,不同的是它使用链表维护元素的次序,这样可以以插入顺序保存元素。LinkedHashSet需要链表维护次序,所以性能略低于HashSet,但优势在于遍历集合内元素上。另外注意一点,它还是Set,所以依然不允许元素重复!

LinkedHashSet names = new LinkedHashSet();
names.add("James");
names.add("Jodan");
System.out.println(names);
//James,Jodan

TreeSet(SortedSet的实现类)

既然是实现类,那SortedSet就是TreeSet的接口了,顾名思义,TreeSet可以让元素处于一定次序状态。与HashSet相比,TreeSet额外提供了如下方法:

  • Comparator comparator():如果TreeSet采用定制排序,则返回定制排序所使用的Comparator,如果采用自然排序,则返回null
  • Object first():返回第一个元素
  • Object last():返回最后一个元素
  • Object lower(Object e):返回处于指定元素(任意元素,不需要在集合中)之前的元素
  • Object higner(Object e):返回处于指定元素之后(更大的元素)的元素
  • SortedSet subSet(Object e1,Object e2):返回从e1到e2的子集合(不包含e1,e2)
  • SortedSet headSet(Object max):返回子集合,元素都小于max
  • SortedSet tailSet(Object min):返回子集合,元素大于等于min

综上,大概就是提供了访问第一个、最后一个、前一个、后一个元素的方法,并提供了三个截取子集合的方法。与此同时,TreeSet采用红黑树的数据结构来储存数据,默认情况下使用自然排序。它的排序规则有以下两种:

1.自然排序

TreeSet调用集合元素的compareTo(Object obj)方法来比较元素之间的大小关系,然后将集合元素按升序排列,这种就是自然排序。Java提供了Comparable接口,该接口内定义了一个compareTo(Object o)方法,方法返回一个整数。实现接口就必须实现该方法。当一个对象之间进行比较时,例如:obj1.compareTo(obj2),如果返回0,则表明这两个对象相等;如果返回一个正整数,则obj1大于obj2;如果返回一个负整数,则obj1小于obj2。

下面提供了实现Comparable接口的类,并提供了比较大小的标准。

  • BigDecimal、BigInteger以及所有数值类型对应的包装类:按数值大小比较
  • Character:按字符的Unicode进行比较
  • Boolean:true对应的包装类实例大于false对应的包装类实例
  • String:按字符串中字符的Unicode值比较
  • Date、Time:后面的时间、日期比前面的日期大

所以TreeSet会自动地给集合中地大小进行排序,但前提是对象实现了Comparable接口,否则将不可行。还有一点需要说明,大部分类在实现compareTo(Object o)方法时,都需要将被比较对象强制类型转换成相同类型,否则无法比较。然而当添加一个对象到集合中去时,集合会调用对象compareTo()方法与集合中的其他元素进行比较,比较要是同一类的对象。

如果向TreeSet添加对象是自定义对象,则可以向TreeSet中添加多种类型对象,但这并不表明这是最好的选择,也不推荐这样干,当取出对象时,元素之间会报ClassCastException异常。

当把一个对象加入集合中时,集合调用对象的compareTo方法与容器的其他对象比较,然后根据红黑树结构找到它的储存位置。如果两个对象通过compareTo(Object obj)方法比较相等,新对象将无法添加到集合中。总之,如果要不报错,TreeSet中只能添加同一种类型的对象。

对于TreeSet集合而言,判断两个对象相等的唯一标准是:两个对象通过compareTo(Object obj)方法比较相等,返回0,则相等。所以它的添加元素的规则和HashSet一样,假如通过equals方法比较相等,则它们记为同一对象,因此通过compareTo()方法返回0,只能存放一个对象,集合不会让第二个元素进去。同样,如果添加了可变对象,并且还修改了对象的实例变量,将导致集合中对象的顺序变化,然而TreeSet不会调整顺序(甚至会导致删除对象失败,TreeSet性能降低)。

2.定制排序

实现定制排序则可以通过Comparator接口,该接口内包含一个int compare(T o1,T o2)方法,用于比较o1、o2的大小,如果返回正整数,则o1>o2;若返回0,则o1=o2;若返回负整数,则o1<o2。但依然不可以添加不同类型的对象。

在实现定制排序之前,需要提供一个Comparator对象与TreeSet集合关联,由该对象对集合元素进行排序。

class M{
    int age;
    public M(int age){
        this.age = age;
    }
    public String toString(){
        return "M(age:" + age +" )";
    }
}
public class Test{
    public static void main(String[] args){//Lambda表达式
        TreeSet t = new TreeSet((o1,o2)->{//o1,02这里没有具体类型
            M m1 = (M)o1;
            M m2 = (M)o2;
            return m1.age>m2.age ? -1:m1.age<m2.age ? 1:0;
        });
        t.add(new M(5));
        t.add(new M(-3));
        t.add(new M(9));
        System.out.println(t);
    }//Lambda表达式实现了Comparator类型的对象
}//输出[M(age:9),M(age:5),M(age:-3)]降序排列

EnumSet类

专门为枚举类设计的集合类,EnumSet中所有元素必须是指定枚举类型的枚举值。值得一提的是EnumSet集合也是有序的,但它以枚举值在类中的定义顺序来决定集合元素的顺序。EnumSet在内部以位向量的形式储存元素,因此占用内存非常小,运行效率很好,特别是在批量操作时。

EnumSet不允许加入null元素,如果试图插入将会抛出NullPointerException异常。而如果只是判断集合中是否有null元素或删除它,将不会抛出异常,删除的话会返回false,因为没有null元素。

EnumSet集合没有给出任何构造器来创建对象,但还是提供了一些方法去创建的对象的。如下:

  • EnumSet allOf(Class elementType):创建一个包含指定枚举类所有枚举值的集合
  • EnumSet complementOf(EnumSet s):创建一个其元素类型与指定EnumSet里元素类型相同的EnumSet集合,新集合包含原集合不包含的、此枚举类剩下的枚举值
  • EnumSet copyOf(Collection c):使用一个普通集合来创建EnumSet
  • EnumSet copyOf(EnumSet e):创建一个与指定EnumSet具有相同类型、相同元素的EnumSet集合
  • EnumSet noneOf(Class elementType):创建一个元素类型为指定枚举类型的空EnumSet
  • EnumSet range(E from ,E to):创建一个包含从from枚举值到to枚举值范围内枚举值的EnumSet集合
  • EnumSet of(E first…E rest ):创建一个包含一个或多个枚举值的EnumSet集合(传入的枚举值必须属于同一个枚举类)
enum Colors{WHITE,YELLOW,RED,GREEN}
public class Test{
    public static void main(String[] args){
        EnumSet e1 = EnumSet.allOf(Colors.class);
        EnumSet e2 = EnumSet.noneOf(Colors.class);//这里为[]
        e2.add(Colors.WHITE);//这里为[WHITE]
        EnumSet e3 = EnumSet.of(Colors.RED,Colors.GREEN);
        System.out.println(e3);//输出[RED,GREEN]
        EnumSet e4 = EnumSet.range(Colors.YELLOW,Colors.GREEN);
        System.out.println(e4);
        //[YELLOW,RED,GREEN]
        EnumSet e5 = EnumSet.complementOf(e4);
        //这里为[WHITE]
    }
}

此外还可以复制另一个EnumSet集合中的元素来创建新集合,或者复制一个Collection集合元素来创建新的EnumSet集合。当复制Collection集合元素创建时,要求元素都来自同一个枚举类,否则抛出ClassCastException异常。

Collection c = new HashSet();
c.clear();
c.add(Colors.RED);
c.add(Colors.YELLOW);
EnumSet e = EnumSet.copyOf(c);
System.out.println(e);
//[RED,YELLOW]

各Set实现类的性能分析

HashSet总是比TreeSet的性能好,主要体现在添加、查询元素上,因为TreeSet采用了红黑树来维护集合的次序。而HashSet的子类LinkedHashSet对插入、查询操作比父类要稍慢些,这是由于采用了链表维护的缘故,造成了额外开销。但这并不影响LinkedHashSet发挥威力,然而这恰恰是它的优势,在遍历等批量操作上,LinkedHashSet更快。

EnumSet是所有Set类中性能最好的,缺点是只能保存一个枚举类的枚举值。总的说,Set的这三个实现类都是线程不安全的,即当有多个线程访问时,如果修改了Set集合,将不能同步,必须手动保证同步。方法是在创建Set集合时,通过Collections工具类的sychronizedXxx()方法来包装该集合(之后会提到)。


文章作者: 流浪舟
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 流浪舟 !
评论
 上一篇
Java集合(三)-List和Queue集合 Java集合(三)-List和Queue集合
公众号: 菜鸡干Java 欢迎关注 Java集合—List集合与Set集合不同,List集合是有序,可重复的,而且默认以添加顺序设置索引。List子接口是继承了Collection接口,则可以使用其中的方法。 特别的是List增加了根
2020-10-09
下一篇 
Java集合类-开篇 Java集合类-开篇
公众号:菜鸡干Java 站点:https://www.maliaoblog.cn 集合介绍Java集合类是一种特别的工具类,可以储存对象,并实现了常用的数据结构,另外还能保存具有映射关系的关联数组。集合大致分为Set,List,Queu
2020-09-29
  目录