Set接口底层实现类

一、Set接口继承关系

存储的数据特点：无序的、不可重复的元素

|—-Set接口：存储无序的、不可重复的数据 –>高中讲的“集合”

  • |—-HashSet：作为Set接口的主要实现类；线程不安全的；可以存储null值
  • |—-LinkedHashSet：作为HashSet的子类；遍历其内部数据时，可以按照添加的顺序遍历在添加数据的同时，每个数据还维护了两个引用，记录此数据前一个数据和后一个数据。 对于频繁的遍历操作，LinkedHashSet效率高于HashSet.
  • |—-TreeSet：可以照添加对象的指定属性，进行排序。

二、HashSet

1.继承情况

可以看到是直接实现了Set接口，和间接继承了Collection接口

2.创建HashSet

debug跟进源代码

可以看到空参构造器里new了一个HashMap出来

59565709297

而HashMap初始化了一个加载因子的常量，这里由于是map内容不多做细讲

实际上HashSet实现Set接口，由哈希表（实际上是一个HashMap实例）支持。它不保证set 的迭代顺序；特别是它不保证该顺序恒久不变，此类允许使用null元素。

在HashSet中，元素都存到HashMap键值对的Key上面，而Value时有一个统一的值private static final Object PRESENT = new Object();，(定义一个虚拟的Object对象作为HashMap的value，将此对象定义为static final。) 在添加数据时就能观察到。

3.添加数据

跟进 首先是一个自动装箱

而PRESENT就是刚才提及到的固定的value值 实现了双列变单列
private static final Object PRESENT = new Object();

接下来的put就是map的操作了

4.不可重复性和无序性

HashSet的俩大特点

1. 无序性：不等于随机性。存储的数据在底层数组中并非照数组索引的顺序添加，而是根据数据的哈希值决定的。
    2. 不可重复性：保证添加的元素照equals()判断时，不能返回true.即：相同的元素只能添加一个。

在进行测试过程中 我发现避免不了去到map的源码，由于太过复杂 尽量用大白话说明白，map会单独出一篇

在jdk7和之前 底层使用的是数组加链表，在jdk8后使用的是数组加链表加红黑树。

因为我们知道map的key是不允许的重复的，如果有重复的key值就会把map的key和value进行更新操作，这一来就说的通了，HashSet就是限制了map的功能，让map的value值固定为常量，只使用key去操作，所以说HashSet不允许有重复的值，其实也是这个新的值把原来的值给替换掉了

而无序性，要重存放的方式说起。（注意，存进HashSet的对象一定要重写HashCode和equals方法）

我们向HashSet中添加元素a,首先调用元素a所在类的hashCode()方法，计算元素a的哈希值，
此哈希值接着通过某种算法计算出在HashSet底层数组中的存放位置（即为：索引位置，判断
数组此位置上是否已经元素）：

此时有俩种情况：

​ 1.如果此位置上没其他元素，则元素a添加成功。 —>插入成功情况1
2.如果此位置上其他元素b(或以链表形式存在的多个元素，则比较元素a与元素b的hash值：

此时又有俩种情况：

​ 1.如果hash值不相同，则元素a添加成功。—>成功情况2
2.如果hash值相同，进而需要调用元素a所在类的equals()方法：

此时还是有俩种情况：

​ 1.equals()返回true,元素a添加失败
2.equals()返回false,则元素a添加成功。—>成功情况3

​ 对于添加成功的情况2和情况3而言：元素a 与已经存在指定索引位置上数据以链表的方式存储。

​

（链表指向区别↓）

jdk 7 :元素a放到数组中，指向原来的元素。
jdk 8 :原来的元素在数组中，指向元素a

此时同学们肯定会有疑问，如果HashCode相同难道会出现equals不同的情况嘛？（还真会待会贴出优秀代码）

由于在数组 和 链表 和 红黑树 的数据结构有点抽象 下面几副图可以形象看到HashSet添加时全过程

情况2：

情况3：

这里没有用到红黑树，是因为加入红黑树是让遍历等操作速度变快，具体的方式为，在数组某一个位置上的链表的层数到8层或总数量多于64个时，链表重新打散，改为使用树结构，当然树结构的头还是数组，变成一颗颗倒着的树。

5.添加代码

class Person{
        Integer num;
        String name;

        public Person(Integer num, String name) {
            this.num = num;
            this.name = name;
        }

        @Override
        public String toString() {
            return "Person{" +
                    "num=" + num +
                    ", name='" + name + '\'' +
                    '}';
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (!(o instanceof Person)) return false;
            Person person = (Person) o;
            return Objects.equals(num, person.num) &&
                    Objects.equals(name, person.name);
        }

        @Override
        public int hashCode() {
            return Objects.hash(num, name);
        }
    }

    @Test
    public void test1(){
        HashSet set = new HashSet();
        Person p1 = new Person(1002,"AA");
        Person p2 = new Person(1002,"BB");

        set.add(p1);
        set.add(p2);
        System.out.println(set);

        p1.name = "CC";
        set.remove(p1);
        System.out.println(set);
        set.add(new Person(1002,"CC"));
        System.out.println(set);
        set.add(new Person(1002,"AA"));
        System.out.println(set);
    }

运行test1中代码结果为：

[Person{num=1002, name='AA'}, Person{num=1002, name='BB'}]
[Person{num=1002, name='CC'}, Person{num=1002, name='BB'}]
[Person{num=1002, name='CC'}, Person{num=1002, name='BB'}, Person{num=1002, name='CC'}]
[Person{num=1002, name='CC'}, Person{num=1002, name='BB'}, Person{num=1002, name='CC'}, Person{num=1002, name='AA'}]

是不是很诡异？其实归根结底还是那三种情况

三、LinkedHashSet

1.继承情况

2.优劣

LinkedHashSet 与 HashSet 区别在于 LinkedHashSet 遍历其内部数据时，可以按照添加的顺序遍历，在添加数据的同时，每个数据还维护了两个引用，记录此数据前一个数据和后一个数据。

特性就剩不可重复性了

对于频繁的遍历操作，LinkedHashSet效率高于HashSet

四、TreeSet

1.继承情况

TreeSet不太一样，它是可以将数据按照一定的排列顺序进行输出。有俩种方式（定制排序，自然排序）

2.自然排序

自然排序就是对象实现了Comparable接口

我们知道，Set是无序的，但是用TreeSet的数据就是有序的，那基本数据类型为什么存进去就会变有序呢？

其实这里有一个自动装箱的过程在Integer中就实现了这个接口

public final class Integer extends Number implements Comparable<Integer> {
    
    
 在里面重写了compareTo
     
public int compareTo(Integer anotherInteger) {
        return compare(this.value, anotherInteger.value);
    }
     
public static int compare(int x, int y) {
        return (x < y) ? -1 : ((x == y) ? 0 : 1);
    }
    
以后要想放在TreeSet实现排序的对象 先要自己重写compareTo方法，用自己的排列方式才能生效

3.定制排序

往往在很多时候，自然排序根本不能用，因为不能去更改源代码，所以有另一种方法，帮助我们定制排序的顺序

这种方法就是给TreeSet构造器中给一个Comparator对象，在Comparator对象中重写compare方法，定制自己需要的排列规则

@Test
   public void test2(){
       Comparator com = new Comparator() {
           //照年龄从小到大排列
           @Override
           public int compare(Object o1, Object o2) {
               if(o1 instanceof User && o2 instanceof User){
                   User u1 = (User)o1;
                   User u2 = (User)o2;
                   return Integer.compare(u1.getAge(),u2.getAge());
               }else{
                   throw new RuntimeException("输入的数据类型不匹配");
               }
           }
       };

       TreeSet set = new TreeSet(com);
       set.add(new User("Tom",12));
       set.add(new User("Jerry",32));
       set.add(new User("Jim",2));
       set.add(new User("Mike",65));
       set.add(new User("Mary",33));
       set.add(new User("Jack",33));
       set.add(new User("Jack",56));


       Iterator iterator = set.iterator();
       while(iterator.hasNext()){
           System.out.println(iterator.next());
       }
   }

一般来说如果某个对象不需要经常使用排序，则使用定制排序就行，因为可以使用匿名内部类的方式，一次性的排序，而使用自然排序则是一直绑定着排序规则，不灵活。