2021-09-29 HashMap与HashSet详解：

如果HashMap初始化的时候没有指定容量，会返回一个空的table数组。 第一次往HashMap中put元素的时候，会使用默认的参数16作为数组的初始化长度；

当HashMap中的元素数量超过 容量*加载因子 时，会进行扩容操作。 容量变为原来的2倍（数学左移一位），HashMap的加载因子默认是0.75；

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 
static final float DEFAULT_LOAD_FACTOR = 0.75f; 

如果已经确定要往HashMap中存储多少数据，那么可以使用重载的构造方法， 在创建时就制定一个具体的合适的初始容量，这样可以减少扩容所产生的开销。 但是大多数情况下加载因子0.75在时间和空间上代价达到了平衡，所以不建议修改。

HashMap底层：是一个Entry数组：transient Node table[] 当存放元素时，首先会根据key的hashCode值找到数据应该保存在table数组的下标位置。

如果数组的位置上没有数据，直接将这个键值对保存在该位置上。

如果数组的位置上已有数据，即发生了哈希冲突/哈希碰撞，也就是两个对象的key的hash值相等， 那么需要通过key的equals方法判断这两个对象是否为同一个对象。

如果是，那么原本存储的value值会被新值替换； 如果不是同一个对象，则采用链地址法，把新的键值对对象保存到旧的键值对对象的next变量中，形成单向链表结构。

查找数据时，首先会根据key的hash值找到数据应该保存在table数组的下标位置，然后通过数组下标快速定位到这个位置上。

① 如果这个位置上什么都没有，则直接返回null。

② 如果这个位置上有键值对对象，并且equals比较为true，则直接将这个键值对对象的value返回。

③ 如果这个位置上有单向链表，那么会拿着key去和单向链表上的每一个节点的key进行equals比较，如果所有equals比较结果都为false，则返回null。

④ 如果其中一个节点的key进行equals比较结果为true，那么此时该节点的value就是我们要找的value，最终返回这个value。

当链表过长时，查询效率会下降，所以JDK8之新增了红黑树作为底层数据结构，如果链表长度超过8并且数组长度>64时，hashMap 会把这个链表转成红黑树来存储（如果数组长度没有超过64会进行扩容）； 当链表长度小于6时红黑树会转回链表。

 static final int TREEIFY_THRESHOLD = 8; 
static final int UNTREEIFY_THRESHOLD = 6; 
static final int MIN_TREEIFY_CAPACITY = 64;

树（Tree）是计算机数据存储的一种结构，因为存储类型和现实生活中的树类似，所以被称为树。 二叉树时最常用的树形结构，每个节点最多能有两个子节点，它的左节点要比父节点小，右节点比父节点大。 它的高度决定了查询的效率。

红黑树是每个节点都带有颜色的二叉树，颜色为红色或黑色。 在二叉树强制的一般要求以外，对于任何有效的红黑树，增加了如下的额外要求：

1、节点是红色或黑色

2、根节点是黑色

3、所有叶子结点都是黑色。

4、每个红色节点的两个子节点都是黑色。（每个叶子结点到根节点的所有路径上不能有两个连续的红色节点）

5、从任一节点到其子树种的每个叶子的所有路径都包含相同数量的黑色节点。（叶子结点到根节点的黑色节点数量，每条路径都相同）

对于红黑树而言，主要包括三大基本操作：左旋，右旋，着色。

HashSet底层由HashMap实现，利用了HashMap的key不能重复的特性，直接将要存储的元素作为key存储到了HashMap中。