Set系列集合

1、Set系列集合的特点
·无序、不重复、无索引
·Set集合的方法上基本上与Collection(所有集合的顶级父类)的API一致

2、Set集合的实现类特点
·HashSet：无序、不重复、无索引
·LinkedHashSet：有序、不重复、无索引
·TreeSet：可排序、不重复、无索引

哈希表

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

哈希值

·根据hashCode方法算出来的int类型的整数，计算公式：（数组长度 - 1） & 哈希值
·该方法定义在Object类中，所有对象都可以调用，默认使用地址值进行计算
·与一般情况下，会重写hashCode方法，利用对象内部的属性值计算哈希值

对象的哈希值特点
·如果没有重写hashCode方法，不同对象计算出的哈希值是不同的
·如果已经重写hashCode方法，不同对象只要属性值相同，计算出的哈希值就是一样的
·在小部分情况下，不同的属性值或者不同的地址值计算出来的哈希值也有可能一样(哈希碰撞，这名字真帅哈哈)

HashSet

底层原理

·HashSet：无序、不重复、无索引
·HashSet集合底层采取哈希表存储数据
·哈希表是一种对于增删改查数据性能都较好的结构

添加元素底层原理

1、创建一个默认长度16，默认加载因子(扩容)0.75的数组，数组名table
2、根据元素的哈希值跟数组长度计算出应存入的位置
3、判断当前位置是否为null，如果是则直接存入
4、如果位置不为null，表示有元素，则调用equals方法比较属性值
5、如果一样则不存(Set不重复)，不一样则存入数据，形成链表
JDK8以前：新元素存入数组，老元素挂在新元素的下面，
JDK8以后：新元素直接挂在老元素下面

当添加元素里面有16*0.75=12的元素之后就会扩容，扩容为原来的两倍 当链表的长度大于8并且数组长度大于等于64的时候，链表就会变成红黑树进行存储
三中结构(数组、链表、红黑树)可以同时存在 如果集合中存储的是自定义对象，必须重写hashCode和equals方法

HashSet的三个问题

HashSet为什么存和取的顺序不一样？
因为存值的时候不是按照顺序存的，放到链表的位置是不固定的，红黑树的方式存储也是一样不固定的。而取是按照顺序取的。无序是由于哈希值影响的

HashSet为什么没有索引？
还是因为有链表和红黑树的存在，1索引下可能是一个链表或者红黑树，1索引下的那么多值都是1索引就没有意义了，所以干脆不设索引

HashSet是利用什么机制保证数据去重的？
利用HashCode方法和equals方法，HashCode获取哈希值，确定当前元素在数组的哪个位置，再利用equals比较数据的属性值就可以判断值是否相同。
如果存储的是自定义对象必须重写这两个方法，不然不能实现去重的效果！！！

LinkedHashSet(HashSet的子类)

底层原理

·LinkedHashSet：有序、不重复、无索引
·这里的有序指的是保证存储和取出的元素顺序一致
·原理：底层数据结构依然是哈希表，只是每个元素又额外多了一个双链表的机制记录存储的顺序，于是就可以保持存储一致，遍历的是双向链表

TreeSet

特点

·不重复、无索引、可排序
·可可排序：按照元素的默认规则(由小到大)排序
·TressSet集合底层是基于红黑树的数据结构实现排序的，增删改查性能都较好

默认排序规则

·对于数值类型：Integer，Double，默认按照从小到大的顺序进行排序
·对于字符、字符串类型：按照字符在ASCII码中的数字升序进行排序，多个字符就是从左到右依次比较，只要比对出来就结束不会再看后面。

自定义对象排序

方式一(自然排序)

自定义类要继承Comparable接口，泛型就是自定义类

之后就重写接口中的方法，编写我们自定义排序的代码
距离：

@Override
public int compareTo(Student o){
    //指定排序的规则
    //只看年龄。我想要按照年龄的升序进行排序
    return this.getAge() - o.getAge();

    /*
        this:表示当前要添加的元素
        o:表示已经在红黑树里面的元素

        返回值：
            负数：认为要添加的元素是小的，存左边
            正数：认为要添加的元素是大的，存右边
            0：认为要添加的元素已经存在，直接舍弃不存
    */
}

方式二(Comparator比较器)

比较器排序：创建TreeSet对象的时候，传递比较器Comparator制定规则

举例：

//在创建对象的时候就可以使用函数式接口把Comparator实现出来
TreeSet<String> ts = new TreeSet<>(new Comparator<String>() {
    @Override
    public int compare(String o1, String o2) {
        //自定义规则
        //按照长度排序
        int i = o1.length() - o2.length();
        //如果一样长则按照首字母排序
        i = i == 0 ? o1.compareTo(o2) : i;
        return i;
    }
}) 

//使用lamba表达式化简
    TreeSet<String> ts = new TreeSet<>((o1 , o2) -> {
        //自定义规则
        //按照长度排序
        int i = o1.length() - o2.length();
        //如果一样长则按照首字母排序
        i = i == 0 ? o1.compareTo(o2) : i;
        return i;
    });