数据结构
参考:
- 1.8 之前是 数组+链表 Entry<K,V>[]
- 1.8 开始修改为数组 + 链表 +红黑树 Node<K,V>[] table
红黑树条件
- 单链存储个数 >=7 && 数组长度>=64 升级为红黑树 ,(如果长度小于64,则扩容)
- 根据泊松概率 单链存储个数到8的概率很小 (7:0.00000094 8:0.00000006)
- 树存储个数<6 时 降级为链表(内存 树:链表 = 2:1)
默认大小及存储规则
数组默认长度为16 ,可在初始化时修改,只能是2的N次幂,如果不是,会找到大于当前设置大小最小的2的N次幂
为什么只能是2的整数倍,减少hash冲突, 2的整数倍减1后 得到的二进制为 0....*n 1...*n, 与运算后得到的结果与hash%length 相同,但是比取余快很多
计算存储下标,会将key 的hash值 与 (数组长度 -1) 进行 '&' 与运算, 得到的值为 [0, 数组长度-1] 的范围内整数,得到的值为最终存储在数组的下标
存储元素时,如果当前下标没有元素.直接存储,如果有元素,比较key值是否一致,一致则覆盖,不一致则添加在该元素的后面
默认加载因子为0.75,16 *0.75=12 ,当存储元素个数超过12后(++size>12), 就会进行扩容
扩容的大小为2倍
操作
计算hash
- hashcode = key.hashcode ^(异或 相同为0 不同为1) key.hashcode >>> 16 ,右移16位 高低位异或
- 因为数组长度一般较小 用不到高位hash值,也是为了让数据分布的更为散列
- hashcode & Node[].length - 1 ,得到的值即为目标solt(桶位 即数组下标)
put
- slot 为null 直接放入
- slot 不为null 且未被链表化 , 比较 hash 和 key ,一致则替换value, 不一致则插入在最后(尾插法)
- slot 已被链表化, 比较 hash 和 key ,一致则替换value, 不一致则插入在最后(尾插法),最后检测是否需要树化(链表长度>=8 && Node[] >=64)
- slot 已被树化,红黑树插入,找到需要插入的位置,如果 hash 和 key一致则替换value,不一致则插入,然后平衡红黑树
get
比较hash 和 key ,链表 next, 红黑树 比较大小 left right ,找不到返回null
remove
比较hash 和 key,找不到不删除,返回null,注意 如果删除后 红黑树元素存储个数<6 时 降级为链表(内存 树:链表 = 2:1)
resize
oldLength<<1 两倍扩容,如果超过最大值 取最大值(1<<30,cpu底层没有乘法 位运算贼快)
计算扩容后元素应该存储的slot(数组下标) hash : hash & 原长度 只会有两种结果 : 0 或者 原先下标+原数组长度
结果1 0000 1011 hash值 0000 1111 原数组长度 16-1 ============== 0000 1011 原下标位置 11 0000 1011 hash值 0001 0000 数组长度 16 ============== 0000 0000 结果为0 结果2 0001 1011 hash值 0000 1111 原数组长度 16-1 ============== 0000 1011 原下标位置 11 0001 1011 hash值 0001 0000 数组长度 16 ============== 0001 0000 结果不为0 0001 1011 hash值 0001 1111 扩容后长度 16*2 -1 ============== 0001 1011 结果为 16 +11原slot是null 跳过
原slot未链化 计算新的下标
原slot链化 挨个计算新的下标,暂存在两个Node中 ,之后分别放入
原slot树化(调用树的split) 将树解码为链表 挨个计算新的下标,暂存在两个Node中 ,放入时需判断是否>6 ,大于6则升级为红黑树放入
网友评论