HashMap基本原理
HashMap主体上是由一个数组来存储数据，每一个索引的位置在这里我们可以先管他叫“桶”，假设你定一个HashMap的长度为16，那么就可以说是由16个桶构成的数组。当我们插入一个数据的时候，并不是按顺序一个一个向后存储的，在HashMap中专门定义了一套用于定位数据存储位置的哈希散列算法来确定数据具体的存储位置，因为是哈希散列计算，所以会存在哈希散列碰撞，意思就是相同的Key计算出的哈希值是相同的，在HashMap中使用的是拉链法来解决，散列碰撞问题。
当两个Key的计算出的Hash值相同，但是key的值不同，那么他们就会被定位到同一个HashMap的桶中，这个时候HashMap为了不让他们相互覆盖，就会在同一个桶中构建一个链表来存储他们。
但是随着HashMap中存储的数据越来越多，发生碰撞的概率就会越大，某个桶中的链表就会越来越长，当一个桶中的链表长度达到8这个阈值的时候，HashMap就将桶中的链表转换成红黑树，以达到提高性能的目的。
HashMap中的桶的长度并不会一成不变，而是当HashMap中存储元素的数量达到总容量的75%的时候就会，触发HashMap的扩容机制，这个时候HashMap就会对桶大小进行扩容，扩容的数量为当前桶大小的两倍。以达到提高性能的目的。
默认容量
HashMap的容量就是数组的长度，默认容量是16
- 初始化时如果没有指定容量，则会使用默认值16，我们也可以为HashMap设置初始容量，而HashMap要求初始容量必须是2的幂次方。保证容量为2的幂次方的目的是：保证最后散列计算的结果是均匀
- 在设置HashMap初始化容量时HashMap会对传入的初始容量值进行转换，并保证初始容量都能为2的幂次方（通过tableSizeFor来保证）
HashMap如何确定Key的唯一性
HashMap是不允许存在相同Key的。
key的唯一性同时满足如下两个条件：
- 比较Key的Hash值是否相同。
- 比较是否同一个对象或者key的值是否相等。
以上两个条件都为true，则可认为是同一个Key。
HashMap为什么要求容量必须是2的幂次方
HashMap容量必须是 2 的幂次方，这样设计是为了保证散列计算更加均匀，计算索引的公式为 index = (n - 1) & hash
HashMap的扩容条件
- HashMap中的键值对数据达到扩容阈值的时候就会触发扩容，扩容阈值=容量*负载因子，负载因子默认值为0.75。
- HashMap扩容的时候，会创建一个容量为原来容量2倍的新数组，将数据从旧的数组中取出存入新的数组中
HashMap扩容负载因为为什么默认值设置为0.75
默认值是0.75是对HashMap查询插入时间和空间利用率权衡得出的结果，当负载因子为0.75的时候，避免了相当多的Hash冲突，HashMap底层的链表和红黑树的高度也比较低，在HashMap的空间利用率、插入和查询效率都比较高。
- 如果设置负载因子值为1.0，就意味着当HashMap中的数组填满之后才会触发扩容，虽然空见的利用率达到了最高。但是也会因为Hash冲突增加，会导致底层的红黑树的高度增高，从而影响数据的插入和查询性能。
- 如果设置负载因子值为0.5，就意味着当HahMap存储的数据达到容量的一半时就会触发扩容，虽然这样Hash冲突减少和查询效率会提升，但是在空间的利用率上就降低了，很多空间还没来得及使用就触发扩容了。
链表红黑树如何互相转换，阈值多少？
- 链表转红黑树的阈值为：8
- 红黑树转换成链表的阈值为：6
经过计算，在hash函数设计合理的情况下，发生hash碰撞8次的几率为百万分之6，从概率上讲，阈值为8足够用；至于为什么红黑树转回来链表的条件阈值是6而不是7或9？因为如果hash碰撞次数在8附近徘徊，可能会频繁发生链表和红黑树的互相转化操作，为了预防这种情况的发生。
插入元素的逻辑
- 计算插入元素Key的Hash值
- 判断HashMap的数组是否为空，为空则初始化数组，并返回数组长度，不为空直接返回数组长度
- 确定数据插入位置，数据插入位置=Key的Hash值 & (HashMap数组长度-1)
- 根据插入位置，取出旧元素，判断元素是否为空
- 为空则初始化数据为链表头节点，然后插入数组
- 如果数据不为空，判断新、旧元素的Key是否相等
- 相等则将新插入的数据覆盖旧的数据，然后结束插入操作。
- 不相等，则判断取出的数据是链表头节点还是红黑树头节点。
- 如果是链表，则将新插入数据插入链表尾部，插入成功后判断链表长度是大于等于8，如果大于等于8则转换成红黑树。
- 如果是红黑树，则将数据插入红黑树中。
- 元素插入成功这之后，HashMap长度+1。
-
判断HashMap的数据容量是否大于扩容阈值，如果大于则触发HashMap扩容。
HashMap-PUT操作
HashMap线程不安全问题
- jdk 1.7中HashMap扩容会产生死循环（元素从链表头部插入）、数据丢失、数据覆盖的问题
- jdk1.8 中HashMap 会有数据覆盖的问题（元素从链表的尾部插入）
