Set集合以及其实现类

2024-03-03 15:03:28

Set集合

Set集合类似于一个罐子，不记录添加元素的添加顺序，只是不允许包含重复元素（重复的判定在不同的实现类中可能有些区别。

HashSet类

HashSet具有很好的存取和查找性能。

HashSet有以下特点：

  • 不能保证元素的排列顺序，顺序可能与添加顺序不同，顺序也可能发生变化
  • HashSet 不是同步的，如果多个线程访问同一个HashSet ，并且有两个或两个以上的线程同时修改HashSet，则必须通过代码来保证同步
  • 集合元素值可以是null

Set像是一个罐子，记不住添加元素的顺序，所以查找的时候只能根据元素本身的属性去查找，因此Set不允许包含重复元素（这个重复的判定在不同的实现类中可能有细微的差别）

import java.util.HashSet;

class A{
    @Override
    public boolean equals(Object obj) {
        return true;
    }

    @Override
    public int hashCode() {
        return 1;
    }
}

class B{
    @Override
    public boolean equals(Object obj) {
        return true;
    }
}

class C{
    @Override
    public int hashCode() {
        return 2;
    }
}

public class HashSetTest {
    public static void main(String[] args) {

        HashSet s = new HashSet();
        System.out.println(s.add(null));
        System.out.println(s.add(null));
        s.forEach(ele-> System.out.println(ele));

        HashSet h = new HashSet();
        System.out.println(h.add(new A()));
        System.out.println(h.add(new A()));
        System.out.println(h.add(new B()));
        System.out.println(h.add(new B()));
        System.out.println(h.add(new C()));
        System.out.println(h.add(new C()));
        System.out.println(h);
    }
}

输出结果

true
false
null
true    //可以看出 HashSet集合判断两个元素相等的标准是：两个对象通过equals()方法比较得到true，并且hashCode()方法的返回值也相等 
false
true    //equals()返回true，但hashCode()返回值不相等时，会把它们保存在不同位置，但这违反了Set集合的“不包含重复元素”的规则
true
true    //equals()返回false，但hashCode()返回值相等时，会把它们用链式结构保存在一个位置，这样会导致在访问时性能下降
true    //（两个以上的元素具有相同的hashCode值）
[A@1, C@2, C@2, B@54a097cc, B@36f6e879]

基于hashCode()和equals()方法对于HashSet的重要性，对于HashSet中的对象，要遵循以下重写这两个方法的基本规则：

  • hashCode()每次运行的返回值应该一样
  • 当两个对象通过equals()方法返回true时，这两个对象的hashCode()方法应该返回相同的值
  • 对象中用作equals()方法比较标准的实例变量，都应该用于计算hashCode值

重写案例

import java.util.HashSet;
import java.util.Iterator;
import java.util.Objects;

class R{
    Double ooo;
    public R(double d){
        this.ooo = d;
    }

    @Override
    public String toString() {
        return "R{" +
                "ooo=" + ooo +
                '}';
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        R r = (R) o;
        return Objects.equals(ooo, r.ooo);
    }

    @Override
    public int hashCode() {
        long l = Double.doubleToLongBits(this.ooo);
        return (int)(1^(l>>>32));
    }
}
public class HashSetTest2 {
    public static void main(String[] args) {
        HashSet hs = new HashSet();
        hs.add(new R(1.1));
        // 整一个迭代器，把第一个元素取出来，没有进入迭代过程所以可以修改元素
        // （这也算不上修改吧，迭代过程中也能修改元素，
        // 但除了迭代器的remove()方法外不能用其他方法添加或删减元素）
        Iterator it = hs.iterator();
        R first = (R)it.next();
        first.ooo = 2.2;
        System.out.println(hs);
        // contains(Object o)方法：HashSet集合会先得到o的hashCode，然后到自己集合中对应的地方去找，
        // 找到后在通过equals()方法去比较，得到true后返回
        System.out.println(hs.contains(new R(1.1)));//因为equals返回了false
        System.out.println(hs.contains(new R(2.2)));//压根就没找到R(2.2)对应的hashCode
        /*
            由此可见，对于已经添加进去的对象，尽量不要修改关于该元素参与计算hashCode()和equals()的实例变量，
            否则，像上面的hs中的那一个对象，既无法通过contains(1.1)访问到，也无法通过contains(2.2)访问到
            这样会给集合操作这些元素带来很大麻烦
        */
    }
}

输出结果

[R{ooo=2.2}]
false
false

LinkedHashSet类

相对于HashSet的区别：

LinkedHashSet 是HashSet的子类，LinkedHashSet集合也是根据元素的hashCode值来决定元素的存储位置，但它同时维护元素存储的次序。
当遍历LinkedHashSet集合里的元素时，LinkedHashSet将会按元素的添加顺序来访问集合中的元素。

import java.util.LinkedHashSet;

public class LinkedHashSetTest {
    public static void main(String[] args) {
        LinkedHashSet ls = new LinkedHashSet();
        ls.add("a");
        ls.add("b");
        ls.add("c");
        ls.add("d");
        System.out.println(ls);
        ls.remove("c");
        System.out.println(ls);
    }
}
[a, b, c, d]
[a, b, d]

此实现使客户摆脱了HashSet提供的未指定的，通常混乱的排序，而不会导致与TreeSet相关的增加的成本。无论原始集的实现如何，都可以使用它来产生与原始集具有相同顺序的集合副本：

  void foo(Set s) {
         Set copy = new LinkedHashSet(s);
         ...
     }

性能

由于需要维护元素的插入顺序（其实是维护链式列表），LinkedHashSet相对于HashSet会增加开销，因此执行添加、删除等操作时性能会轻微下降，但当迭代的时候LinkedHashSet集合的迭代时间与集合的大小成正比，而HashSet集合的迭代时间与集合的容量成正比，因此LinkedHashSet的迭代性能要好一些。

当构造HashSet集合时，有两个参数，一个是初始化容量（默认是16），一个是负载因子（默认值是0.75），因为HashSet的迭代性能和容量成正比，所以我们通常不会设置太大的容量，默认或者更低。
但当构造LinkedHashSet时，选择初始化容量过高的值的副作用不会那么严重，因为其迭代性能与集合大小成正比。

TreeSet类

public class TreeSetTest {
    public static void main(String[] args) {
        TreeSet s = new TreeSet();
        s.add(1);
        s.add(2);
        s.add(3);
        s.add(4);
        System.out.println(s);
        System.out.println(s.first());  //1
        System.out.println(s.last());   //4
        System.out.println(s.headSet(3));   //1,2
        System.out.println(s.tailSet(2));   //2,3,4
        System.out.println(s.subSet(1,3)); //1,2,3
    }
}

可以看出（好像也看不太出。。没事），TreeSet并不是根据元素的插入顺序进行排序的，而是根据元素的实际值大小来排序的
与HashSet集合采用hash算法来决定元素的存储位置不同，TreeSet采用红黑树的数据结构来存储集合元素。
TreeSet支持两种排序规则：自然排序和定制排序。在默认情况下，TreeSet采用自然排序。

TreeSet自然排序

自然排序：TreeSet会调用集合元素的compareTo(Object obj)方法来比较元素之间的大小关系，然后将集合元素按升序排列。

a.compareTo(b)方法来自Comparable接口，该方法返回一个整数：
返回0：两个对象相等
返回1：a大于b
返回-1：a小于b
Java的一些类已经实现了Comparable接口，并提供了比较大小的标准：

  • BigDemical、BigInteger以及所有的数值型对应的包装类：按他们的大小进行比较
  • Character：按字符的Unicode值进行比较
  • Boolean：true对应的包装类实例大于false对应的包装类实例
  • String：按字符串中字符的Unicode值进行比较
  • Data、Time：（后面的时间、日期） 比 （前面的时间、日期大）
    //下面程序试图向TreeSet集合中添加两个Err对象，添加第二个对象时，TreeSet会调用
    //该对象的compareTo(Object o)方法与集合中的其他元素进行比较——
    //如果其对应类没有实现Comparable接口，则会引发ClassCastException异常
    TreeSet ts = new TreeSet();
    ts.add(new Error());
    ts.add(new Error());
    /**
    *而且，大部分类在实现compareTo(Object o)方法的时候，都需要将被比较的对象o强转为相同类型，因为只有两个相同类型才能比较大小。
    *因此，向TreeSet里添加的应该是同一个类的对象，不然容易引发ClassCastException异常
    **/

总结：如果希望TreeSet能够正常工作，TreeSet集合中只能存同一类对象。

HashSet和TreeSet中可变元素的实例变量尽量不要修改（参与相等判断的）

对于TreeSet而言，判断两个元素是否相等的唯一标准是：两个对象通过compareTo(Object o)返回的整数是不是0。

import java.util.TreeSet;

class P implements Comparable{

    int num;

    public P(int num) {
        this.num = num;
    }

    @Override
    public String toString() {
        return "P{" +
                "num=" + num +
                '}';
    }

    @Override
    public int compareTo(Object o) {
        P p = (P)o;
        return this.num>p.num? 1: this.num==p.num?0:-1;
    }
}

public class TreeSet2 {
    public static void main(String[] args) {
        TreeSet ts = new TreeSet();
        ts.add(new P(1));
        ts.add(new P(5));
        ts.add(new P(7));
        ts.add(new P(9));
        System.out.println(ts);
        P first = (P)ts.first();
        first.num = 100;
        P last = (P)ts.last();
        last.num = 7;
        System.out.println(ts);

        System.out.println(ts.remove(new P(1)));
        System.out.println(ts.remove(new P(100)));
        System.out.println(ts);
        System.out.println(ts.remove(new P(5)));//①
        System.out.println(ts);
        /**
         * 添加后的元素如果实例变量被修改（而且这个实例变量能够影响compareTo()方法的判断，TreeSet也不会重新排序
         * 反而可能会造成出现重复的元素，导致两个都无法被删除，给操作带来困难
         * 
         * 一旦修改了TreeSet集合里可变元素的实例对象，当再试图删除该对象时，TreeSet也会删除失败
         * 甚至连集合中原有的、实例变量没有被修改但与修改后的元素相等的元素也无法被删除
         *
         * 说明TreeSet可以删除没有被修改实例变量、且不与其他修改实例变量的对象重复的对象
         * 
         * 当执行上面①行代码时，TreeSet会对集合中的元素重新索引（不是重新排序）。接下来
         * 就可以删除TreeSet中的其他元素了。包括那些被修改过的实例变量的元素。
         */
    }
}
[P{num=1}, P{num=5}, P{num=7}, P{num=9}]
[P{num=100}, P{num=5}, P{num=7}, P{num=7}]
false
false
[P{num=100}, P{num=5}, P{num=7}, P{num=7}]
true
[P{num=100}, P{num=7}, P{num=7}]

与HashSet类似的是，如果TreeSet中包含了可变对象，当可变对象的实例变量被修改时，TreeSet在处理这些对象将非常复杂，而且容易出错.为了让程序更加健壮，不要修改放入HashSet和TreeSet集合中的关键实例变量（与CompareTo()方法相关的）.

定制排序

TreeSet如果想要实现定制排序，则可以通过Comparator接口的帮助。该接口里包含一个int compare(Object o1,Object o2)方法，o1 == o2 返回0；o1>o2 返回1；o1<o2 返回-1；
通过提供一个Comparator对象与TreeSet关联，由该Comparator对象负责集合的排序逻辑。
由于Comparator是一个函数式接口，因此可使用Lambda表达式来代替Comparator对象。

import java.util.TreeSet;

class N{
    int age;

    public N(int age) {
        this.age = age;
    }
}

class  M{
    int age;

    public M(int age) {
        this.age = age;
    }

    @Override
    public String toString() {
        return "M{" +
                "age=" + age +
                '}';
    }
}

public class TreeSetTest {
    public static void main(String[] args) {
        TreeSet ts = new TreeSet((o1,o2)->{
            M m1 = (M)o1;
            M m2 = (M)o2;
            //根据M对象的age属性来决定大小，age越大，M对象反而越小
            return m1.age>m2.age? -1:m1.age<m2.age?1:0;
        });
        ts.add(new M(5));
        ts.add(new M(9));
        ts.add(new M(10));
        ts.add(new M(1));
//        ts.add(new N(90));  ClassCastException异常 所以还是不要添加不同类的对象
        System.out.println(ts);
    }
}
[M{age=10}, M{age=9}, M{age=5}, M{age=1}]
上一篇：JAVA基础-集合Set


下一篇：ArrayList和LinkedList区别以及list,set,map三者的区别