一、Set集合
1、Set接口
Set接口继承了Collcetion接口，包含Collcetion中的所有方法。
TreeSet类增加的方法
| 方法 | 功能描述 |
| first() | 返回此Set中当前第一个（最低）元素 |
| last() | 返回此Set中当前最后一个（最高）元素 |
| comparator() | 返回对此Set中的元素进行排序的比较器；如果此Set使用自然顺粗，则返回null |
| headSet(E toElement) | 返回一个新的Set集合，新集合是toElement（不包含）之前的所有对象 |
| subSet(E fromElement,E fromElement) | 返回一个新的Set集合，是fromElement（包含）对象与fromElement（不包含）对象之间的所有对象 |
| tailSet(E fromElement) | 返回一个新的Set集合，新集合包含对象fromElement（包含）之后的所有对象 |
2、Set特点
元素无放入顺序，元素不可重复，重复元素会覆盖掉，（注意：元素虽然无放入顺序，但是元素在set中的位置是有该元素的HashCode决定的，其位置其实是固定的，加入Set 的Object必须定义equals()方法 ，另外list支持for循环，也就是通过下标来遍历，也可以用迭代器，但是set只能用迭代，因为他无序，无法用下标来取得想要的值。）
检索元素效率低下，删除和插入效率高，插入和删除不会引起元素位置改变。
3、HashSet
（1）、简介
HashSet类实现了Set接口，不保证Set的迭代顺序，特别是它不保证该顺序恒久不变。HashSet按Hash算法来存储集合中的元素，因此具有很好的存储和查找性能。底层数据结构是哈希表。
HashSet特点如下：
-
不能保证元素的排列顺序，顺序可能与添加顺序不同，顺序也有可能发生变化
-
HashSet不是同步的，如果多个线程同时访问一个HashSet，假设有两个或者两个以上线程通知修改了HashSet集合时，则必须通过代码来保证其同步
-
集合元素值可以为null
HashMap基于Map接口实现，元素以键值对的方式存储，并且允许使用null。HashMap用Entry数组存储键值对，Entry是一个单向的链表结构，它具有Next指针，可以连接下一个Entry实体，以此来解决Hash冲突的问题。HashMap继承自AbstractMap，而AbstractMap又继承Map接口
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {HashMap基本属性
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //默认初始大小为16
static final int MAXIMUM_CAPACITY = 1 << 30; //默认负载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f; //默认负载因子为0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f; //装载因子用来衡量HashMap满的程度，表示当map集合中存储的数据达到当前数组大小的75%则需要进行扩容
static final int TREEIFY_THRESHOLD = 8; //链表转红黑树边界?
static final int UNTREEIFY_THRESHOLD = 6; //红黑树转离链表边界
transient Node<K,V>[] table; //哈希桶数组?
transient int size; //实际存储的元素个数
int threshold 阈值 = table.length * loadFactor //当map里面的数据大于这个threshold就会进行扩容数组存储区间是连续的，占用内存严重，故空间复杂的很大。但数组的二分查找时间复杂度小，为O(1)；数组的特点是：寻址容易，插入和删除困难；
链表存储区间离散，占用内存比较宽松，故空间复杂度很小，但时间复杂度很大，达O（N）。链表的特点是：寻址困难，插入和删除容易。
（2）、HashSet底层实现
创建HashSet实例对象
public class HashTest {
? ? public static void main(String[] args) {
? ? ? ? HashSet hashSet = new HashSet();
? ? ? ? hashSet.add("jack");
? ? ? ? hashSet.add("lucy");
? ? ? ? hashSet.add("john");
? ? ? ? System.out.println("hashset="+hashSet);
? ? }
}先调用HashSet构造器
调用add()
PERSENT是HashSet中的一个Object对象，add()方法中起占位的作用
执行Put()，该方法会执行hash(key)方法，得到key对应的hash值，但此hash值并不完全等价于hashcode值
如果key==null那么就将键值对存入索引为0的桶内，如果不为空则计算key的hashcode值，将h无符号右移16位进行异或运算得到hash值（>>(带符号右移) & >>>(无符号右移)）。之所以右移16位是为了减少碰撞，进一步降低hash冲突的几率。int类型的数值是4个字节的，右移16位异或可以同时保留高16位于低16位的特征。
putVal()方法
定义辅助变量
table就是HashMap的一个数组，类型是Node[]；
如果table数组为空或者table数组长度为0，则赋值resize的长度给变量n；其中有一个resize()方法
由于table为null，所以oldcap为0
此时oldcap为0，进入if判断，newCap赋值为16，并计算临界值，到底临界值就扩容，到达数组大小的0.75倍时就进行扩容，比如当前cap=16，则到12个元素进行扩容
这里有两个常量，默认初始容量和默认加载因子
当使用量接近数组容量75%时，数组中还剩下25%的空间，平均来看就是10个桶有四分之一是空的，当向map中存放数据时，碰撞概率是75%，但有25%的空闲空间，发生hash碰撞的概率还处在一个可以接受的范围内，所以如果扩容因子越大，碰撞的概率也就越大，效率也就越低，
如果负载因子是0.9，则平均来看10个桶中之有一个是空的，碰撞概率90%，几乎可以认为会发生碰撞。
如果负载因子是0.5，则平均来看10个桶中一半都是空的，当数组中的元素达到了一半就开始扩容，既然填充的元素少了，Hash冲突也会减少，底层链表或者红黑树的高度就会降低，但查询效率会增加。
现在创建newTab，newTab的容量就是16，并且把newTab赋值给Table
此时返回putVal()方法，根据key得到的hash值（(n - 1) & hash计算hash值，n即为tab.length），计算该key存到放table表的那个索引位置，并把这个位置的对象赋值给p
，如果p为空，表示还没有存放过元素，就创建一个Node
Node中存放hash, key, value, next四个值
modCount计数器改变，记录修改次数，判断如果长度大于12，则进行扩容，afterNodeInsertion方法为空方法，最后返回null
afterNodeInsertion()方法
map.put(e, PRESENT)返回一个null，说明map集合里存放成功，否则就表示添加的元素已经有了
当再次添加时，如果当前索引位置对应的链表的第一个元素和准备添加的key的hash值一样，并且二者中任意一个 ①准备加入的key和p指向的Node结点的key是同一个对象 ②P指向的Node结点的key的equals()和准备加入的key比较后相同 则就不能加入；再判断p是不是一棵红黑树，如果是则调用putTreeVal()来进行添加；如果table对应索引位置已经是一个链表，就使用for循环中的循环比较机制，即添加进来的元素以此与已添加的链表元素对比，如过有相同的则返回，否则就添加到当前链表之后，注意添加到链表后判断该链表是否到达8个结点，如果达到则调用treefyBin()对当前链表进行树化，在进行树化时再判断table.length <= 64，达不到64时先扩容，到64后再进行树化
4、LinkedHashSet
（1）、简介
LinkedHashSet是HashSet的子类，底层是LinkedHashMap实现，维护了一个数组+双向链表，LinkedHashSet不允许重复添加元素，链表保证了元素的顺序与存储顺序一致，哈希表保证了元素的唯一性。线程不安全，效率高。
LinkedHashSet中维护了一个hash表和双向链表，每一个节点中有pre和next属性，这样可以形成双向链表，在添加一个元素时，先求hash值，再求索引，确定该元素在hashtable中的位置，然后将添加的元素加入到双向链表（如果已经存在则不添加）
（2）、LinkedHashSet底层机制
创建LinkedHashSet实例对象
?
public class LinkedHashSet {
? ? public static void main(String[] args) {
? ? ? ? Set set = new java.util.LinkedHashSet();
? ? ? ? set.add("john");
? ? ? ? set.add(412);
? ? ? ? set.add(412);
? ? ? ? set.add(new Customer("王宏",1250023));
? ? ? ? System.out.println("set="+set);
? ? }
}
class Customer{
? ? private String name;
? ? private int sno;
? ? public Customer(String name, int sno) {
? ? ? ? this.name = name;
? ? ? ? this.sno = sno;
? ? }
? ? @Override
? ? public String toString() {
? ? ? ? return "Customer{" +
? ? ? ? ? ? ? ? "name='" + name + '\'' +
? ? ? ? ? ? ? ? ", sno=" + sno +
? ? ? ? ? ? ? ? '}';
? ? }
}LinkedHashSet底层维护的是一个LinkedHashMap，
LinkedHashSet底层是一个数组+双向链表，第一次添加时，直接将数组table扩容到16，存放的结点类型是LinkedHashMap$Entry；数组是HashMap￥Node类型，里面存放的是LinkedHashMap$Entry类型，
before, after为每一个结点的属性，前指针和下一指针
对整数型还是先进行装箱
还是执行add方法
执行put方法计算hash值，然后执行putval方法
添加完第一个元素后可以看到head指向元素本身，下一个元素为空
多次添加元素后可以看到，添加元素的前指针指向前一个元素，下一指针为空
5、TreeSet
TreeSet类不仅实现了Set接口，还实现了java.util.SortedSet接口，因此，TreeSet类实现的Set集合在遍历集合时按照自然顺序递增排序，也可以按照指定比较器递增排序
底层数据结构采用二叉树来实现，元素唯一且已经排好序；唯一性同样需要重写hashCode和equals()方法，二叉树结构保证了元素的有序性。根据构造方法不同，分为自然排序（无参构造）和比较器排序（有参构造），自然排序要求元素必须实现Compareable接口，并重写里面的compareTo()方法，元素通过比较返回的int值来判断排序序列，返回0说明两个对象相同，不需要存储；比较器排需要在TreeSet初始化是时候传入一个实现Comparator接口的比较器对象，或者采用匿名内部类的方式new一个Comparator对象，重写里面的compare()方法。
底层数据结构是红黑树。(唯一，有序)
1. 如何保证元素排序的呢?
自然排序
比较器排序
2.如何保证元素唯一性的呢?
根据比较的返回值是否是0来决定