【Java】集合（二）Set

1.Set接口基本介绍

无序:存取顺序不一致
不重复:可以去除重复
无索引:没有带索引的方法，所以不能使用普通for循环遍历，也不能通过索引来获取元素

2.Set集合的实现类

HashSet:无序、不重复、无索引
LinkedHashSet: 有序、不重复、无索引
TreeSet: 可排序、不重复、无索引

3.Set接口中的常用方法

1)add:添加单个元素

2)remove:删除指定元素

3)contains:查找元素是否存在

4) size:获取元素个数

5)isEmpty:判断是否为空

6)clear:清空

7)addAll添加多个元素

8) containsAll:查找多个元素是否都存在

9) removeAll: 删除多个元素

4.HashSet

HashSet的全面说明

1）HashSet 的实现是依赖于HashMap的，HashSet 的值都是存储在HashMap中的。

2）可以存放null值，但是只能有一个

3）不保证元素是有序的，取决于hash后，再确定索引的结果

4）不能重复对象

HsahSet底层原理

1）HashSet 底层是数组+链表+红黑树

2）添加一个元素时，先得到哈希值值-会转成-> 索引值（int index=(数组长度-1)&哈希值）

3）找到存储数据表table，看这个索引位置是否已经存放的有元素

4）如果没有，直接加入

5）如果有，调用 equals 比较，如果相同，就放弃添加，如果不相同，则添加到最后在

6）Java8中,如果一条链表的元素个数到达 TREEIFY THRESHOLD(默认是 8)，并且table的大小 >=MIN TREEIFY CAPACITY(默认64），就会进行树化(红黑树)

HashSet的扩容机制

1）HashSet底层是HashMap,第一次添加时，table 数组扩容到 16，临界值(threshold)是 16*加载因子loadFactor)是0.75 = 12

2）如果table 数组使用到了临界值 12,就会扩容到 16 * 2 = 32,新的临界值就是32*0.75 = 24,依次类推

3）在Java8中,如果一条链表的元素个数到达 TREEIFY THRESHOLD(默认是 8)并且table的大小 >=MIN TREEIFY CAPACITY(默认64)就会进行树化(红黑树),否则仍然采用数组扩容机制

5.LinkedHashSet

LinkedHashSet的全面说明

1）LinkedHashSet是HashSet的子类

2）LinkedHashSet底层是一个LinkedHashMap,底层维护了一个数组+双向链表

3）LinkedHashSet根据元素的hashCode值来决定元素的存储位置，同时使用链表维护元素的次序，这使得元素看起来是以插入顺序保存的。

4）LinkedHashSet不允许重复元素

LinkedHashSet的底层机制

1)在LinkedHastSet 中维护了一个hash表和双向链表( LinkedHashSet 有 head 和 tail )

2)每一个节点有 pre 和 next 属性,这样可以形成双向链表

3)在添加一个元素时，先求hash值，在求索引，确定该元素在hashtable的位置，然后将添加的元素加入到双向链表(如果已经存在，不添加[原则和hashset一样])

tail.next = newElement // 简单指定
newElement.pre = tail

tail = newEelment;
4)这样的话，我们遍历LinkedHashSet 也能确保插入顺序和遍历顺序一致

6.TreeSet

TreeSet集合的特点

可排序、不重复、无索引
底层基于红黑树实现排序，增删改查性能较好

TreeSet集合的自定义排序规则
TreeSet集合存储自定义类型的对象时，必须指定排序规则，支持如下两种方式来指定比较规则。
方式一
让自定义的类(如学生类)实现Comparable接口，重写里面的compareTo方法来指定比较规则。
方式二
通过调用TreeSet集合有参数构造器，可以设置Comparator对象 (比较器对象，用于指定比较规则）
public TreeSet(Comparator<? super E> comparator)
两种方式中，排序规则:
根据compareTo方法的返回值进行指定元素位置如

如果返回值为负数，表示当前存入的元素是较小值，存左边

如果返回值为0，表示当前存入的元素相等，不存

如果返回值为正数，表示当前存入的元素是较大值，存右边

注意: 如果类本身有实现Comparable接口，TreeSet集合同时也自带比较器，默认使用集合自带的比较器排序