前言
在说HashMap之前，我们先说一说hash冲突。当数据通过hash算法求得hash值的时候，是不可避免的出现相同的hash值，这也叫做hash冲突。通常我们会采用4种方式去应对hash冲突的情况。
HashMap的简介
HashMap是基于映射(键值对)处理的数据数据结构。是程序员使用的频率最高的数据结构之一，在jdk1.8之后引入红黑树，优化底层数据结构。
传统的数据的数据结构是在内存中申请一段连续的内存空间，查询的时间复杂度为O(1)，而插入和删除是O(n)，这是因为伴随着数据的移动。
在Java7中数组+链表的形式，一旦链表过长那么会很影响put和get的效率，所以在Java8之后引入了红黑树+链表来代替链表。
为什么不一直使用链表？
我们是很清楚链表的弊端的，就是查询的效率很低，是O(n)，当数据量很大的时候是不能接受这样的查询效率的。在JDK1.8之前它的结构大概是这样的
所以会一直花费心思在扰动函数上，让hash的更加分散。
为什么选择红黑树？
我们通过比较几种树的特性来说为什么选择了红黑树。
二叉查找树
我们最常见的就是二叉查找树，它的特点就是左节点永远都比它的父节点小，右节点一定比它的父节点大，比如下图
但是它有个很大的问题，就是容易瘸腿，比如下面
当瘸腿的时候，你会发现这和链表没啥区别了。然后就出现了下面这个树。
平衡二叉树
这个树的特性就是每一个节点的左子树和右子树的高度差至多等于1，如果大于1就需要进行左旋或者右旋，这样就保证了它的查询的时间复杂度始终保持在O(LogN)。如下图
虽然查询满足了我们的需求，但是它的问题是在插入和删除的时候维护树上面复杂很多，需要频繁的调整树结构来保证查询效率，所以就引申出了红黑树
红黑树
相对于平衡二叉树，它的特点如下
- 根节点是黑色的。
- 所有的叶子节点都是黑色的，并且不存数据。
- 任何相邻的节点不能同时为红色，红色节点是被黑色节点隔开的。
- 每个节点到达它可达的叶子节点的路径，都经过相同数目的黑色节点。
主要优点就是：它不追求绝对的平衡，插入最多两次旋转，删除最多三次旋转。
具体的实现我会单独的放到我数据结构专栏，太复杂了。。。
HashMap什么时机会从链表转为红黑树？什么时候再转回来呢？
在上面我说了，JDK1.8之后是链表+红黑树来替代的链表，组合的意思就是代表着这两种数据结构是需要切换的，这个时机就是链表长度到达8的时候进行切换，当然这个只是条件之一，还有一个条件是想转换为红黑树，table中，也就是hash表的横向容量必须达到64，否则就会优先resize hash表。等讲完resize的方法的时候再总结一下HashMap中的存储数据的结构。所以就引出一些疑问。
为什么不在hash冲突的时候直接就使用红黑树呢？
因为红黑树的空间是链表的两倍，虽然能提升查询效率，但是插入的速度慢了很多，还涉及到平衡树的时候的各种旋转变色，所以链表其实是起到一个缓冲的作用。
为什么要到达8的时候转为红黑树呢？
原文注释上说，当hashCode遵循泊松分布的时候，因为hash冲突造成桶的的链表长度等于8的概率只有0.00000006。官方认为这个概率足够低，当需要红黑树介入的时候，你可以想象一下你的数据会是什么样的。
什么时候从红黑树转为链表呢？
当红黑树节点小于6的时候就会转回来，为什么是6呢，首先不能是8，因为如果是8的话，你会面临着频繁的链表与红黑树的切换，就让我想起了那句台词，我进来了，我出来了，我又进来了，我又出来了。。。。而选择6不选择7是因为，官方经过大量的验证，发现，当红黑树节点小于6的时候，它的优势就不那么明显了，不足以抵消维护红黑树的开销，之前听过一个大哥这么说的，经过工业严谨的实验证明，6在绝大多数的情况下表现良好。
所以我们可以看出，作者在链表转为红黑树这里考虑的非常多，就是要让两种结构达到一个均衡点，过于草率的进行结构转换的话，其实非常的影响效率。
从源码入手解析HashMap工作原理
接下来我会从源码开始一步一步引申出对HashMap的一些疑问。
我们先看一下HashMap中比较重要的一些属性，我的注释会解释相关含义
HashMap中的重要属性介绍，以及一些疑问
//默认的初始容量，1向左移动4位10000=16
static final int DEFAULT_INITIAL_CAPACITY = 1 > 16);
}
看三元表达式的后半部分就可以了。(h = key.hashCode()) ^ (h >>> 16)。用key的hashCode去异或hashcode向右移16位。接着提出几点疑问
为什么要选择异或运算，而不是与运算和或运算？
与运算的方式是同为1则为1，否则为0。或运算是有1则为1，否则为0。异或是不同为1，相同为0。这样一对比其实就能发现与运算的结构更向0靠拢，或运算的结果更向1靠拢，而异或运算更加平均。公平起见，选异或。
为什么要让hashcode异或hashcode右移16位？
首先我们要知道的是hashcode是int类型，所以占4个字节32位，hash方法可以认为是对key本身的hashcode进行二次加工，这其实和HashMap计算key的位置的方式有关系的，确定位置在putVal的方法中，为了不搞乱，我单独把它拿出来了，如下，看一下它计算位置的方式i = (n - 1) & hash，n就是hash表的长度，用长度-1然后去&hash，看着挺难懂的，其实它就等于hash%n。当然这个前提是n得是2的幂次方。因为基于&的方式去计算，要快于十进制%的计算方式很多。所以这也解释了为什么容量要设置成2的幂次倍，就是采用取模的方式取址，还要提升计算速度！
再回来说为什么要右移16位。举个例子：你的hashcode是1111110001然后&1111，等于=0001，然后下一个hashcode和上一个只是发生了高位的变化，比如1100110001然后&1111，结果其实还是0001，那就会导致计算出来的地址都一样，类似这种情况那大家不都在一个桶里了吗，当长度较低的时候，只有hashcode的低16位参与运算了，所以没有选择用hash直接计算地址，向右移动16位相当于让高位下来了，然后再去异或hashcode，相当于高低位结合了，也就提升了hash值的散列程度。
为什么负载因子要设置成0.75？为什么不设置成1呢？
设置成1的话就代表着，只有table装满了的时候才会去扩容，这时候所有键的hash都需要重新计算，这比较损耗性能，同时，这也会导致冲突的hash比较多。所以既不能频繁的扩容，也不能太晚的扩容，所以0.75是一个很均衡的值，而且0.75也就是四分之三，用table的长度去乘这个负载因子得出来的数就是扩容的阈值，而0.75刚好使得这个阈值是一个整数，因为上面我们提到的，容量是2的幂次倍。
那么说完为什么容量要设置成2的幂次倍了，我们再说一下它是怎么保证的
其实就是和构造方法相关了，在这里我就直接写了，对后面看构造函数的源码也是有帮助的，它的构造方法中有个非常关键的方法就是tableSizeFor，这个方法就是重新计算容量的，即便你重新传了初始容量，也要计算得出真实容量，我们看一下源码的实现
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n = MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
整个过程就是为了找到传入容量最近的大于它的一个2次幂的值，下面是我根据上面的算法写的几个例子
从例子中就可以很清楚的看出来为什么要传入的容量-1去计算。
接下来，我接着走源码，看看构造方法是怎么样的逻辑
HashMap的构造方法的工作流程解析
它的构造方法有四个，我这里只解析其中一个，如下
//参数位Map的构造函数，看过这个的解析，那么，其他三个一看就明白了
public HashMap(Map
