Set集合(Java) 及底层原理_set集合的底层原理

SET<E>是一个接口，添加的元素是无序的：添加数据的顺序和获取出的数据顺序不一致；不重复，无索引。

实现类：

1.HashSet：无序不重复无索引

2.LinkedHashSet：有序不重复无索引

3.TreeSet：排序不重复无索引

一、HashSet

//创建一个Set集合对象
        Set<Integer> set;
        set = new HashSet<>(); //创建了一个HashSet集合对象    无序不重复无索引
        set.add(66);set.add(34);set.add(54);set.add(16);set.add(87);set.add(435);set.add(66);
        System.out.println(set);  //[16, 66, 34, 435, 54, 87]
        //注意：这里的无序只会无序一次，定下来以后就不改变

 HashSet集合底层原理

哈希值是一个int类型的数值，Java中每个对象都有一个哈希值

Java中的所有对象，都可以调用OBject类提供的hashCode方法，返回该对象自己的哈希值

同一个对象多次调用hashCode()方法返回的哈希值是相同的

不同的对象他们的哈希值一般不相同，但也有可能会相同（哈希碰撞）

--------------------------------------------------------------------

HashSet底层原理是基于哈希表实现的，哈希表是一种增删改查数据性能都比较好的数据结构，JDK8开始，哈希表是由数组+链表+红黑树组成的。

JDK8之前哈希表：数组＋链表

创建HashSet集合对象并且第一次添加数据的时候会创建一个默认长度16的数组，默认加载因子0.75，数组名table，然后使用元素的哈希值对数组的长度求余计算出存入的位置，判断当前位置是否为null，如果是就直接存入，如果不为null，就调用equals比较，如果相等就不存，如果不相等就JDK8之前：把新元素存入数组，占老元素位置，老元素挂下面；JDK8之后：直接把新元素挂老元素下面。

一旦占了12个，数组会扩容，达到优化性能的目的，JDK8之后，当链表长度超过8，且数组长度>=64时，自动将链表转换成红黑树。

注意：HashSet集合默认不能对内容一样的两个不同对象去重

那么如何实现对内容一样的两个不同对象去重复呢？

必须通过重写对象的hashCode()和equals()方法：

equals：只要两个对象内容一样就返回true。

hashCode：只要两个对象内容一样，哈希值就一样。

二、LinkedHashSet

//创建一个Set集合对象
        Set<Integer> set;
        set = new LinkedHashSet<>(); //创建了一个LinkedHashSet集合对象    有序不重复无索引
        set.add(66);set.add(34);set.add(54);set.add(16);set.add(87);set.add(435);set.add(66);
        System.out.println(set);  //[66, 34, 54, 16, 87, 435]

  LinkedHashSet集合底层原理

依然是基于哈希表实现的，但是每一个元素都额外多练一个双链表的机制记录它前后元素的位置。

三、TreeSet

//创建一个Set集合对象
        Set<Integer> set;
        set = new TreeSet<>(); //创建了一个TreeSet集合对象    排序不重复无索引
        set.add(66);set.add(34);set.add(54);set.add(16);set.add(87);set.add(435);set.add(66);
        System.out.println(set);  //[16, 34, 54, 66, 87, 435]

注意：Set要用到的常用方法，基本上就是Collection提供的

TreeSet底层原理

对于数值类型，默认按照数值本身的大小进行升序排序

对于字符串类型，默认按照首字符的编号升序排序

对于自定义类型，默认无法直接排序，必须指定排序规则：

1.让自定义的类实现Comparable接口，重写compareTo方法来制定比较规则：

2.通过调用TreeSet集合有参构造器，可以设置Comparator对象：