JDK1.7和1.8中HashMap的底层原理介绍

• HashMap jdk1.7 底层原理的介绍
• • 数据结构
  • 数组容量
  • 扩容
  • fast-fail
• HashMap jdk1.8 底层原理的介绍
• • 数据结构
  • 扩容
  • 链表树化

HashMap jdk1.7 底层原理的介绍

数据结构

1. 底层数据结构是数组加链表
2. 数组中查找元素的时间复杂度是O(1),get某下标下的元素时直接从该下标处取就行
3. 引入链表是为了解决hash冲突，当然解决hash冲突的方法还有比如线性探测再散列，二次线性探测再散列, 再hash法等。
   而链表查询一个元素的时间复杂度是O(n),取任意下标位置的元素都要从头遍历
4. HashMap用来存储键值对的元素类是内部类Entry,实现了Map.Entry接口（它是Map接口内部定义的一个接口），HashMap中的Entry主要属性是key value hash值 next(下一个元素的引用)

数组容量

1. 当我们new一个HashMap并指定它的初始容量时，开始并不会初始化数组，当调用put方法时会重新计算capacity,大于等于我们
   给定值的2的n次方，
2. 为什么是2的n次方呢? 主要是为了更方便合理的计算元素的数组下标。因为2的n次方的数二进制高位为1低位全是0，当这个数减一则低位为0的二进制
   位全为1，这个数能表示的数据范围就是0到数组长度减一，将这个数与元素的hash值进行与（&）运算，就能保留hash值中低位
   为1的二进制位，运算后的结果自然在0到数组长度减一的范围内
3. HashMap默认的负载因子是0.75，负载因子乘以数组容量是扩容的阈值
   这里可以提出一个问题，new HashMap时给定10000，当数组元素个数达到10000时有没有进行过扩容？1000呢？答案是一万不会扩容，一千会扩容，
   因为一万时实际的数组容量大于等于2的n次方倍应该是一万六千多，乘以0.75的阈值（此处使用默认阈值，没有自定义指定）也要大于一万，所以不会扩容，
   而一千的实际数组容量是1024（2的10次方），乘以0.75后要小于一千

扩容

1. put方法执行过程中，对于数组位置冲突的元素采用头插法插入到链表中
2. 对于key为null的元素会放入数组的第一个位置
3. 什么时机会扩容呢？
   put方法执行过程中，已经计算好数组下标后会判断当前元素数量大于等于阈值且该下标位置下已有元素就会触发扩容机制，注意此时是在put元素前，
   元素数量还是原来的。
4. 扩容的过程： 扩容的操作简单就是new一个两倍容量的数组然后从旧数组转移元素，元素转移时也是采用头插法，转移后的新位置一般来说可能跟原来
   相同也可能是旧下标+旧数组容量值，顺序跟原来比是相反的，但若是有重新生成hash种子的操作，新位置下标计算时会重新生成hash值，位置就不确定了。
   头插法带来的缺点就是如果此时有多个线程并发执行扩容操作就可能会出现循环链表，查询时链表不停循环。因为转移操作时有两个变量指向链表的当前位置
   和下一个位置，如果这个链表上的元素转移后的位置跟旧数组一致，但由于顺序相反，并发时可能出现这两个引用变量指向的元素顺序翻转，从而形成死链。
   当然基本原理是这样，具体的业务场景上有多种情况。
5. 初始化数组和扩容时都有个重新生成hash种子的步骤，一般情况下我们都用hash种子的默认值0，可以通过环境变量指定一个交替散列阈值的变量
   （具体是哪个变量可以查询），初始化数组和扩容时判断当数组容量大于我们指定交替散列阈值是就会生成一个随机数作为新种子，该种子在计算元素
   hash值时会用到，目的就是为了让元素更加散列，减少hash冲突，优化查询性能，在jdk1.8中就没有这个操作了，因为引入了红黑树，
   查询性能得到了保证，jdk7中计算hash值的方法也比jdk8中的复杂点，还是为了更加散列

fast-fail

快速失败机制是为了保证集合元素遍历时的一致性而设计的，正常遍历过程中元素发现元素被修改了就会抛出异常，在HashMap中，我们使用for循环遍历元素的代码编译成class文件后实际就是迭代器的遍历，集合中有个modCount属性，在执行put remove等修改集合元素的方法时增加modCount的值，从集合对象获取迭代器对象时，集合的modCount属性会传给迭代器对象的exceptionModCount属性，迭代器的next方法会判断它俩的值是否相等，不等则会抛出异常。
解决：使用迭代器的remove方法可以将集合中的modCount重新赋值给exceptionModCount，避免在遍历过程中删除元素出现异常，但是并发情况下还是会抛出异常

HashMap jdk1.8 底层原理的介绍

数据结构

1. jdk1.8中HashMap的底层数据结构是数组，链表，红黑树。
2. 链表的插入采用尾插法
3. 红黑树的定义：
   每个节点只能是红色或黑色
   根节点是黑色
   叶子节点都是黑色且为null
   红色节点的左右子节点都是黑色
   对每个节点，从该节点到其子孙节点的所有路径上包含相同数目的黑节点。
4. 用来存储键值对的元素类是内部类Node和TreeNode,Node实现了Map.Entry接口,属性与jdk1.7中的内部类Entry是一样的，TreeNode接口继承了LinkedHashMap中的
   静态内部类Entry，而这个Entry又继承了HashMap中的Node,因此除了具有Node中的属性外还有链表中指向前驱和后继节点的引用属性，还有二叉树中指向父节点，
   左右子节点的引用属性
5. hash算法没有1.7的复杂，不需要更散列，引入黑红树，在查询性能上有了保证
6. 红黑树查询的时间复杂度是O(lgn)
7. 红黑树结构中依旧存在双向链表

扩容

1. 执行put方法时，数组下标的计算逻辑也是hash值和数组长度减一进行与运算，计算出下标位置已有元素时判断
   第一个元素的类型是Node还是treeNode以此执行插入链表还是红黑树

2. 插入链表时使用尾插法，遍历列表，判断元素个数大于8时执行链表转红黑树的操作，同时要求数组元素个数要小于64，否则
   不进行树化操作而是先扩容数组，扩容后的数组可能会减小链表长度

3. 元素个数大于阈值，对数组进行扩容。同样是new一个两倍大小的数组然后进行元素的转移，这里的转移分为链表的转移和
   红黑树的转移。链表转移时先将元素下标计算好再尾插法连在一起一次性转移，红黑树红黑树中也存在双向链表，
   计算出元素的新位置可能跟原来相同也可能是旧下标+旧数组容量值，这里没有hash种子的操作，相同元素连在一起后形成数组
   的高位和低位链表，一次性转移。转移后判断元素个数小于等于6时会进行去树化（链表化）处理，否则重新进行树化

链表树化

1. 使用红黑树的原因：链表的插入速度比红黑树快但是在元素节点太多时查询很慢，普通的二叉查找树解决不了长腿问题，查找速度会退化成链表
   AVL树是高度平衡的二叉树，要求所有节点的左右子树的高度差不超过1，查询较
   红黑树快但是节点多时要通过多次旋转来达到平衡
2. 红黑树平衡的操作：变色，左旋，右旋
3. 当链表中的元素个数大于阈值8且数组长度大于等于64时会将链表转换为红黑树
4. 转换过程中节点大小的判断规则：先使用hashCode比较，相等时调comparable接口，还相等的话再调getClass().getName()获取类名用字符串比较，
   还比较不出再调System.identityHashCode()方法计算key的内存地址相关的hash值，最终在这会处理两个内存hash值相等的情况
5. 红黑树结构中数组的节点table[i]是根节点
6. remove方法移除元素后如果是红黑树结构会判断是否要转成链表，判断的条件中没有限制节点数量而是根据树的结构比如
   根无左子节点，根无右子节点，根的左子节点无左子节点，源码注释中解释在2到6个节点的情况下可能被转成链表，取决于数的结构

本文地址：https://blog.csdn.net/weixin_37773933/article/details/112664553