HashMap
1、存储过程
1、HashMap<String,Integer> hm = new HashMap<>();
当创建HashMap集合对象的时候，JDK8前，构造方法中创建一个一个长度是16的Entry[] table 用来存储键值对数据的。在JDK8之后不是在HashMap的构造方法底层创建数组了，是在第一次调用put方法时创建数组，Node[] table 用来存储键值对数据的。
2、假设向哈希表中存储柳岩-18数据，根据柳岩调用String类中重写之后的hashCode()方法计算出值，然后结合数组长度采用某种算法计算出向Node数组中存储数据的空间的索引值，如果计算出的索引空间没有数据，则直接将柳岩-18存储到数组中
面试题：哈希表底层采用何种算法计算hash值？还有哪些算法可以计算出hash值|
底层采用的key的hashCode()方法的值结合数组长度进行无符号右移（>>>)、按位异或(^)、按位与(&)计算出索引。
还可以采用：平方取中法、取余法、伪随机数法。
3、向哈希表中存储数据刘德华-40，假设刘德华计算出的hashCode方法结合数组长度计算的索引值也是3，那么此时数组空间不是null，此时底层会比较柳岩和刘德华的hash值是否一致，如果不一致，则在此空间上划出一个节点来 存储键值对数据刘德华-40，这种方法称为拉链法
4、假设向哈希表中存储数据柳岩-20，那么首先根据柳岩调用hashCode方法结合数组长度计算出 索引值为3，此时比较后存储的数据柳岩和已经存在 的数据的hash值是否相等，如果相等，此时发生哈希碰撞。
那么底层会调用柳岩所属类的String中的equals方法比较两个内容是否相等。
相等：则将后添加的数据的value覆盖之前的value
不相等：那么继续向下和其他的数据的key进行比较，如果都不相等，则划出一个节点存储数据
如果节点长度即链表长度大于阈值8并且数组长度大于64，则进行将链表变成红黑树。
面试题：
1、何时发生哈希碰撞和什么是哈希碰撞，如何解决哈希碰撞？
只要两个元素的key计算的哈希码值相同就会发生哈希碰撞。JDK8之前使用链表解决哈希碰撞。JDK8之后使用链表+红黑树解决哈希碰撞。
2、如果两个键的hashCode相同，如何存储键值对？
hashCode相同，通过equals比较内容是否相同。
相同：则新的value覆盖之前的value
不相同：则将新的键值对添加到哈希表中
3、为什么要引入红黑树？
如果节点太多，遍历时间复杂度就是O(n),红黑树的时间复杂度为O(logn)
2、hashMap继承关系
3、HashMap集合类的成员变量
3.1 成员变量
1、序列化版本号
private static final long serialVersionUID = 362498820763181265L;
2、集合的初始化容量（必须是二的n次幂)
//默认的初始容量是16 – 1<<4相当于12的4次方—116
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
问题：为什么必须是2的n次幂？如果输入值不是2的幂比如10会怎么样？
HashMap构造方法还可以指定集合的初始化容量大小：
HashMap(int initialCapacity) 构造一个带指定初始容量和默认加载因子 (0.75) 的空 HashMap。
根据上述讲解我们已经知道，当向HashMap中添加一个元素的时候，需要根据key的hash值，去确定其在数组中的具体位置。 HashMap为了存取高效，要尽量较少碰撞，就是要尽量把数据分配均匀，每个链表长度大致相同，这个实现就在把数据存到哪个链表中的算法。
这个算法实际就是取模，hash%length，计算机中直接求余效率不如位移运算(这点上述已经讲解)。所以源码中做了优化,使用 hash&(length-1)，而实际上hash%length等于hash&(length-1)的前提是length是2的n次幂。
为什么这样能均匀分布减少碰撞呢？2的n次方实际就是1后面n个0，2的n次方-1 实际就是n个1；
举例：
说明：按位与运算：相同的二进制数位上，都是1的时候，结果为1，否则为零。
例如长度为8时候，3&(8-1)=3 2&(8-1)=2 ，不同位置上，不碰撞；
例如长度length为8时候，8是2的3次幂。二进制是：1000
length-1 二进制运算：
1000
- 1111如下所示：
hash&(length-1)
3 &(8 - 1)=3
00000011 3 hash
& 00000111 7 length-100000011-----》3 数组下标hash&(length-1)
2 & (8 - 1) = 2
00000010 2 hash
& 00000111 7 length-100000010-----》2 数组下标说明：上述计算结果是不同位置上，不碰撞；
例如长度为9时候，3&(9-1)=0 2&(9-1)=0 ，都在0上，碰撞了；
例如长度length为9时候，9不是2的n次幂。二进制是：00001001
length-1 二进制运算：
1001
- 11000如下所示：
hash&(length-1)
3 &(9 - 1)=0
00000011 3 hash
& 00001000 8 length-100000000-----》0 数组下标hash&(length-1)
2 & (9 - 1) = 2
00000010 2 hash
& 00001000 8 length-100000000-----》0 数组下标说明：上述计算结果都在0上，碰撞了；
总结：
1.由上面可以看出，当我们根据key的hash确定其在数组的位置时，如果n为2的幂次方，可以保证数据的均匀插入，如果n不是2的幂次方，可能数组的一些位置永远不会插入数据，浪费数组的空间，加大hash冲突。
2.另一方面，一般我们可能会想通过 % 求余来确定位置，这样也可以，只不过性能不如 & 运算。而且当n是2的幂次方时：hash & (length - 1) == hash % length
3.因此，HashMap 容量为2次幂的原因，就是为了数据的的均匀分布，减少hash冲突，毕竟hash冲突越大，代表数组中一个链的长度越大，这样的话会降低hashmap的性能