Set集合 - 图1

基本概念

  • java.util.Set集合是Collection集合的子集合，与List集合平级。
  • 该集合中元素没有先后放入次序「不是随机」，且不允许重复 {与list集合相反}

  • 该集合的主要实现类是：HashSet类 和 TreeSet类以及LinkedHashSet类

    • HashSet类的底层是采用哈希表进行数据管理的

      哈希表是一个

    • TreeSet类的底层是采用红黑树进行数据管理的

其中LinkedHashSet类与HashSet类的不同之处在于内部维护了一个双向链表，链表中记录了元素的迭代顺序，也就是元素插入集合中的先后顺序，因此便于迭代。

常用的方法

参考Collection集合中的方法

案例题目

  • 准备一个Set集合指向HashSet对象，向该集合中添加元素"two"并打印，再向集合中添加元素"one"并打印，再向集合中添加元素"three"并打印，再向集合中添加"one"并打印。
  1. public class HashSetDemo {
  2.     public static void main(String[] args) {
  3.         Set set = new HashSet();
  4.         System.out.println("set集合：" + set);//[]
  6.         boolean add = set.add("two");
  7.         System.out.println("添加是否成功："+ add);//true
  8.         System.out.println("set集合：" + set);//[two]
  9.         add = set.add("one");
  10.         System.out.println("添加是否成功："+ add);//true
  11.         System.out.println("set集合：" + set);//[one, two]
  12.         add = set.add("three");
  13.         System.out.println("添加是否成功："+ add);//true
  14.         System.out.println("set集合：" + set);//[one, two, three]
  15.         add = set.add("one");
  16.         System.out.println("添加是否成功："+ add);//false
  17.         System.out.println("set集合：" + set);//[one, two, three]
  18.     }
  19. }
  • 对应的不能有重复的元素，如果添加重复元素，则返回false，添加失败
  • 如果声明的是LinkedHashSet，对应的打印顺序，是按着添加顺序打印 
  1. public class HashSetDemo {
  3.     public static void main(String[] args) {
  4. //        Set set = new HashSet();
  5.         Set set = new LinkedHashSet();
  7.         System.out.println("set集合：" + set);//[]
  9.         boolean add = set.add("two");
  10.         System.out.println("添加是否成功："+ add);//true
  11.         System.out.println("set集合：" + set);//[two]
  12.         add = set.add("one");
  13.         System.out.println("添加是否成功："+ add);//true
  14.         System.out.println("set集合：" + set);//[one, two] [two, one]
  15.         add = set.add("three");
  16.         System.out.println("添加是否成功："+ add);//true
  17.         System.out.println("set集合：" + set);//[one, two, three]  [two, one, three]
  18.         add = set.add("one");
  19.         System.out.println("添加是否成功："+ add);//false
  20.         System.out.println("set集合：" + set);//[one, two, three]   [two, one, three]
  21.     }
  22. }

元素放入HashSet集合的原理

  • 使用元素调用hashCode方法获取对应的哈希码值，再由某种哈希算法计算出该元素在数组中的索引位置。
  • 若该位置没有元素，则将该元素直接放入即可。
  • 若该位置有元素，则使用新元素与已有元素依次比较哈希值，若哈希值不相同，则将该元素直接放入。
  • 若新元素与已有元素的哈希值相同，则使用新元素调用equals方法与已有元素依次比较。
  • 若相等则添加元素失败，否则将元素直接放入即可。

思考：为什么要求重写equals方法后要重写hashCode方法呢？解析：

当两个元素调用equals方法相等时证明这两个元素相同，重写hashCode方法后保证这两个元素得到的哈希码值相同，由同一个哈希算法生成的索引位置相同，此时只需要与该索引位置已有元素比较即可，从而提高效率并避免重复元素的出现。

TreeSet集合的概念

二叉树主要指每个节点最多只有两个子节点的树形结构。

二叉树

Set集合 - 图2

根节点

  • 节点1是所有的节点中最起始的节点，叫根节点

子节点

  • 节点2，3叫做节点1的子节点
  • 节点4，5叫做节点2的子节点
  • 节点6，7叫做节点3的子节点

父节点

  • 节点1叫节点2，3的父节点
  • 节点2叫节点4，5的父节点
  • 节点3叫节点6，7的父节点

叶子节点

  • 节点4，5，6，7叫叶子节点

枝节点

  • 节点2，3叫枝节点

高度，大小

  • 高度是3层
  • 大小是有7个节点

有序二叉树

  • 满足以下3个特征的二叉树叫做有序二叉树。
    • 左子树中的任意节点元素都小于根节点元素值；
    • 右子树中的任意节点元素都大于根节点元素值；
    • 左子树和右子树的内部也遵守上述规则；

Set集合 - 图3

  • 节点30称为节点50的左子节点
  • 节点80称为节点50的右子节点

由于TreeSet集合的底层采用红黑树进行数据的管理，当有新元素插入到TreeSet集合时，需要使用新元素与集合中已有的元素依次比较来确定新元素的合理位置。

  1. public class TreeSetDemo {
  2.     public static void main(String[] args) {
  4.         // 1.准备一个TreeSet集合并打印
  5.         Set<String> s1 = new TreeSet<>();
  6.         System.out.println("s1 = " + s1); // [啥也没有]
  8.         // 2.向集合中添加String类型的对象并打印
  9.         boolean b1 = s1.add("aa");
  10.         System.out.println("b1 = " + b1); // true
  11.         System.out.println("s1 = " + s1); // [aa]
  13.         b1 = s1.add("cc");
  14.         System.out.println("b1 = " + b1); // true
  15.         System.out.println("s1 = " + s1); // [aa, cc]
  17.         b1 = s1.add("bb");
  18.         System.out.println("b1 = " + b1); // true
  19.         // 由于TreeSet集合的底层是采用红黑树实现的，因此元素有大小次序，默认从小到大打印
  20.         System.out.println("s1 = " + s1); // [aa, bb, cc]
  21.         }
  23. }
  • 比较元素大小的规则有两种方式：
    • 使用元素的自然排序规则进行比较并排序，让元素类型实现java.lang.Comparable接口；
    • 使用比较器规则进行比较并排序，构造TreeSet集合时传入java.util.Comparator接口；

自然排序的规则比较单一，而比较器的规则比较多元化，而且比较器优先于自然排序；

自然排序规则

默认结果为0
  1. public class Student implements Comparable<Student> {
  2.    private String name;
  3.     private int age;
  5.     @Override
  6.     public int compareTo(Student o) {
  7.         return 0;   // 调用对象和参数对象相等，调用对象就是新增加的对象
  8.     }
  9. }
  1. Set<Student> s2 = new TreeSet<>();
  2. s2.add(new Student("gaigai", 35));
  3. s2.add(new Student("gaigai", 30));
  4. s2.add(new Student("java", 35));
  5. s2.add(new Student("set", 40));
  6. System.out.println("s2 = " + s2);

结果：

  1. s2 = [Student{name='gaigai', age=35}]
  • 只剩下第一个添加的内容，后面的添加内容默认当作相等
    • set集合里面不能添加相同元素，所以添加失败

默认结果为1
  1. public class Student implements Comparable<Student> {
  2.    private String name;
  3.     private int age;
  5.     @Override
  6.     public int compareTo(Student o) {
  7.         return 1;   // 调用对象和参数对象相等，调用对象就是新增加的对象
  8.     }
  9. }
  1. Set<Student> s2 = new TreeSet<>();
  2. s2.add(new Student("gaigai", 35));
  3. s2.add(new Student("gaigai", 30));
  4. s2.add(new Student("java", 35));
  5. s2.add(new Student("set", 40));
  6. System.out.println("s2 = " + s2);

结果：

  1. s2 = [Student{name='gaigai', age=35}, Student{name='gaigai', age=30}, Student{name='java', age=35}, Student{name='set', age=40}]
  • 按添加顺序一个个往后添加

默认结果为-1
  1. public class Student implements Comparable<Student> {
  2.    private String name;
  3.     private int age;
  5.     @Override
  6.     public int compareTo(Student o) {
  7.         return -1;   // 调用对象和参数对象相等，调用对象就是新增加的对象
  8.     }
  9. }
  1. Set<Student> s2 = new TreeSet<>();
  2. s2.add(new Student("gaigai", 35));
  3. s2.add(new Student("gaigai", 30));
  4. s2.add(new Student("java", 35));
  5. s2.add(new Student("set", 40));
  6. System.out.println("s2 = " + s2);

结果：

  1. s2 = [Student{name='set', age=40}, Student{name='java', age=35}, Student{name='gaigai', age=30}, Student{name='gaigai', age=35}]
  • 按添加顺序一个个往前添加

比较姓名
  1. public class Student implements Comparable<Student> {
  2.    private String name;
  3.     private int age;
  5.     @Override
  6.     public int compareTo(Student o) {
  7.         return this.getName().compareTo(o.getName());  // 比较姓名
  8.     }
  9. }
  1. Set<Student> s2 = new TreeSet<>();
  2. s2.add(new Student("gaigai", 35));
  3. s2.add(new Student("gaigai", 30));
  4. s2.add(new Student("java", 35));
  5. s2.add(new Student("set", 40));
  6. System.out.println("s2 = " + s2);

结果：

  1. s2 = [Student{name='gaigai', age=35}, Student{name='java', age=35}, Student{name='set', age=40}]
  • 姓名相同的没有添加成功，其它的按姓名开头英文字母排序

比较年龄
  1. public class Student implements Comparable<Student> {
  2.    private String name;
  3.     private int age;
  5.     @Override
  6.     public int compareTo(Student o) {
  7.         return this.getAge() - o.getAge(); // 比较年龄
  8.     }
  9. }
  1. Set<Student> s2 = new TreeSet<>();
  2. s2.add(new Student("gaigai", 35));
  3. s2.add(new Student("gaigai", 30));
  4. s2.add(new Student("java", 35));
  5. s2.add(new Student("set", 40));
  6. System.out.println("s2 = " + s2);

结果：

  1. s2 = [Student{name='gaigai', age=30}, Student{name='gaigai', age=35}, Student{name='set', age=40}]
  • 年龄相同的后面出现的对象元素没有添加成功，其它的按年龄大小排序

比较姓名+年龄
  1. public class Student implements Comparable<Student> {
  2.    private String name;
  3.     private int age;
  5.     @Override
  6.     public int compareTo(Student o) {
  7.         int ia = this.getName().compareTo(o.getName());
  8.         if (0 == ia) {
  9.             return this.getAge() - o.getAge();
  10.         }
  11.         return ia;
  12.     }
  13. }
  1. Set<Student> s2 = new TreeSet<>();
  2. s2.add(new Student("gaigai", 35));
  3. s2.add(new Student("gaigai", 30));
  4. s2.add(new Student("java", 35));
  5. s2.add(new Student("set", 40));
  6. System.out.println("s2 = " + s2);

结果：

s2 = [Student{name='gaigai', age=30}, Student{name='gaigai', age=35}, Student{name='java', age=35}, Student{name='set', age=40}]
  • 先比较姓名，如果姓名相同再比较年龄，都添加进入

比较器规则

public class TreeSetDemo {
    public static void main(String[] args) {
System.out.println("----------------------------------------------------------");
        // 准备一个比较器对象作为参数传递给构造方法
        // 匿名内部类： 
        //接口/父类类型 引用变量名 = new 接口/父类类型() { 方法的重写 };

        Comparator<Student> comparator = new Comparator<Student>() {
            @Override
            public int compare(Student o1, Student o2) {  
            // o1表示新增加的对象  o2表示集合中已有的对象
                return o1.getAge() - o2.getAge(); 
                // 表示按照年龄比较
            }
        };

        Set<Student> s2 = new TreeSet<>(comparator);
        s2.add(new Student("gaigai", 35));
        s2.add(new Student("gaigai", 30));
        s2.add(new Student("java", 35));
        s2.add(new Student("set", 40));
        System.out.println("s2 = " + s2);
    }
}

结果：

s2 = [Student{name='gaigai', age=30}, Student{name='gaigai', age=35}, Student{name='set', age=40}]

优化为lambda:

  • 从Java8开始支持Lambda表达式: (参数列表) -> { 方法体 }
Comparator<Student> comparator = (Student o1, Student o2) -> { return o1.getAge() - o2.getAge(); };