结构
JDK1.8 数组+链表（红黑树）
插入原理
1.判断数组是否为空，为空进行初始化
2.不为空，计算k的hash值，通过(n-1)&hash计算应存放在table[index]中
3.查看table[index]是否存在数据，没有数据就构造一个Node节点存放在table[index]中
4.存在数据，说明发生了hash冲突，继续判断key是否相等，相等，用新的value替换原数据
5.如果不相等，判断当前节点类型是不是树型节点，如果是树型节点，创造树型节点插入红黑树中
6.如果不是树型节点，创建普通Node加入链表中，判断链表长度是否大于8，大于的话链表转换为红黑树
7.插入完成之后判断当前节点数是否大于阈值，如果大于开始扩容为原数组的两倍
HashMap如何设定初始容量的大小
如果new HashMap()不传值，默认大小是16，负载因子是0.75
如果自己传入初始大小为k，初始化大小为大于k的2的整数次方，例如如果传10，大小为16
HashMap的哈希函数如何设计？
先拿到通过key的hashcode,是32位的int值，然后让hashcode的高16位和低16位进行异或操作
JDK1.8对HashMap的优化
1.数据+链表改成了数据+链表或红黑树
原因：防止发生hash冲突，链表长度过长，将时间复杂度由O(n)降为O(logn)
2.链表的插入方式从头插法改成了尾插法
原因：1.7头插法扩容时，头插法会使链表发生反转，多线程环境下会产生环。
A线程在插入节点B，B线程也在插入，遇到容量不够时开始扩容，重新hash放置元素，采用头插法，后遍历到的B节点放入了头部，这样形成了环。
3.扩容的时候1.7需要对原数组中的元素进行重新hash定位在新数组的位置。1.8采用更简单的判断逻辑，位置不变或索引+旧容量大小
原因：这是由于扩容是扩大为原数组大小的 2 倍，用于计算数组位置的掩码仅仅只是高位多了一个 1，怎么理解呢？
扩容前长度为 16，用于计算(n-1) & hash 的二进制 n-1 为 0000 1111，扩容为 32 后的二进制就高位多了 1，为 0001 1111。
因为是& 运算，1 和任何数 & 都是它本身，那就分二种情况，如下图：原数据 hashcode 高位第 4 位为 0 和高位为 1 的情况；
第四位高位为 0，重新 hash 数值不变，第四位为 1，重新 hash 数值比原来大 16（旧数组的容量）
4.在插入时，1.7先判断是否需要扩容，再插入。1.8先进行插入，插入完成后再判断是否需要扩容
HashMap线程安全性
HashMap不是线程安全的
在多线程环境下，1.7会产生死循环、数据丢失、数据覆盖的问题
1.8中会有数据覆盖的问题
eg:当A线程判断index位置为空后正好挂起，B线程开始往index位置写入节点数据，这时A线程恢复现场，执行赋值操作，就把B线程的数据给覆盖了
解决HashMap线程不安全的方法
1.HashTable
直接在操作方法上加synchronized关键字，锁住整个数组，粒度比较大。
2.Collections.synchronizedMap
使用Collections集合工具的内部类，通过传入Map封装出一个SynchronizedMap对象，内部定义一个对象锁，方法内通过传入对象锁实现
3.ConcurrentHashMap
使用分段锁，降低了锁粒度，让并发度大大提高
ConcurrentHashMap分段锁的实现原理
ConcurrentHashMap成员变量使用volatile修饰，免除了指令重排序，同时保证内存可见性
使用CAS操作和synchronized结合实现赋值操作，多线程只会锁住当前操作索引的节点
如上图，线程A锁住A节点所在链表，线程B锁住B节点所在链表，操作互不干涉
链表转红黑树和红黑树转链表的阈值是多少？
链表转红黑树：8
红黑树转链表：6
因为经过计算，在 hash 函数设计合理的情况下，发生 hash 碰撞 8 次的几率为百万分之 6，概率说话。因为 8 够用了，至于为什么转回来是 6，因为如果 hash 碰撞次数在 8 附近徘徊，会一直发生链表和红黑树的转化，为了预防这种情况的发生。
HashMap内部节点是有序的吗？
无序，根据hash值随机插入
有序的Map?
LinkedHashMap
LinkedHashMap内部维护了一个单链表，有头尾节点，同时LinkedHashMap节点Entry内部除了继承HashMap的Node属性，还有before和after用于标识前置节点和后置节点。可以实现插入的顺序或访问顺序排序
TreeMap
TreeMap按照Key的自然顺序或者Comparator的顺序进行排序，内部通过红黑树实现。所以要么key所属的类实现Comparable接口，或者自定义一个实现了Comparator接口的比较器，传给TreeMap用户key的比较
