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个 二叉树 -》 转成链表

Q.E.D.