HashMap底层数据结构
2023-02-04 10:32:18 0 举报只进行文字性的总结，欢迎指出不足，数据结构可视化工具分享：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
作者其他创作
大纲/内容
再扩容时如果拆分树时，树元素<=6则退化链表
hash表的查找，更新的时间复杂度是0(1)，而红黑树的查找，更新的额时间复杂度是O(log2n)，TreeNode占用空间也比普通Node大如非必要尽量还是使用链表
HashMap
数组+链表|红黑树
jdk1.8
为什么要用红黑树
JDK1.8 以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间
也是树化阈值为啥是8
红黑树特征（空间换时间）
通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。（如果超出旋转和变色进行调整）
查找元素的过程：计算键的哈希值进行二次哈希，得到二次哈希值与当前的数组长度进行取模得到的桶下标即为该元素的位置
方式一：对数组扩容（元素的个数打到数组长度的3/4就会自动乘二倍扩容），扩容后则会重新计算哈希值重新取模分配位置
方式二：红黑树树化的条件：一：链表长度大于阈值8，数组的容量长度大于64
红黑树退化链表
先扩容再树化（树化是一个非正常状态）
红黑树是一种二叉查找树父节点的左侧都是比他小的元素右侧都是比他大的元素（字符串）
红黑树用来避免Dos攻击的，防止链表过长造成性能下滑，树化是一种偶然现象
hash值如果足够随机，则在hash表内按泊松分布，在负载因子0.75的情况下，长度超过8的链表出现概率是亿分之6，选择8是为了让树化几率足够小
remove树节点时，若root、root.left、root.right、root.left.left有一个为null，也会退化为链表
当很多和元素的桶下标相同
0 条评论
下一页
