1,数据结构
数组+链表+红黑树(JDK>=1.8加入)
长度必须为2的指数幂 即 16 ,32....... 会强制向上转化最近的2的指数幂值
为什么
最低长度为16 即是你设置的是8 他在内部运算时强制向上去2的指数幂即16
2,HASH碰撞
1.任意相同的输入,一定能得到相同的输出
2.不同的输入,有可能得到相同的输出(哈希碰撞)
JDK1.7
put时会先对对象取HashCode,会进行哈希散列,目的是尽可能的避免hash碰撞,然后通过HashCode进行位运算(效率最高,最接近机器语言)得到具体的数组下标位置(hashcode值 & 数组长度值-1,为什么是数组长度-1,由于长度是2的幂次方,不减1进行位运算得话只有两种结果 要么数组的头要么是数组的尾部),找到对应下标的key,value后,判断改key是否已经存在,如果已经存在那么将value值覆盖,由于还是会出现hash碰撞,所以引入了链表,头插法(单线程扩容如果有链表,会出现位置互换)
3.扩容
哈希表的最大容量2的30次方 初始容量2的四次方 默认扩容加因子0.75
容量增加也要满足2的指数次幂,new 一个新的数组, 第一步首先遍历每个数组的下标位,第二步判断是否有链表, 第三步再次进行rehash,第四步将遍历到的数据迁移到新数组
头插法(单线程扩容如果有链表,会出现位置互换) 多线程扩容由于采取头插法会死循环( 链表成环 死锁)无法避免
高阶:为什么默认扩容因子是0.75
0.75是JAVA开发者从空间和时间上认为0.75为合适的值
最好的值为0.69
JDK8中引入了红黑树
只有等链表长度达到9时 会将链表转换为红黑树
网友评论