Set接口和常用方法

Set接口基本介绍

1. 无序（添加和取出顺序不一样），没有索引
2. 不允许重复元素，所以最多包含一个null

Set接口的常用方法和List一样，Set接口也是Collection的子接口，因此，常用方法和Collection接口一样

Set接口的遍历方式

同Collection的遍历方式一样，因为Set接口是Collection接口的子接口

1. 可以使用迭代器
2. 增强for
3. 不能使用索引的方式来获取，（即不能使用普通for循环）

Set接口实现类-HashSet

HashSet的全面说明

1. HashSet实现了Set接口
2. HashSet实际上是HashMap

 

1. 可以存放null值，但是只能有一个null
2. HashSet不保证元素是有序的，取决于hash后，在确定索引的结果
3. 不能有重复元素/对象

HashSet底层机制说明

HashSet底层是HashMap,HashMap底层是（数组+链表+红黑树）

1. HashSet底层是HashMap
2. 添加一个元素，先得到hash值 会转成->索引值
3. 找到存储数据表table，看这个索引位置是否已经存放的有元素
4. 如果没有，直接加入
5. 如果有，调用equals比较，如果相同，就放弃添加，如果不相同，则以链表添加在最后
6. 在Java8中，如果一条链表的元素个数超过TREEIFY_THRESHOLD（默认是8），并且table的大小>=MIN_TREELFY_CAPACITY（默认64），就会进行树化（红黑树）

分析HashSet的扩容和转成红黑树机制

1. HashSet底层是HashMap，第一次添加时，table数组扩容到16*加载因子（loadFactor）是0.75=12
2. r如果table数组使用到了临界值12，就会扩容到16*2=32，新的临界值就是32*0.75=24，就会扩容到32*2=64，以此类推
3. 在Java8中，如果一条链表的元素个数到达TREEIFY_THRSHOLD（默认是8），并且table的大小>=MIN_TREELFY_CAPACITY（默认64），就会进行树化（红黑树），否则仍然采用数组扩容机制

Set接口实现类-LinkedHashSet  -->（HashSet子类）

LinkedHashSet的全面说明

1. LinkedHashSet是一个HashSet的子类
2. LinkedHashSet加入元素/数据的顺序和取出顺序是一致的
3. LinkedHashSet底层维护的是一个LinkedHashMap（是HashMap的子类），底层维护了一个 数组+双向链表
4. LinkedHashSet根据元素的hashCode值来决定元素的储存位置，同时使用链表维护元素的次序，这使得元素看起来是以插入顺序保存的
5. LinkedHashSet 不允许添重复元素

说明

1. 在LinkedHashSet中维护了一个hash表和双向链表(LinkedHashSet有head和tail)
2. 每个节点有before和after属性，这样可以形成双向链表
3. 在添加一个元素时，先求hash值，再求索引，确定该元素在table的位置，然后将添加的元素加入到双向链表中（如果已经存在，不添加[原则和hashSet一样])

//示意代码

Tail.next = newElement;

newElement = tail;

Tail = newElement;

      4.这样的话，我们遍历LinkedHashSet也能确保插入顺序和遍历顺序一致

//1、LinkedHashSet的加入元素/数据顺序 和 取出元素/数据顺序一致
//2、LinkedHashSet底层维护的是一个LinkedHashMap（是HashMap的子类)
//3、LinkedHashSet底层结构（数组table+双向链表）
//4、添加第一次时，直接将数组table扩容到16，存放的节点类型是LinkedHashMap$Entry
//5、数组是HashMap$node[]存放的元素/数据 是LinkedHashMap$Entry类型