HashMap的put()方法流程
数组容量为质数会使hash值分布均匀, 但是2^n计算索引的效率更高.
HashMap的put()方法流程
1.8的put流程
- HashMap 是懒惰创建数组的,首次使用才创建数组
- 计算索引(桶下标)
- 如果桶下标还没人占用,创建Node放入数据后返回
- 如果桶下标已经有人占用
- 已经是TreeNode走红黑树的添加或更新逻辑
- 是普通Node,走链表的添加或更新逻辑. 如果链表长度超过树化阈值,走树化
逻辑
- 返回前检查容量是否超过阈值, 一旦超过进行扩容.
- 扩容时, 先将新的数据放进数组, 然后创建新的数组, 再将旧数组元素迁移到
新数组
1.8和1.7的put流程不同之处
链表插入节点时, 1.7是头插法, 1.8是尾插法
1.8有判断链表长度, 树化的逻辑. 1.7没有.
负载因子为何是0.75
0.75是在占用空间和查询时间中取得了比较好的平衡. (扩容阈值=数组大小*负载因子)
大于0.75, 冲突增加了, 数组空间就节省了, 但是链表就会比较长, 影响性能.
若负载因子为1, 则16*1 = 16, 只有当存满16个元素之后, 才会扩容. 节省空间, 影响性能.
小于0.75, 冲突减少了, 链表会比较短, 数组扩容会很频繁, 空间占用增多.
若负载因子为0.25, 则16*0.25=4, 当元素个数大于4个, 就会扩容. 浪费空间, 提高性能