• Set接口是Collection的子接口，set接口没有提供额外的方法
  • Set 集合不允许包含相同的元素，如果试把两个相同的元素加入同一个Set 集合中，则添加操作失败。
  • Set 判断两个对象是否相同不是使用==运算符，而是根据equals()方法

    1、Set接口实现类的对比

    ```java /**
    • 1.Set接口的框架：
    • |——Collection接口：单列集合，用来存储一个一个的对象
    • |——Set接口：存储无序的、不可重复的数据 —>高中讲的“集合”
    • |——HashSet：作为Set接口的主要实现类；线程不安全的；可以存储null值
    • |——LinkedHashSet：作为HashSet的子类；遍历其内部数据时，可以按照添加的顺序遍历
    • 对于频繁的遍历操作，LinkedHashSet效率高于HashSet.
    • |——TreeSet：可以按照添加对象的指定属性，进行排序。 */
  1. <a name="v6DhE"></a>
  2. # 2、Set的无序性与不可重复性的理解
  3. **Set : 存储无序的、不可重复的数据**
  5. - 无序性：不等于随机性，存储的数据在底层数据中并非按照数组的索引的顺序添加，而是根据数值的哈希值进行决定的
  6. - 不可重复性：保证添加的元素按照equals()判断，不能返回true,即相同的元素只能添加一个
  7. ```java
  8. import java.util.HashSet;
  9. import java.util.Iterator;
  10. import java.util.Set;
  12. /**
  13.  *
  14.  * 1.Set接口中没有定义额外的方法，使用的都是Collection中声明过的方法。
  15.  *
  16.  */
  17. public class SetTest {
  19.     /**
  20.      * 一、Set:存储无序的、不可重复的数据
  21.      *      1.无序性：不等于随机性。存储的数据在底层数组中并非按照数组索引的顺序添加，而是根据数据的哈希值决定的。
  22.      *
  23.      *      2.不可重复性：保证添加的元素按照equals()判断时，不能返回true.即：相同的元素只能添加一个。
  24.      *
  25.      * 二、添加元素的过程：以HashSet为例：
  26.      *
  27.      */
  28.     @Test
  29.     public void test(){
  30.         Set set = new HashSet();
  31.         set.add(123);
  32.         set.add(456);
  33.         set.add("fgd");
  34.         set.add("book");
  35.         set.add(new User("Tom",12));
  36.         set.add(new User("Tom",12));
  37.         set.add(129);
  39.         Iterator iterator = set.iterator();
  40.         while(iterator.hasNext()){
  41.             System.out.println(iterator.next());
  42.         }
  43.     }
  44. }
  1. public class User{
  2.     private String name;
  3.     private int age;
  5.     public User() {
  6.     }
  8.     public User(String name, int age) {
  9.         this.name = name;
  10.         this.age = age;
  11.     }
  13.     public String getName() {
  14.         return name;
  15.     }
  17.     public void setName(String name) {
  18.         this.name = name;
  19.     }
  21.     public int getAge() {
  22.         return age;
  23.     }
  25.     public void setAge(int age) {
  26.         this.age = age;
  27.     }
  29.     @Override
  30.     public String toString() {
  31.         return "User{" +
  32.                 "name='" + name + '\'' +
  33.                 ", age=" + age +
  34.                 '}';
  35.     }
  37.     @Override
  38.     public boolean equals(Object o) {
  39.         System.out.println("User equals()....");
  40.         if (this == o) return true;
  41.         if (o == null || getClass() != o.getClass()) return false;
  43.         User user = (User) o;
  45.         if (age != user.age) return false;
  46.         return name != null ? name.equals(user.name) : user.name == null;
  47.     }
  49.     @Override
  50.     public int hashCode() { 
  51.         int result = name != null ? name.hashCode() : 0;
  52.         result = 31 * result + age;
  53.         return result;
  54.     }
  55. }

3、HashSet中元素的添加过程

  • HashSet是Set 接口的典型实现，大多数时候使用Set 集合时都使用这个实现类。
  • HashSet按Hash 算法来存储集合中的元素，因此具有很好的存取、查找、删除性能。
  • HashSet具有以下特点：不能保证元素的排列顺序
    • HashSet不是线程安全的
    • 集合元素可以是null
  • 底层也是数组，初始容量为16，当如果使用率超过0.75，（16*0.75=12）就会扩大容量为原来的2倍。（16扩容为32，依次为64,128…等）
  • HashSet 集合判断两个元素相等的标准：两个对象通过hashCode() 方法比较相等，并且两个对象的equals()方法返回值也相等。
  • 对于存放在Set容器中的对象，对应的类一定要重写equals()和hashCode(Object obj)方法，以实现对象相等规则。即：”相等的对象必须具有相等的散列码“。

    3.1、添加元素的过程

    以HashSet为例
    我们向HashSet中添加元素a,首先调用的是a所在类的hashCode()方法，计算出元素a的哈希值，此哈希值通过某种算法计算出HashSet底层数组的存放位置（即为:索引位置），判断数组上是否已经有元素
    如果此位置上没有其他元素，则元素a添加成功。——> 情况1
    如果此位置上有其他元素b(或以链表形式存在的多个元素)，则比较元素a与元素b的hash值：
    如果hash值不同，则元素a添加成功 ——> 情况2
    如果hash值相同，进而需要调用元素a所在类的equals()方法：
    equals()返回true,元素a添加失败
    equals() 返回false,则元素a添加成功。——> 情况3

对于添加成功的情况2和情况3而言：元素a 与已经存在指定索引位置上数据以链表的方式存储。
jdk 7 :元素a放到数组中，指向原来的元素。
jdk 8 :原来的元素在数组中，指向元素a

image.png

4、关于hashCode()和equals()的重写

4.1、重写hashCode() 方法的基本原则

  • 在程序运行时，同一个对象多次调用hashCode()方法应该返回相同的值。
  • 当两个对象的equals()方法比较返回true时，这两个对象的hashCode()方法的返回值也应相等。

  • 对象中用作equals() 方法比较的Field，都应该用来计算hashCode值。

    4.2、重写equals() 方法的基本原则

    以自定义的Customer类为例，何时需要重写equals()？

  • 当一个类有自己特有的“逻辑相等”概念,当改写equals()的时候，总是要改写hashCode()，根据一个类的equals方法（改写后），两个截然不同的实例有可能在逻辑上是相等的，但是，根据Object.hashCode()方法，它们仅仅是两个对象。

  • 因此，违反了“相等的对象必须具有相等的散列码”。

  • 结论：复写equals方法的时候一般都需要同时复写hashCode方法。通常参与计算hashCode的对象的属性也应该参与到equals()中进行计算。

    5、LinkedHashSet的使用

  • LinkedHashSet是HashSet的子类

  • LinkedHashSet根据元素的hashCode值来决定元素的存储位置，但它同时使用双向链表维护元素的次序，这使得元素看起来是以插入顺序保存的。
  • LinkedHashSet插入性能略低于HashSet，但在迭代访问Set 里的全部元素时有很好的性能。
  • LinkedHashSet不允许集合元素重复。

image.png

  1. import org.junit.Test;
  3. import java.util.Iterator;
  4. import java.util.LinkedHashSet;
  5. import java.util.Set;
  7. public class SetTest {
  9.     /**
  10.      * LinkedHashSet的使用
  11.      * LinkedHashSet作为HashSet的子类，在添加数据的同时，每个数据还维护了两个引用，记录此数据前一个
  12.      * 数据和后一个数据。
  13.      * 优点：对于频繁的遍历操作，LinkedHashSet效率高于HashSet
  14.      */
  15.     @Test
  16.     public void test2(){
  17.         Set set = new LinkedHashSet();
  18.         set.add(456);
  19.         set.add(123);
  20.         set.add(123);
  21.         set.add("AA");
  22.         set.add("CC");
  23.         set.add(new User("Tom",12));
  24.         set.add(new User("Tom",12));
  25.         set.add(129);
  27.         Iterator iterator = set.iterator();
  28.         while(iterator.hasNext()){
  29.             System.out.println(iterator.next());
  30.         }
  31.     }
  32. }
  1. public class User{
  2.     private String name;
  3.     private int age;
  5.     public User() {
  6.     }
  8.     public User(String name, int age) {
  9.         this.name = name;
  10.         this.age = age;
  11.     }
  13.     public String getName() {
  14.         return name;
  15.     }
  17.     public void setName(String name) {
  18.         this.name = name;
  19.     }
  21.     public int getAge() {
  22.         return age;
  23.     }
  25.     public void setAge(int age) {
  26.         this.age = age;
  27.     }
  29.     @Override
  30.     public String toString() {
  31.         return "User{" +
  32.                 "name='" + name + '\'' +
  33.                 ", age=" + age +
  34.                 '}';
  35.     }
  37.     @Override
  38.     public boolean equals(Object o) {
  39.         System.out.println("User equals()....");
  40.         if (this == o) return true;
  41.         if (o == null || getClass() != o.getClass()) return false;
  43.         User user = (User) o;
  45.         if (age != user.age) return false;
  46.         return name != null ? name.equals(user.name) : user.name == null;
  47.     }
  49.     @Override
  50.     public int hashCode() { //return name.hashCode() + age;
  51.         int result = name != null ? name.hashCode() : 0;
  52.         result = 31 * result + age;
  53.         return result;
  54.     }
  55. }

6、TreeSet的自然排序

  • TreeSet是SortedSet接口的实现类，TreeSet可以确保集合元素处于排序状态。
  • TreeSet底层使用红黑树结构存储数据
  • 新增的方法如下：(了解)
    • Comparator comparator()
    • Object first()
    • Object last()
    • Object lower(Object e)
    • Object higher(Object e)
    • SortedSet subSet(fromElement, toElement)
    • SortedSet headSet(toElement)
    • SortedSet tailSet(fromElement)
  • TreeSet两种排序方法：自然排序和定制排序。默认情况下，TreeSet采用自然排序。
  • TreeSet和后面要讲的TreeMap采用红黑树的存储结构
  • 特点：有序，查询速度比List快
  • 自然排序：TreeSet会调用集合元素的compareTo(Object obj)方法来比较元素之间的大小关系，然后将集合元素按升序(默认情况)排列。
  • 如果试图把一个对象添加到TreeSet时，则该对象的类必须实现Comparable 接口。
    • 实现Comparable 的类必须实现compareTo(Object obj)方法，两个对象即通过compareTo(Object obj)方法的返回值来比较大小。
  • Comparable 的典型实现
    • BigDecimal、BigInteger以及所有的数值型对应的包装类：按它们对应的数值大小进行比较
    • Character：按字符的unicode值来进行比较
    • Boolean：true 对应的包装类实例大于false 对应的包装类实例
    • String：按字符串中字符的unicode 值进行比较
    • Date、Time：后边的时间、日期比前面的时间、日期大
  • 向TreeSet中添加元素时，只有第一个元素无须比较compareTo()方法，后面添加的所有元素都会调用compareTo()方法进行比较。
  • 因为只有相同类的两个实例才会比较大小，所以向TreeSet中添加的应该是同一个类的对象。
  • 对于TreeSet集合而言，它判断两个对象是否相等的唯一标准是：两个对象通过compareTo(Object obj)方法比较返回值。
  • 当需要把一个对象放入TreeSet中，重写该对象对应的equals()方法时，应保证该方法与compareTo(Object obj) 方法有一致的结果：如果两个对象通过equals()方法比较返回true，则通过compareTo(Object obj)方法比较应返回0。否则，让人难以理解。 ```java import org.junit.Test;

import java.util.Iterator; import java.util.TreeSet;

/**

  • 1.向TreeSet中添加的数据，要求是相同类的对象。
  • 2.两种排序方式：自然排序（实现Comparable接口） 和 定制排序（Comparator）
  • 3.自然排序中，比较两个对象是否相同的标准为：compareTo()返回0.不再是equals().

  • 4.定制排序中，比较两个对象是否相同的标准为：compare()返回0.不再是equals(). */ public class TreeSetTest {

    @Test public void test() {

    1.  TreeSet set = new TreeSet();
    3.  //失败：不能添加不同类的对象

    // set.add(123); // set.add(456); // set.add(“AA”); // set.add(new User(“Tom”,12));

    1.  //举例一：

    // set.add(34); // set.add(-34); // set.add(43); // set.add(11); // set.add(8);

    1.  //举例二：
    2.  set.add(new User("Tom",12));
    3.  set.add(new User("Jerry",32));
    4.  set.add(new User("Jim",2));
    5.  set.add(new User("Mike",65));
    6.  set.add(new User("Jack",33));
    7.  set.add(new User("Jack",56));
    9.  Iterator iterator = set.iterator();
    10.  while(iterator.hasNext()){
    11.      System.out.println(iterator.next());
    12.  }

    } }

  1. <a name="zoiqA"></a>
  2. # 7、TreeSet的定制排序
  4. - TreeSet的**自然排序**要求元素所属的类实现Comparable接口，如果元素所属的类没有实现Comparable接口，或不希望按照升序(默认情况)的方式排列元素或希望按照其它属性大小进行排序，则考虑使用定制排序。定制排序，通过Comparator接口来实现。需要重写compare(T o1,T o2)方法。
  5. - 利用int compare(T o1,T o2)方法，比较o1和o2的大小：如果方法返回正整数，则表示o1大于o2；如果返回0，表示相等；返回负整数，表示o1小于o2。
  6. - 要实现**定制排序**，需要将实现Comparator接口的实例作为形参传递给TreeSet的构造器。
  7. - 此时，仍然只能向TreeSet中添加类型相同的对象。否则发生ClassCastException异常。
  8. - 使用定制排序判断两个元素相等的标准是：通过Comparator比较两个元素返回了0。
  9. ```java
  10. import org.junit.Test;
  12. import java.util.Comparator;
  13. import java.util.Iterator;
  14. import java.util.TreeSet;
  16. /**
  17.  * 1.向TreeSet中添加的数据，要求是相同类的对象。
  18.  * 2.两种排序方式：自然排序（实现Comparable接口） 和 定制排序（Comparator）
  19.  * 3.自然排序中，比较两个对象是否相同的标准为：compareTo()返回0.不再是equals().
  20.  * 4.定制排序中，比较两个对象是否相同的标准为：compare()返回0.不再是equals().
  21.  */
  22. public class TreeSetTest {
  24.     @Test
  25.     public void tets2(){
  26.         Comparator com = new Comparator() {
  27.             //按照年龄从小到大排列
  28.             @Override
  29.             public int compare(Object o1, Object o2) {
  30.                 if(o1 instanceof User && o2 instanceof User){
  31.                     User u1 = (User)o1;
  32.                     User u2 = (User)o2;
  33.                     return Integer.compare(u1.getAge(),u2.getAge());
  34.                 }else{
  35.                     throw new RuntimeException("输入的数据类型不匹配");
  36.                 }
  37.             }
  38.         };
  40.         TreeSet set = new TreeSet(com);
  41.         set.add(new User("Tom",12));
  42.         set.add(new User("Jerry",32));
  43.         set.add(new User("Jim",2));
  44.         set.add(new User("Mike",65));
  45.         set.add(new User("Mary",33));
  46.         set.add(new User("Jack",33));
  47.         set.add(new User("Jack",56));
  50.         Iterator iterator = set.iterator();
  51.         while(iterator.hasNext()){
  52.             System.out.println(iterator.next());
  53.         }
  54.     }
  55. }
  1. public class User implements Comparable{
  2.     private String name;
  3.     private int age;
  5.     public User() {
  6.     }
  8.     public User(String name, int age) {
  9.         this.name = name;
  10.         this.age = age;
  11.     }
  13.     public String getName() {
  14.         return name;
  15.     }
  17.     public void setName(String name) {
  18.         this.name = name;
  19.     }
  21.     public int getAge() {
  22.         return age;
  23.     }
  25.     public void setAge(int age) {
  26.         this.age = age;
  27.     }
  29.     @Override
  30.     public String toString() {
  31.         return "User{" +
  32.                 "name='" + name + '\'' +
  33.                 ", age=" + age +
  34.                 '}';
  35.     }
  37.     @Override
  38.     public boolean equals(Object o) {
  39.         System.out.println("User equals()....");
  40.         if (this == o) return true;
  41.         if (o == null || getClass() != o.getClass()) return false;
  43.         User user = (User) o;
  45.         if (age != user.age) return false;
  46.         return name != null ? name.equals(user.name) : user.name == null;
  47.     }
  49.     @Override
  50.     public int hashCode() { //return name.hashCode() + age;
  51.         int result = name != null ? name.hashCode() : 0;
  52.         result = 31 * result + age;
  53.         return result;
  54.     }
  56.     //按照姓名从大到小排列,年龄从小到大排列
  57.     @Override
  58.     public int compareTo(Object o) {
  59.         if (o instanceof User) {
  60.             User user = (User) o;
  61. //            return this.name.compareTo(user.name);  //按照姓名从小到大排列
  62. //            return -this.name.compareTo(user.name);  //按照姓名从大到小排列
  63.             int compare = -this.name.compareTo(user.name);  //按照姓名从大到小排列
  64.             if(compare != 0){   //年龄从小到大排列
  65.                 return compare;
  66.             }else{
  67.                 return Integer.compare(this.age,user.age);
  68.             }
  69.         } else {
  70.             throw new RuntimeException("输入的类型不匹配");
  71.         }
  72.     }
  73. }