相信大家对HashMap并不陌生，最近在考虑换工作，看了一下相关的知识点，随手记录下来加深记忆，希望对大家也能有帮助
java中hashMap的底层数据结构是：数组+链表/红黑树，jdk1.8之前红黑树还没有引入，jdk1.8之后就引入了红黑树的概念
延伸一下，为什么不是别的树呢？
首先
二叉查找树（二叉排序树）特性：
1、左子树不为空，那左子树上的所有节点的值都会小于根节点的值
2、右子树不为空，那右子树上的所有节点的值都会大于根节点的值
如果用二叉查找树，特定情况下，二叉查找树会出现线性结构
比如，根节点值我放个100，后面的所有值都是小于100的，那就会一直在左子树上添加数据，就变成了链表一样的结构，那我还引入什么树，直接用链表好了呗，duck不必
平衡二叉树：
个人理解，平衡二叉树比较严谨，两颗树的高度差大于1的时候就要调整，有点太废性能了
红黑树特性：
1、根节点永远是黑的
2、每一个节点要么红的要么黑的
3、每个叶子节点都是黑的
4、任何一个节点到其叶子节点都会经过相同数量的黑色节点
5、如果一个节点是红的，那两个子节点都是黑的
红黑树本质上还是二叉查找树，但是与二叉查找树不同的是，红黑树使用了颜色区分和一些相关的特性使得红黑树能够保持相对平衡，从而提升了效率
综合能力来说，红黑树完胜，也够用
回到hashMap上面
刚才说了hashMap的结构是数组+链表/红黑树，当发生hash冲突的时候，hashMap会把数据放到链表里面，如果数组大于64并且链表长度大于8的时候，链表会转变成红黑树，当红黑树大小小于6的时候，为了读写的性能，又会变成链表
当我们new HashMap的时候，系统都干了什么呢
系统肯定会去看这个对象有没有被初始化过，然后进行类加载，给这个分配空间等操作
HashMap有三个方法，有参的无参的
无参的时候，hashMap使用默认值，即
根据这些默认值给map进行初始化
如果是调用的有参方法，根据传进去的参数，负载因子，给hashMap进行初始化，但正常情况下，负载因子不建议修改，因为负载因子太高，提升了造成hash冲突的可能性，负载因子太低，则会导致hashMap频繁扩容，都会影响性能
至于hashMap的大小，是可以自己定义的，但长度一定要是2的幂次方
这样可以更高效的取hash值并且可以减少hash冲突，并且可以保证，位置永远在长度之内
在扩容的时候也不需要重新计算位置，只需要判断最高位是0还是1，0的话位置不变，1的话位置变成原长度+原位置
HashMap的put原理
hashMap拿到key的时候首先计算key的hash值，如下图
key的hashCode与高16位做异或运算得到最终的hash值
然后在putVal方法里，hash值跟数组长度-1做与运算得到index ，如下图630行
得到index以后，判断这个位置是否存在值，无，直接放进去，有，判断是链表还是红黑树，遍历里面的key，判断key是否相等
判断key是否相等：首先判断hash值，然后用==||equals来判断，hash值与==||equals都相等的话，直接用新值覆盖原值，否则说明发生hash冲突，根据是链表还是红黑树以不同的方式存放数据
链表的话，jdk1.7采用的是头插法，jdk1.8采用的是尾插法，这个我也没搞懂为什么头插会死循环，感兴趣的朋友可以去了解下，有大神懂的话希望指点下小弟
数据存放完毕，看下链表是不是需要转成红黑树，根据threshold（阈值：负载因子*数组大小）判断数组长度是否够用，看是否需要扩容
HashMap的get原理
了解了put的原理，那get的原理就反向推一下就好了，也是先算出hash值，然后拿到index，判断key是否相等，遍历链表/红黑树取值返回
HashMap的扩容机制
当数组大小超过阈值的时候，会触发hashMap的扩容机制，新数组大小为原数组的两倍
当hashMap还没有被实例化的时候
第一次put，会先触发扩容机制，长度为默认值，存放完毕再次判断是否需要扩容
不是第一次put，会直接存放数据，然后判断是否需要扩容
扩容完毕元素迁移的方法就是上面说的，新的索引位置不需要重新计算了，只需要判断最高位是0还是1就好了，然后判断链表长度，决定是否转化为红黑树
以上，说错或者没有说到位的地方，欢迎大家补充