什么是哈希表：
? ? ? ? ? ? ? ? 哈希表就是数组加链表
? ? ? ? ? ? ? ? 或者是数组加红黑树
数组的特点：查询快，增删慢（根据索引值获取元素快）
链表的特点：查询慢，增删快
红黑树的特点：查询和增删都比较快
接下来我们来举例了解一个什么时候哈希表是数组加链表，什么时候哈希表是数组加红黑树。
一.关于Set集合中我们知道，Set集合的特点是：没有索引值，元素不能重复。这里我们主要说一下关于Set集合下的HashSet集合，因为它的底层数据结构就是哈希表。
1.我们先来创建一个HashSet集合
?这里新建了一个String类型的HashSet集合，在集合中添加了三个元素，我们打断点来看一下底层源码是怎么实现这个新增的。
2.进来后这里，我们实现的新增元素，所以这里的泛型e就是我们刚刚新增的zz，
3.再进来，这里的key就是zz,putVal方法中有五个参数，第一个参数是一个hash方法的返回值，我们再点进去看这个hash方法是怎么处理我们的zz的。
?4.这里有一个三元运算符，首先判断我们的zz是否为null，很明显，zz不为null，所以就返回(h = key.hashCode()) ^ (h >>> 16)，这里的hashCode可以计算元素的地址值，仔细看这个方法返回的是一个int类型的值，获得这个值后赋给了h,然后将h右移了16位，与h再进行异或，然后将结果返回交给我们上一步中的hash(key)。（这里其实就是计算了哈希值）。
5.继续点进来，putVal中第一个参数就是我们刚刚计算出来的哈希值，第二个Value就是zz。
下面是一个Node类型的数组，对这个数组进行了一个if判断，判断一下这个数组是否有空间，为null就是没有空间，不为null就是有空间，没有空间就需要创建空间。这里我们的table为null就要进到resize方法。
?6.这里将table赋值给了oldTab,下面的判断oldTable为true,将0赋给oldCap,意思就是旧空间长度为0，下面的if就为false，就执行else部分。
?7.这里新的空间为16。（数组长度为16）
?8.这里就新建了一个Node类型的数组，长度为16，我们看一下这个Node是什么
?9.从右上角我们看见发现，Node是一个静态成员内部类。从下面成员变量Node<K,V> next;中可以知道，这是一个单项链表。最开始所说的哈希表是数组加链表，那么链表就是在这里体现的。
?10.这里n的值就是我们刚刚创建的数组长度16，数组创建好了，接下来就应该确定zz的索引值位置，那么zz的索引值位置是怎么确定的呢，我们接着往下运行。
?11.这里判断tab[i]的位置的值是否为null，等于null就是该位置没有元素，没有元素我们就可以将我们新增的元素新增进去，但是不为null就是该位置有元素，就不能直接新增元素。这个索引值i的值根据我们刚刚的数组长度n和之前计算出来的哈希值去确定的。
12.这里就是判断元素是否重复的规则。如果不重复就新增到该元素索引值的最后面，如果重复则不新增。
?二.这里我们再新建一个Integer类型的HashSet集合
?从图中我们可以知道，什么时候链表会转为红黑树。
?总结：
HashSet:无序：新增顺序和取出顺序不一定一致
- ? ? ??底层数据结构：哈希表（数组加链表/红黑树）
- ? ? ? 什么类型的数组：java.util.HashMap$Node(表示一个单项链表）
- ? ? ? 数组长度是多少：16
- ? ? ? 如何判断新增的两个元素是否重复：
- ? ? ? 规则:比较两个对象的哈希值&&（地址值相同||equals相同）
- ? ? ? 新增过程：
- ?? a.计算新增元素的哈希值
- ? ?b.（假设数组已经创建出来），通过hash%数组长度，获取索引值。
- ? ?c.如果该位置为null：则直接新增
- ? ?如果该位置不为null：
- ? ? c1.判断该元素是否重复：
- ? ?c11.如果不重复，则新增到该索引值位置链表的最后面
- ? ? c12.如果重复：则不新增
- ? ? ??什么情况下链表会转红黑树：
- 当同一个索引值下元素个数>8,并且数组长度>=64会把"该索引值"下的元素转为红黑树。