Map

HashMap也是懒加载

红黑树特点

1.根节点为黑色，所有节点都是红色或者黑色

2.相邻节点不能为红色

3.从任意一个节点出发到叶子节点黑色节点数量相同

4.所有叶子节点都是黑色并且为null

二叉树：可能退化为链表

AVL树（平衡二叉树）：高度平衡需要更多次的旋转

旋转 or 染色

1.获取key的hash值（hashcode + 扰动计算）

2.分三种情况插入

hash槽为空 => 直接插入
不为空且存在key相同的节点
- 比较第一个节点的key值是否相同（equals），相同 => 覆盖原来的值
- 遍历链表查看是否有key相同的节点直到next为null
不为空且不存在key相同的节点：new一个节点放到最后 => 判断是否树化

3.判断是否需要扩容

4.返回旧节点的value或者null

1.取模的时候位运算

2.扩容因子是0.75,扩容后大小为整数

3.扩容rehash的时候能快速移动链表中的节点

因为在hash函数服从泊松分布的情况下一个链表长度达到8的概率为百万分之一，所以转红黑树只是一种兜底策略

避免过小的因子：浪费空间

避免过大的因子：造成过多的hash冲突

0.75跟4的幂相乘为整数

rehash速度更快：如果 hash & oldCap != 0 ，新位置就是旧位置+旧容量，否则新位置为原来的位置

头插更改为尾插