hashMap部分相关知识
不要将ArrayList的初始容量和HashMap的初始容量混淆：
ArrayList初始容量是10；
HashMap初始容量是16，加载因子（容量*因子=扩容阈值）默认是0.75；
HashMap是懒惰加载，在创建对象时并没有初始化数组，仅设置加载因子；
hashMap的插入put流程？
1.判断当前大小是否为0，是则先初始化数组；根据key计算索引；
不是直接根据key计算索引；
2.判断数组的索引位置是否为null，是直接加入，不是进入下一个判断；
3.判断当前key是否和存储位置上对象的key一致，如果是，覆盖，否则进入下一层判断；
4.判断当前数组位置是否是红黑树，是则将key加入红黑树，否则说明是链表进入下一步；
5.遍历链表当前key是否出现，如果出现则覆盖，没有出现则加入链表，判断链表长度和数组长度，判断是否需要转化为红黑树；
6.无论是数组插入，还是链表插入，红黑树插入在结束后，都需要对数组当前长度进行判断，是否需要扩容。
hashMap的扩容机制？
hashMap中数组存储节点的数据结构：
hash：对key hash后的数值
key
value
next：指向下一个对象的指针
判断oldcap是否大于0，如果不是说明是第一次扩容，即初始化数组，则创建容量为16的数组；
如果大于0，则构建一个新的数组，newcap=2*oldcap，
- 原来存在数组的元素，直接加入新数组（⽤ e.hash & (newCap - 1)等价于对新数组取模，数组扩容为原来两倍后，对新数组取模要么在原来的位置，要么在一个新的位置）；
- 原来存在链表的元素，计算hash&oldcap，判断是高位元素还是低位元素，对应放入数组原始位置+增加的大小，还是放入数组原始位置；
- 原来存在红黑树的元素，与链表类似，不过需要判断拆分后长度是否小于等于6，如果是，则拆分为链表。
链表长度改变触发的不同改变：
链表长度>8,数组长度>64，将链表转化为红黑树；
链表长度>8,数组长度<64，将数组扩容；
扩容后拆分链表的操作？
jdk1.7
对链表所有元素重新hash对新长度取模
jdk1.8
hash&oldcap判断是低位元素还是高位元素，
如果是低位元素，存放在原位置；
如果是高位元素，存放在原下标+增加的容量的位置；
为什么hashMap初始化长度为2的幂次？
hashMap扩容为什么是两倍？
数组长度为什么是2的n次方？
以上三个问题的原因类似：
1.可以使用位运算来计算索引
通过hash& （len-1）位运算代替取模操作，提高效率，
为什么能够hash& （len-1）代替取模操作？
len是2的幂次，如：16,16-1=15,15的二进制是1111，16的取模范围为0-15，使用hash& （len-1）在len=16时意味着hash的低四位（0000-1111）可以直接决定获取的索引，低四位和1111相与，低四位是什么结果就是什么，直接通过位运算代替取模操作，提高性能。
2.使分布更加均匀
当长度是2的幂次时可以充分利用哈希码的位，length−1的二进制中没有0，使用位与运算每个位都得到考虑，与运算和1与，原来是什么就是什么；如果长度不是2的幂次，则部分低位可能得不到充分利用，比如低位有0，不管什么相与都为0.
比如长度任为16：length−1为15：1111，充分考虑长度限度内的每一位，而超度为10：1010，则最低位就没有得到充分的利用，更容易产生hash碰撞。
hash寻址算法？
hash冲突解决方法？
开放定址法（冲突找空位）
再哈希法（冲突后使用别的hash函数来再次定位）
链表法（通过形成链表来存储冲突的hash值）
为什么使用位移运算？
CPU不支持乘法运算，所有乘法运算最后都会转化为加法运算，性能较低，而使用位移运算对CPU来说简洁高效，效率高。
hashMap的再hash算法？
先获取key的hashCode值，然后右移16位 异或运算 原来的hashCode值；
右移16位将hashcode的高位移动到低位，因为hashcode是一个32位整数，基本上使用的hash数组不可能到达这个长度，所以一般hash数组仅使用到hashcode的低位，这里将高位移动到低位，再和原来的hashcode异或，是将hashcode高位的随机性带到低位，使分布更均匀。
扩容时的hash&oldcap原理？
由于hash数组扩容为原来的两倍，所以相当于增加了最高位，原来映射到同一位置的元素（链表或红黑树中的元素）除了最高位的其他位一定相同，不用考虑，只用考虑最高位是什么，所以根据hash&oldcap分为高位和低位，如oldcap=16（使用位运算0000-1111），扩容后为32（使用位运算00000-11111），通过对16：10000与hash位运算可以直接判断高位，而选择在原来的位置还是旧索引+增加容量。
参考视频
hashMap的一些相关原理可以参见以下视频，个人觉得问答挺全面的，适合学了一点又不太清晰的来补充补充，
【电话面试】HashMap面试聊了30分钟，狂问红黑树细节，深挖扩容机制细节，怪不得他能拿25k月薪！】https://www.bilibili.com/video/BV1Qk4y1672n?vd_source=a70a5573b182a2efadab0e4922233ceb