1. HashMap底层用到了那些数据结构？

1.8以前HashMap是通过数组+链表来实现的，1.8以后是通过数组+链表+红黑树实现的
1.8主要的改变有两个，一：将链表头插的方式改变成了尾插，这样做的目的是为了避免出现链表死循环的问题，并且因为转变为红黑树以后，也不能再使用头插法了。
二：在链表长度大于8并且数组长度大于64的情况下，会将链表转换为红黑树。这样也是为了避免链表过长而导致的查询效率降低。

2. 为什么要用到这些结构？

Hash表就是通过K-V的数组来保存数据，所以数组是必须的
链表是因为HashMap解决哈希冲突采用的是拉链法，会将哈希值相同但是equals不同的数据用链表的形式保存起来，这样的好处时解决hash冲突简单，并且删除数据容易。
红黑树是为了解决当链表长度过长时，遍历链表的效率会大幅降低的问题。红黑树的查询效率是非常高的，因为它是树状结构，所以可以使用二分法查找。

3. 为什么要用到链表结构？

解决哈希冲突
开发地址法的问题在于，删除节点的时候过于麻烦，记录删除标记需要额外的空间和操作
并且如果数组发生扩容，将会导致某次探测的效率大幅降低

4. 为什么要用到红黑树？

为了解决链表过长造成的查询效率低的问题
为什么不用二叉树而要用红黑树？
因为使用二叉树，如果一直往一侧添加数据，会造成其退化成链表。而红黑树通过颜色改变，加左旋右旋的方式可以达到自平衡。虽然平衡二叉树也能做到平衡，但是它每次增删要进行大量的平衡度计算，开销远大于红黑树。

5. 链表和红黑树在什么情况下转换的？

当链表长度大于8并且数组长度大于64的时候会进行转换。
也就是说如果链表长度大于8但是数组长度不够，它会去执行扩容，而不是转换为红黑树。

6. HashMap在什么情况下扩容？

扩容主要有以下几种情况：
一：如果我们没有在设置负载因子和长度的情况下，在首次添加数据的时候会进行初始化数组长度，默认是16，负载因子是0.75
二：当链表长度大于8并发生了哈希冲突的时候，如果数组的长度小于64，会进行一次扩容
三：源代码中，在添加操作的最末尾，如果检查到当前存储的键值对数量超过阈值，也会进行一次扩容。
阈值就等于数组长度负载因为，所以初始化阈值就是160.75=12

7. HashMap如何扩容的？

大体分为两种情况
一：如果数组为null，则使用默认值进行初始化
二：如果不为null
1.如果当前长度已经大于最大容量，不会进行扩容，直接返回旧的数组，并把阈值设置为Integer的最大值。
2.如果当前长度小于最大容量且大于等于默认长度16，则将长度扩容2倍
3.将旧数组中的节点转移到新数组中

HashMap每次扩容都是2的幂次方，这也是为了数据的均匀分布，尽量减少哈希冲突。

8. HashMap是如何Put一个元素的？

1.将key作为变量，通过哈希函数，计算出一个散列值
2.判断数组是否为null，如果是则进行初始化数组
3.将散列值与数组最大长度进行与运算，得到其在数组的位置
4.查看当前位置是否已经有键值对，如果没有，直接将节点放在这个位置
5.如果有，这个时候要通过判断key的equals是否相等，如果相等则覆盖
如果不等，再判断当前是链表还是红黑树
如果是红黑树，以红黑树的方式添加一个节点到红黑上上
如果是链表，则将其添加到链表之后。这个时候去再去判断链表的长度是否大于8，如果是则判断数组的长度是否大于64，如果不是则将数组扩容，如果是则转换为红黑树
6.如果有被覆盖的值，此时将被覆盖的值返回
7.判断当前键值对的数量是否大于阈值，如果是，则扩容。

9. HashMap是如何Get一个元素的？

10. 什么是Hash冲突

11. HashMap是如何解决Hash冲突的？

12. 还有哪些解决Hash冲突的方式？