HashMap小结

• 1.Hash的理解
• 2.Hash的特点
• 3.HashMap的结构
• 4.HashMap的初始数据
• 5.HashMap的创建时机
• 6.负载因子
• 7.链表转为红黑树条件
• 8.HashMap写入数据的流程
• 9.红黑树的几个原则
• 10.为什么jdk1.8后要引入红黑树
• 11.HashMap的扩容机制
• 12.为什么HashMap使用位移运算进行扩容而不是直接 x2

把任意长度的输入通过hash算法映射为固定长度的输出，输出的内容就是hash值

• 无法倒推出原值
• 原值细微的变化也会导致结果不同，相同的原值计算后的hash值相同
• 效率高，长文本也能快速计算出hash值
• 冲突概率要小(因为hash的原理是将原值大空间转换为小空间输出，所以必定会导致抽屉原理：10个苹果放到9个抽屉里，必定有个抽屉会放入至少两个苹果)

JDK1.8以后，HashMap采用的是数组+链表+红黑树的结构，每个数据单元都是一个node结构，node结构中有key、value、next、hash这四个字段。
next字段是发生hash冲突时，当前桶位中的node与冲突的node形成链表需要用到的字段
hash这个字段的值不是key的hashcode()方法返回值，是经过返回值二次加工得到的（haskcodeg高16位^低16位）

hashmap如果没有指定初始值，散列表的长度默认为16

散列表属于懒加载机制，只有在第一次put数据的时候才加载

HashMap默认的负载因子为0.75，负载因子用来计算表的扩容阈值，比如说默认的长度为16时 扩容阈值就是：16*0.75=12。也就是说每次put数据后都会判断一下目前表的长度是否到达了扩容阈值。
为什么负载因子是0.75而不是1.0或者0.5
为1.0：扩容时需要解决大量冲突，红黑树会变得比较复杂，查询效率会降低
为0.5：负载因子太小，虽然时间效率提升了，但是空间利用率降低了
所以负载因子是0.75的时候，空间利用率比较高，而且避免了相当多的Hash冲突，使得底层的链表或者是红黑树的高度比较低，提升了空间效率。

• 链表长度达到8(就算链表长度达到8，如果数组长度没到64也不会扩容)
• 散列表数组长度达到64

• null节点

计算hashcode值后直接插入

• 非空节点但未链化

新的key值计算的hashcode值找到slot下的node节点，比对key值是否完全相等与node节点，完全相同时就是一个替换操作，不同时就是一个冲突产生了，使用尾插法链接到这个node后就行了

• 链化节点

和上一种情况类似，迭代查找node，然后比对链表上的key和传入的key是否完全一致，一致就是repleace操作，直到链表尾部也没有一致的情况的话就把传来的值包装为新的node加入到链表尾部，检查树化的阈值，到达8了后就调用树化方法，树化操作都在这个方法里完成

• 已转为红黑树节点(此处还需完善)

查找方法同上类似，但是他是
特殊的排序二叉树，底层使用二分查找法进行操作
查询到叶子节点也没有一致的情况就成为当前节点的子节点 具体左右子节点还需要和父节点的hash值比较才能确认
插入后会打破平衡，还需要一个红黑树的平衡算法
查询到一致的情况也是一次repleace操作

• 每一个节点不是红色的就是黑色的。

• 根节点总是黑色的。

• 如果节点是红色的，则他的子节点必须是黑色的（反之不一定成立）

• 从根节点到叶节点或者到空子节点的每条路径，必须包含相同数目的黑色节点。

• 每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]

其中规则4中的空子节点就是说非叶节点可以接子节点的位置，换句话说，就是一个有右子节点的节点（没有左子节点）就有一个空子节点

主要是因为链化现象太严重了，就是失去了链化的意义，如果查找元素是链表最后一个节点，那么查找的效率也是会很低的，需要一个一个链表去比对值，时间复杂度就变成O(n)了

当存入数据后可能会触发扩容机制，hashmap中有个记录当前数据量的字段，这个字段到达扩容的阈值时就会进行扩容
table数组的长度必须为2的次方数，所以每次扩容都是按照上一次的tableSize位移运算得到的：
左移一位 16<<1==32 16、32、64

因为考虑性能，底层的CPU不支持乘法运算，所有的乘法运算最终在指令层面都是转化为加法实现的，效率很低，如果使用位移运算的话，对CPU来说效率就会很高