JDK1.7采用数组+链表
JDK1.8采用数组+链表+红黑树
HashMap在存储K-V时，实际上会把K-V封装成一个Entry对象，数组和链表上存储的实际上是一个个Entry对象
因为使用了数组，所以要确定下标的位置，方便存储
所以采用了求key的hashcode，并取余数组的长度，但实际在源码中，并不是取余，因为取余很有可能得到相同的数组下标，引起hash冲突，所以用到了hashcode&（数组长度-1）
对于这个key是采用通过hashcode与自己进行右移和异或运算，这样就保证了计算出来的hash值足够随机分布，产生的数组下标也足够随机。
而对于hashcode&（数组长度-1） 这样做的好处是：
1.保证数组不会发生越界 2.保证元素尽可能的均匀分布
在hashmap中，数组的长度一定是2的幂次方，因此数组长度的二进制是1后面偶数个0，而长度-1则变成了0后面偶数个1，最高位是0，和hash值进行与运算，结果一定不会比数组长度大，而且如果-1之后变成偶数的话，最后一位都会别舍弃，有的位置根本保存不到数据，造成空间浪费。如果使用十进制取余的话，速度也会变慢，所以既要达到分配均匀，又要实现速度，容量一定是2的幂次方。
当算出对象的下标一致时候，会出现hash冲突，而JDK1.7会采用头插法（保证get的效率）
因为采用头插法的话，对于链表来说，插入链表的头部效率要更快一些，如果插入尾部，链表本身查询效率就慢，还需要遍历链表，速度会更慢。
如果在头部插入一个Entry对象，要进行查找时，并不能找到，所以它会进行下移的操作，就是把当前的引用换成刚刚插入的头节点的引用。
在使用hashmap无参构造的时候，其实什么都没有做
只是初始化两个参数 一个是数组的容量（1<<4） 16，一个是加载因子0.75
只有当第一次put的时候，才会进行数组的容量的初始化
并且初始化阈值 数组的容量*加载因子（12）
也就是说HashMap并没有在数组容量为16的时候进行扩容，而是在容量为12的时候就进行扩容了，为防止数据量大时候，可以起到缓冲作用
为什么加载因子是0.75？
加载因子其实是表示Hsah表中元素的填满的程度。
加载因子越大,填满的元素越多,空间利用率越高，但冲突的机会加大了。
反之,加载因子越小,填满的元素越少,冲突的机会减小,但空间浪费多了。
冲突的机会越大,则查找的成本越高。反之,查找的成本越小。
因此,必须在 "冲突的机会"与"空间利用率"之间寻找一种平衡与折衷。
扩容：JDK1.7 是先进行扩容，再添加元素，而JDK1.8是先添加元素，再扩容
为什么要扩容？
如果put的元素过多，那么get的效率就会越低，为了让put和get的效率都比较高，所以会对数组进行扩容
在JDK1.7中必须满足两个条件才会进行扩容
先判断当前数组容量是否大于阈值，并且put进入的位置已经有元素了（只有1.7有），才会进行扩容
扩容是2倍的数组长度，会生成一个新的数组，然后把旧的值，根据hashcode再去进行&运算，再次确定下标进入到新数组中，这样做也是为了均匀分布
JDK1.8采用了数组+链表+红黑树
为什么要加入红黑树？
在某些极端的情况下，链表可能还是特别长，对于链表来说，插入速度快，查询效率低，而对于红黑树，查询和插入的速度都比较高，所以采用了这种的方式
同时引用红黑树也是防止用户自行实现hash算法影响性能
对于key的hash算法，JDK1.8是采用了右移16异或运算，JDK1.7比较复杂是因为要增加查询效率，而1.8引入红黑树就对此进行了简化。
而JDK1.8为什么采用了右移16位？
是为了减少碰撞，进一步降低了hash冲突的几率，当数组长度很短时，只有低位的hashcode值参与运算，而右移可以让高位参加运算，更好的均匀分布，否则冲突太多
链表和红黑树的转化？
有一个树化的阈值，当大于8时，会进行数化，当小于等于6时，会转化为链表，这样也是为了防止链表、红黑树的返回横跳，影响效率
在进行树化的时候，要判断元素个数是否是8个，肯定要遍历链表，所以JDK1.8采用了尾插法
如果要插入一个元素，要判断key和当前的key是否相等，如果不相等，再去判断当前的节点是一个什么样的节点，如果是树节点，那么久遍历树，如果是链表，就遍历链表，同时也会去判断是否到了尾节点，如果到了尾节点，就把元素加入到尾节点
其实链表元素个数等于8时候并不一定会进行树化
还有一个判断，是当前数组容量是否小于64，如果小于64不会进行树化，而是进行扩容
为什么是64？
通过扩容可以把链表进行缩短，并且扩容后会有更多的存储空间，而如果是64再进行扩容的话，内存空间占用会更大
