HashMap
底层数据结构，1.7和1.8？
1.7数据加链表
1.8数组加链表或者红黑树
链表中元素多变化为红黑树，删除退化为链表
为何一上来不树化，树化阈值为何是8，何时会树化，何时退化为链表？
1.7时候链表太长了会影响性能，数组容量大于64 和阈值大于8同时满足
为何一上来不进行树化
链表短要好的，长的化。
链表是node,红黑树treenode；
红黑树是一种问题情况
1.防止dos攻击机，防止链表超长时性能下降，树化应当是偶然情况
泊松分布，负载因子0.75下，是0.0000006，选择8树化概率小
何时退化链表：
1.做一次扩容，阈值小于等于6
2.退化条件2：remove 树节点，若root,root.left,root.right,root.left 有一个为null也会退化
（移除之前检查）
3/4扩容 原来2倍
索引怎么计算？hashcode，为何提供hash(),数组容量为何为2的n次秘？
首先计算对象的hashcode(),然后调用hashmap的hash（）方法进行二次哈希，最后得到哈希
hashcode
二次哈希 ：通过对原始哈希表的计算实现更高效的查询和匹配，与单一比，二次哈希
算法能够在哈希表中多个键执行哈希操作，减少哈希冲突。哈希冲突是指当俩个或多个键得映射
在同一哈系统发生的问题，导致查询效率低，
二次哈希作用：1.8位移16位。不是用hash进行索引，分布均匀，足够随机。
初始必须2的n次方
二次哈希后%16运算，得到桶下表
求m%运算可以优化为$运算
2的n次幂好处（最求效率）
1.用按位与替换取模运算，效率更高，2.扩容是hash& oldCap==0 的元素留在原来位置，
否则新位置=旧位置+oldCap3.计算索引&(capacity -1)
2的n次幂缺点
分布性不太好
最求哈希表的分布好，选质数。
HashMap
底层数据结构，1.7和1.8？
1.7数据加链表
1.8数组加链表或者红黑树
链表中元素多变化为红黑树，删除退化为链表
为何一上来不树化，树化阈值为何是8，何时会树化，何时退化为链表？
1.7时候链表太长了会影响性能，数组容量大于64 和阈值大于8同时满足
为何一上来不进行树化
链表短要好的，长的化。
链表是node,红黑树treenode；
红黑树是一种问题情况
1.防止dos攻击机，防止链表超长时性能下降，树化应当是偶然情况
泊松分布，负载因子0.75下，是0.0000006，选择8树化概率小
何时退化链表：
1.做一次扩容，阈值小于等于6
2.退化条件2：remove 树节点，若root,root.left,root.right,root.left 有一个为null也会退化
（移除之前检查）
3/4扩容 原来2倍
索引怎么计算？hashcode，为何提供hash(),数组容量为何为2的n次秘？
首先计算对象的hashcode(),然后调用hashmap的hash（）方法进行二次哈希，最后得到哈希
hashcode
二次哈希 ：通过对原始哈希表的计算实现更高效的查询和匹配，与单一比，二次哈希
算法能够在哈希表中多个键执行哈希操作，减少哈希冲突。哈希冲突是指当俩个或多个键得映射
在同一哈系统发生的问题，导致查询效率低，
二次哈希作用：1.8位移16位。不是用hash进行索引，分布均匀，足够随机。
初始必须2的n次方
二次哈希后%16运算，得到桶下表
求m%运算可以优化为$运算
2的n次幂好处（最求效率）
1.用按位与替换取模运算，效率更高，2.扩容是hash& oldCap==0 的元素留在原来位置，
否则新位置=旧位置+oldCap3.计算索引&(capacity -1)
2的n次幂缺点
分布性不太好
最求哈希表的分布好，选质数。
hash扩容是2倍
红黑树类似于平衡二叉树
链表n
log2n
hash扩容是2倍
红黑树类似于平衡二叉树
链表n
log2n
标签：hash,hashMap,树化,链表,哈希,红黑树,root From： https://www.cnblogs.com/zyb-luckey/p/17997860