Cllection--Set集合

Set集合概述

java.util.Set接口和java.util.List接口一样，同样继承自Collection接口，与Collection接口中的方法基本一致，并没有对Collection接口进行功能上的扩充，只是比Collection接口更加严格了。与List接口不同的是，Set接口中元素无序，并且都会以某种规则保证存入的元素不出现重复。

Set集合有多个子类，这里介绍其中的java.util.HashSet、java.util.LinkedHashSet两个集合。

Set集合的特点

 1.Set集合中的元素不可重复

 2.Set集合没有索引

HashSet集合

什么是HashSet集合

java.util.HashSet是Set接口的一个实现类，存储的元素是不可重复的，并且元素都是无序的(即存取顺序不一致)。java.util.HashSet底层的实现其实是一个java.util.HashMap支持。

HashSet根据对象的哈希值来确定元素在集合中的存储位置，具有良好的存取和查找性能。保证元素唯一性依赖于：hashCode与equals方法。

HashSet集合的特点

HashSet代码演示

public class HashSetDemo {
    public static void main(String[] args) {
        //创建 Set集合
        HashSet<String>  set = new HashSet<String>();
        //添加元素
        set.add(new String("cba"));
        set.add("abc");
        set.add("bac"); 
        set.add("cba");  
        //遍历
        for (String name : set) {
            System.out.println(name);
        }
    }
}

如何保证Hashset集合唯一？
底层依赖 两个方法：hashCode()和equals()。
   步骤：
        首先比较哈希值
        如果相同，继续走，比较地址值或者走equals()
        如果不同,就直接添加到集合中  
   按照方法的步骤来说：   
        先看hashCode()值是否相同
            相同:继续走equals()方法
                返回true： 说明元素重复，就不添加
                返回false：说明元素不重复，就添加到集合
            不同：就直接把元素添加到集合
   如果类没有重写这两个方法，默认使用的Object()。一般来说一样。
   而String类重写了hashCode()和equals()方法，所以，它就可以把内容相同的字符串去掉。只留下一个。

HashSet存储自定义类型元素

定义Student类

public class Student {
    private String name;
    private int age;
    public Student() {   }
    public Student(String name, int age) {
        this.name = name;
        this.age = age;    }
    public String getName() {     return name;    }
    public void setName(String name) {  this.name = name;   }
    public int getAge() {   return age;   }
    public void setAge(int age) {  this.age = age;   }
    @Override
    public String toString() {
        return "Student{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }   
    //不需要你手动重写Object  hashCode和equals ，再去测试
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Student student = (Student) o;
        return age == student.age &&
                Objects.equals(name, student.name);
    }
    @Override
    public int hashCode() {
        return Objects.hash(name, age);
    }
}

定义测试类

public class HashSetDemo2 {
    public static void main(String[] args) {
        //创建集合对象   该集合中存储 Student类型对象
        HashSet<Student> stuSet = new HashSet<Student>();
        //存储 
        stuSet.add(new Student("于谦", 43));
        stuSet.add(new Student("于谦", 43));
        stuSet.add(new Student("郭麒麟", 23));
        stuSet.add(new Student("郭麒麟", 23));
      
        for (Student stu2 : stuSet) {
            System.out.println(stu2);
        }
    }
}

HashSet集合存储数据的结构

JDK的版本不同，HashSet集合的数据结构有所不同：

JDK8之前：数组+链表

JDK8之后：数组+链表+红黑树

以上数据结构我们称之为是哈希表

负载因子：补充一下；0.75;

什么是哈希表

在JDK1.8之前，哈希表底层采用数组+链表实现，即使用链表处理冲突，同一hash值的链表都存储在一个链表里。但是当位于一个桶中的元素较多，即hash值相等的元素较多时，通过key值依次查找的效率较低。而JDK1.8中，哈希表存储采用数组+链表+红黑树实现，当链表长度超过阈值（8）时，将链表转换为红黑树，这样大大减少了查找时间。

简单的来说，哈希表是由数组+链表+红黑树（JDK1.8增加了红黑树部分）实现的，如下图所示。

存储流程分析：

总结

总而言之，JDK1.8引入红黑树大程度优化了HashMap的性能，那么对于我们来讲保证HashSet集合元素的唯一，其实就是根据对象的hashCode和equals方法来决定的。【如果我们往集合中存放自定义的对象，那么保证其唯一，就必须复写hashCode和equals方法建立属于当前对象的比较方式】。

LinkedHashSet

什么是LinkedHashSet

我们知道HashSet保证元素唯一，可是元素存放进去是没有顺序的，那么我们要保证有序，怎么办呢？

在HashSet下面有一个子类java.util.LinkedHashSet，它是 链表 和 哈希表组合的一个数据存储结构。

LinkedHashSet集合的特点

LinkedHashSet集合中的元素不可重复

LinkedHashSet集合没有索引

LinkedHashSet集合是有序的(存储元素的顺序与取出元素顺序一致)

总结： 有序，唯一

代码演示

public class LinkedHashSetDemo {
    public static void main(String[] args) {
        Set<String> set = new LinkedHashSet<String>();
        set.add("bbb");
        set.add("aaa");
        set.add("abc");
        set.add("bbc");
        Iterator<String> it = set.iterator();
        while (it.hasNext()) {
            System.out.println(it.next());
        }
    }
}

TreeSet

使用元素的自然排序对元素进行排序
或者根据创建set时提供的Comparable排序
具体取决于你用的构造方法

TreeSet自然排序

代码实现

public class TreeSetDemo {
    public static void main(String[] args) {
        //使用元素的自然顺序对元素进行排序,唯一
        TreeSet<Integer> ts = new TreeSet<>();
        ts.add(20);
        ts.add(18);
        ts.add(23);
        ts.add(22);
        ts.add(17);
        ts.add(24);
        ts.add(19);
        ts.add(18);
        ts.add(24);

        for(Integer i : ts){
            System.out.println(i);
        }
        System.out.println("=================");
        TreeSet<String> ts2 = new TreeSet<>();
        ts2.add("ab");
        ts2.add("e");
        ts2.add("r");
        ts2.add("y");
        ts2.add("c");
        ts2.add("ac");

        for(String s : ts2){
            System.out.println(s);
        }
    }
}

TreeSet存储自定义对象

public class Demo {
    public static void main(String[] args) {
     // 创建集合对象
        TreeSet<Student> ts = new TreeSet<Student>();

        Student s1 = new Student("b",23);
        Student s2 = new Student("a",23);
        Student s3 = new Student("jack",27);

        ts.add(s1);
        ts.add(s2);
        ts.add(s3);

        for(Student s : ts){
            System.out.println(s.getName()+"--"+s.getAge());
        }
    }
}

/**
 * @Desc  如果一个类的元素要想进行自然排序，就必须实现自然排序的接口
          Comparable 可以看成是内部比较器
 */
public class Student implements  Comparable<Student>{
    private String name;
    private int age;

    public Student() {
    }
    public Student(String name, int age) {
        this.name = name;
        this.age = age;
    }
    public String getName() {     return name; }
    public void setName(String name) {  this.name = name;  }
    public int getAge() {  return age;  }
    public void setAge(int age) {  this.age = age; }
    @Override
    public String toString() {
        return "Student{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }
    @Override
    public int compareTo(Student s) {
        //按照年龄排序 ，主要条件
        int num = this.age - s.age;//年龄相同就不存储
        int num2 = num == 0 ? this.name.compareTo(s.name) : num ;//年龄相同的的时同，比较一下名是否相同
        return num2;
    }
}

比较器排序

Comparator 可以看成一个外部比较器，好处不用修改原代码直接实现

Comparetable需要修改原有代码，不符合OCP原则 英文缩写OCP，全称Open Closed Principle。 原始定义：Software entities (classes, modules, functions) should be open for extension but closed for modification。开闭原则。 字面翻译：软件实体（包括类、模块、功能等）应该对扩展开放，但是对修改关闭。 总的来说，开闭原则提高系统的可维护性和代码的重用性。

代码实现

import java.util.TreeSet;
/*
 * 需求：请按照姓名的长度排序
 * TreeSet集合保证元素排序和唯一性的原理
 * 唯一性：是根据比较的返回是否是0来决定。
 * 排序：
 *      A:自然排序(元素具备比较性)
 *          让元素所属的类实现自然排序接口 Comparable
 *      B:比较器排序(集合具备比较性)
 *          让集合的构造方法接收一个比较器接口的子类对象 Comparator
 */
public class Demo {
    public static void main(String[] args) {
        // 创建集合对象
        // TreeSet<Student> ts = new TreeSet<Student>(); //自然排序
        // public TreeSet(Comparator comparator) //比较器排序
        TreeSet<Student> ts = new TreeSet<Student>(new MyComparator());
        // 创建元素
        Student s1 = new Student("linqingxia", 27);
        Student s2 = new Student("zhangguorong", 29);
        Student s3 = new Student("wanglihong", 23);
        Student s4 = new Student("linqingxia", 27);
        Student s5 = new Student("liushishi", 22);
        Student s6 = new Student("wuqilong", 40);
        Student s7 = new Student("fengqingy", 22);
        Student s8 = new Student("linqingxia", 29);
        // 添加元素
        ts.add(s1);
        ts.add(s2);
        ts.add(s3);
        ts.add(s4);
        ts.add(s5);
        ts.add(s6);
        ts.add(s7);
        ts.add(s8);
        // 遍历
        for (Student s : ts) {
            System.out.println(s.getName() + "---" + s.getAge());
        }
    }
}

public class Student{
    private String name;
    private int age;
    public Student() {
    }
    public Student(String name, int age) {
        this.name = name;
        this.age = age;
    }
    public String getName() {        return name;    }
    public void setName(String name) {     this.name = name;    }
    public int getAge() {     return age;    }
    public void setAge(int age) {  this.age = age;    }
    @Override
    public String toString() {
        return "Student{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }
}

public class MyComparator implements Comparator<Student> {
    @Override
    public int compare(Student s1, Student s2) {
        // int num = this.name.length() - s.name.length();
        // this -- s1
        // s -- s2
        // 姓名长度
        int num = s1.getName().length() - s2.getName().length();
        // 姓名内容
        int num2 = num == 0 ? s1.getName().compareTo(s2.getName()) : num;
        // 年龄
        int num3 = num2 == 0 ? s1.getAge() - s2.getAge() : num2;
        return num3;
    }
}

Comparable<T> 内部比较器，需要修改原代码，不符合OCP原则
    重写方法：  public int compareTo(T t) 
    
Comparator 可以看成一个外部比较器，好处不用修改原代码直接实现
    重写方法：  public int compare(Ojbect s1, Ojbect s2)
    
返回值类型：int 等于0 表示相等 大于0表示升序 小于0表示是降序