这是在基于 JDK 1.8 之后的源码进行的浅谈
简介：
在 JDK 8 中，HashMap 由 “数组 + 链表 + 红黑树” 组成。链表过长会影响查询性能，而红黑树搜索的时间复杂度是 O(logn)，而链表则是O(n)，JDK 8 对数据结构进行了进一步的优化，引入了红黑树，链表在一定条件下会转化为红黑树：
- 当链表长度超过 8 且数据总量超过 64 时会转红黑树。
- 将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树，以减少搜索时间。
JDK 8 中 HashMap 的结构如下：
在 HashMap 进行 put 操作的时候，简要流程如下：
- 首先根据 key 的值计算 hash 值，找到该元素在数组中存储的下标
- 如果数组是空的，则调用 resize 进行初始化
- 如果没有发生 hash 冲突则直接将 key 放在数组对应的位置
- 如果发生了 hash 冲突，且 key 已经存在，则用新 value 覆盖掉旧值
- 如果发生冲突后，发现该节点是红黑树，则直接将该节点挂载在树上
- 如果发生冲突，并且该位置是链表，首先判断链表长度是否大于8，如果大于8并且数组容量小于 64 则进行数组扩容；如果链表节点长度大于 8 并且容量大于 64 则将该位置的结构转换为红黑树；否则连败哦插入键值对，若 key 存在，就覆盖掉 value
贴一个高频引用的图，具体流程如下
扩容时数据的迁移：
在数组元素小于 64 的时候，如果某一位置链表的长度恰好为8，并且要插入的数据恰巧也落在这个位置，那么就会发生数组的扩容。
数组的长度扩容（默认为原来的二倍）不需要重新计算下标，只需要将 hash 值和旧数组长度相与即可确定位置。
由于数组的容量是以2的幂次方扩容的，那么一个Entity在扩容时，新的位置要么在原位置，要么在原长度+原位置的位置，原因如下图
数组长度变为原来的2倍，表现在二进制上就是多了一个高位参与数组下标确定。此时，一个元素通过hash转换坐标的方法计算后，恰好出现一个现象：最高位是0则坐标不变，最高位是1则坐标变为 “10000+原坐标”，即 “原长度+原坐标”
今天的小八股就到这里啦
