一、什么是Hash冲突

哈希冲突，也叫哈希碰撞，指的是两个不同的key值，计算出了相同的hashcode值，然后计算出相同的下标，通常解决方案有：

  • 拉链法，把哈希碰撞的元素指向一个链表
  • 开放寻址法，把产生冲突的哈希值作为值，再进行哈希运算，直到不冲突
  • 再散列法，就是换一种哈希算法重来一次
  • 建立公共溢出区，把哈希表分为基本表和溢出表，将产生哈希冲突的元素移到溢出表

二、HashMap为什么要用到链表结构

当我们向HashMap中添加元素时，会先根据key进行哈希运算，把hash值模与数组长度得到一个下标，然后将该元素添加进去。但是如果产生了哈希碰撞，也就是不同的key计算出了相同的hash值，这就出问题了，因此它采用了拉链法来解决这个问题，将产生hash碰撞的元素，挂载到链表中

三、HashMap为什么要用到红黑树

当HashMap中同一个索引位置出现哈希碰撞的元素多了，链表会变得越来越长，查询效率会变得越来越慢。因此在JDK1.8之后，当链表长度超过8个，会将链表转坏为红黑树来提高查询

四、HashMap链表和红黑树在什么情况下转换的？

当链表的长度大于等于8，同时数组的长度大于64，链表会自动转化为红黑树,当树中的节点数小于等于6，红黑树会自动转化为链表

五、HashMap在什么情况下扩容？HashMap如何扩容的？

HashMap的数组初始容量是16，负载因子是0.75，也就是说当数组中的元素个数大于12个，会成倍扩容

tips:为啥子是0.75：负载因子过小容易浪费空间，过大容易造成更多的哈希碰撞，产生更多的链表和树，因此折中考虑采用了0.75

为啥子是成倍扩容：需要保证数组的长度是2的整数次幂

为嘛数组的长度必须是2的整数次幂：我们在存储元素到数组中的时候，是通过hash值模与数组的长度，计算出下标的。但是由于计算机的运算效率，加减法>乘法>除法>取模，取模的效率是最低的。开发者们为了让你用的开心，也是呕心沥血。将取模运算转化成了与运算，即数组长度减1的值和hash值的与运算，以此来优化性能。但是这个转化有一个前提，就是数组的长度必须为2的整数次幂