Set 接口

说明

  • Set接口是Collection的子接口，set接口没有提供额外的方法
  • Set 集合不允许包含相同的元素，如果试把两个相同的元素加入同一个 Set 集合中，则添加操作失败。
  • 无序性：不等于随机性。存储的数据在底层数组中并非照数组索引的顺序添加，而是根据数据的哈希值决定的。
  • 不可重复性：保证添加的元素照equals()判断时，不能返回true.即：相同的元素只能添加一个。

    结构图

    Collection子接口：Set接口 - 图1

Set实现类之一：HashSet

HashSet底层：数组+链表的结构。（前提：jdk7)

向HashSet中添加元素的过程

  1. 我们向HashSet中添加元素a，首先调用元素a所在类的hashCode()方法，计算元素a的哈希值，然后根据 hashCode 值，通过某种散列函数决定该对象在 HashSet 底层数组中的存储位置。（即为：索引位置）
  2. 然后判断数组此位置上是否已经有没有元素：

如果此位置上没其他元素，则元素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

重写 hashCode() 方法和 equals() 方法的基本原则

  1. 向Set(主要指：HashSet、LinkedHashSet)中添加的数据，其所在的类一定要重写hashCode()和equals()
  2. 要求：重写的hashCode()和equals()尽可能保持一致性：相等的对象必须具有相等的散列码
  3. 对象中用作 equals() 方法比较的 Field，都应该用来计算 hashCode 值。
  4. 复写equals方法的时候一般都需要同时复写hashCode方法。通常参与计算hashCode的对象的属性也应该参与到equals()中进行计算。

Set实现类之二：LinkedHashSet

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

image.png

Set实现类之三： TreeSet

使用说明

  • 向TreeSet中添加的数据，要求是相同类的对象。
  • 两种排序方式：自然排序（实现Comparable接口 和 定制排序（Comparator）
  • TreeSet和后面要讲的TreeMap 采用红黑树的存储结构
  • 特点：有序，查询速度比List快

image.png

排序—自然排序

  • TreeSet 会调用集合元素的 compareTo(Object obj) 方法来比较元素之间的大小关系，然后将集合元素按升序(默认情况)排列
  • 如果试图把一个对象添加到 TreeSet 时，则该对象的类必须实现Comparable 接口compareTo(Object obj) 方法，两个对象即通过 compareTo(Object obj) 方法的返回值来比较大小。
  • 向 TreeSet 中添加元素时，只有第一个元素无须比较compareTo()方法，后面添加的所有元素都会调用compareTo()方法进行比较。
  • 因为只有相同类的两个实例才会比较大小，所以向 TreeSet中添加的应该是同一个类的对象。
  • 对于 TreeSet 集合而言，它判断两个对象是否相等的唯一标准是：两个对象通过 compareTo(Object obj) 方法比较返回值。

  • 当需要把一个对象放入 TreeSet 中，重写该对象对应的 equals() 方法时，应保证该方法与 compareTo(Object obj) 方法有一致的结果：如果两个对象通过 equals() 方法比较返回 true，则通过 compareTo(Object obj) 方法比较应返回 0。 否则，让人难以理解。
    ```java @Test public void test1(){

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

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

    1.   //举例二：
    2.   set.add(new User("Tom",12));
    3.   set.add(new User("Jerry",32));//默认调用String内部实现的compareTo接口
    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));
  1.     Iterator iterator = set.iterator();
  2.     while(iterator.hasNext()){
  3.         System.out.println(iterator.next());
  4.     }
  6. }
  1. <a name="ckKGN"></a>
  2. ###  排序—定制排序
  4. - TreeSet的自然排序要求元素所属的类实现Comparable接口，如果元素所属的类没有实现Comparable接口，或不希望按照升序(默认情况)的方式排列元素或希望按照其它属性大小进行排序，则考虑使用定制排序。定制排序，通过Comparator接口来 实现。需要重写compare(T o1,T o2)方法。
  5. - 利用int compare(T o1,T o2)方法，比较o1和o2的大小
  6. > 如果方法返回正整数，则表示o1大于o2；
  7. > 如果返回0，表示相等；
  8. > 返回负整数，表示o1小于o2。 
  10. - 要实现定制排序，需要将实现Comparator接口的实例作为形参传递给TreeSet的构造器。
  11. - 此时，仍然只能向TreeSet中添加类型相同的对象。否则发生ClassCastException异常。
  12. - 使用定制排序判断两个元素相等的标准是：通过Comparator比较两个元素返回了0。   
  13. ```java
  14. public void test2(){
  15.         Comparator com = new Comparator() {
  16.             //照年龄从小到大排列
  17.             @Override
  18.             public int compare(Object o1, Object o2) {
  19.                 if(o1 instanceof User && o2 instanceof User){
  20.                     User u1 = (User)o1;
  21.                     User u2 = (User)o2;
  22.                     return Integer.compare(u1.getAge(),u2.getAge());
  23.                 }else{
  24.                     throw new RuntimeException("输入的数据类型不匹配");
  25.                 }
  26.             }
  27.         };
  29.         TreeSet set = new TreeSet(com);
  30.         set.add(new User("Tom",12));
  31.         set.add(new User("Jerry",32));
  32.         set.add(new User("Jim",2));
  33.         set.add(new User("Mike",65));
  34.         set.add(new User("Mary",33));
  35.         set.add(new User("Jack",33));
  36.         set.add(new User("Jack",56));
  39.         Iterator iterator = set.iterator();
  40.         while(iterator.hasNext()){
  41.             System.out.println(iterator.next());
  42.         }
  43.     }

面试题

  1. public void test(){
  2.         HashSet set = new HashSet();
  3.         Person p1 = new Person(1001,"AA");
  4.         Person p2 = new Person(1002,"BB");
  6.         set.add(p1);
  7.         set.add(p2);
  8.         System.out.println(set);//[Person{id=1002, name='BB'}, Person{id=1001, name='AA'}]
  10.         p1.name = "CC";//赋值后，位置未改变
  11.         set.remove(p1);//remove之前先根据哈希值判断p1是否存在，equals判断不存在，移除失败
  12.         System.out.println(set);//[Person{id=1002, name='BB'}, Person{id=1001, name='CC'}]
  13.         set.add(new Person(1001,"CC"));//根据哈希值计算位置，跟p1位置不同
  14.         System.out.println(set);//[Person{id=1002, name='BB'}, Person{id=1001, name='CC'}, Person{id=1001, name='CC'}]
  15.         set.add(new Person(1001,"AA"));;//根据哈希值计算位置，跟p1位置相同，但equals相同，通过链表插入
  16.         System.out.println(set);
  17.     //[Person{id=1002, name='BB'}, Person{id=1001, name='CC'}, Person{id=1001, name='CC'}, Person{id=1001, name='AA'}]
  19.     }

image.png