HashMap在JDK7.0及之前和JDK8.0及之后区别
前言
我们在学习集合的时候,出去list就是map集合使用比较多,今天主要说一下常用的HashMap底层的进化
干货
jdk7.0之前 数组 + 链表 阈值：30
jdk8.0开始 数组 + 链表 + 二叉树 阈值：30
HashMap底层在1.8之前是基于数组和链表组成 形成一个哈希表
首先数组的优点：
查找元素效率高 由于数组这个数据结构的特点
他们是等大连续 所以当我们想要查找某个元素的时候
只要计算偏移量给可以 时间复杂度是O(n)
链表的优点：
链表的数据结构导致他们在添加 删除元素的时候效率高
他们通过保存地址指向形成一个链表结构彼此相连接
当我们想要往链表里面添加或者删除一个元素的时候
只需要修改地址指向就可以 时间复杂度是O(n)
当我们想要往HashSet/HashMap集合里面添加元素的时候
元素被装进那个小组 我们是需要根据hahCode()算出
哈希码值 然后根据哈希码值%分组组数看余数
通过余数判断应该去哪一个小组[查找进入的小组]
所以哈希表的表头应该用数组存储这个余数 方便查找
但是进入该小组之后 如果发现这个小组里面有元素需要
在详细作比较 如果比较完之后 发现该小组里面的元素
没有和新来的元素一样 那么新来元素需要插入进去
既然组内经常涉及到插入删除元素 那么应该考虑用链表结构
所以在8.0之前 先根据哈希码值计算去到哪个小组
表头用数组装 好查找
查找应该去到某个小组之后 开始往该小组里面插入、删除元素
所以组内又是拿着链表装 好添加、删除
但是在8.0及之后 考虑到可能算法不好 导致一个组内里面的元素
过多 那么再往某个小组里面添加元素的时候 比较的次数
变多 所以在8.0开始 所有个很大的进步 就是引入二叉树机制
当组内元素个数>8个 由链表转成二叉树
这样又能分散点元素 在添加、删除元素的时候就不需要和
组内所有的元素都作比较 只需要和部分元素作比较
当组内元素个数<6个 二叉树 -》 转成链表
