前言
HashMap采用Entry数组来存储key-value对，每一个键值对组成了一个Entry实体，Entry类实际上是一个单向的链表结构，它具有Next指针，可以连接下一个Entry实体，以此来解决Hash冲突的问题。数组存储区间是连续的，占用内存严重，故空间复杂的很大。但数组的二分查找时间复杂度小，为O(1)；数组的特点是：寻址容易，插入和删除困难；链表存储区间离散，占用内存比较宽松，故空间复杂度很小，但时间复杂度很大，达O（N）。链表的特点是：寻址困难，插入和删除容易。HashMap可以使用null作为key，但是尽量不建议这样使用。HashMap底层的数据存储结构
Entry[]数组对象
HashMap由数组+链表
JDK1.8HashMap的改变
1，HashMap是由数组+链表+红黑树
在Jdk1.8中HashMap的实现方式做了一些改变，但是基本思想还是没有变得，只是在一些地方做了优化，下面来看一下这些改变的地方,数据结构的存储由数组+链表的方式，变化为数组+链表+红黑树的存储方式，当链表长度超过阈值（8）时且数组的容量大于等于64，将链表转换为红黑树。在性能上进一步得到提升。
为什么要引入红黑树？
红黑树是一种自平衡二叉查找树，是计算机科学领域中的一种数据结构，典型的用途是实现关联数组，存储有序的数据。它是在年由RudolfBayer发明的，别称"对称二叉B树"，它现代的名字由LeoJ.Guibas和RobertSedgewick于年写的一篇论文中获得的。它是复杂的，但它的操作有着良好的最坏情况运行时间，并且在实践中是高效的。它可以在O(logn)时间内做查找，插入和删除，这里的n是树的结点个数。是为了解决链表的查询效率低的问题，链表的查询时间复杂度O(N),尤其针对链表长度很长的时候。就是hash冲突比较严重的时候，转换为很长的单向链表。此时的时间复杂度O(N)。在这个时候符合泊松分布。使用红黑树后，可以使得查询时间复杂度提升到O(logn),红黑树是可以旋转。达到一个动态的平衡。2，为什么数组的容量是2的倍数，扩容为啥是两倍目的减少碰撞几率。2的倍数-1得到二进制位全部是1，和计算值后保证结果是单一，如果二进制位数0越多，hash碰撞的概率越大。比如看下面一个例子，2的4次方减一，二进制值是，结果是，还是。结果值是单一的不变。如果不是2的4次方，比如15，二进制值是，结果是，结果也是，此时和就发送碰撞。数组扩容后的索引位置如何变化？数组初始长度=16。
32位的二进制值表示如下：
n-00000
hash10000
(n-1)hash1的结果=5（index=5的位置）
n-00000
hash20001
(n-1)hash2的结果=5（index=5的位置）
在数组长度为16的时候，他们两个hash值的位置是一样的，用链表来处理，出现一个hash冲突的问题
如果数组的长度扩容之后=32，重新对每个hash值进行寻址，也就是用每个hash值跟新数组的length-1进行与操作
n-00001
hash10000
(n-1)hash1的结果=5（index=5的位置）
n-00001
hash20001
(n-1)hash2结果=21（index=21的位置）
判断二进制结果中是否多出一个bit的1，如果没多，那么就是原来的index，如果多了出来，那么就是index+oldCap，oldCap是初始容量，通过这个方式，就避免了rehash的时候，用每个hash对新数组.length取模，取模性能不高，位运算的性能比较高。
扩容后，链表拆分成两部分，高位和低位，低位不变，高危多出一个0还是一个1.
3，链表也是为了解决hash冲突对key进行哈希的时候，需要找到对应在数组中的索引位置，如果不同的key在数组中占用形同的索引位置，需要怎么存放？--链表就诞生了。不同key在哈希后在Entry[]相同的位置，根据key-value形式存储在链表中，在链表的尾部插入。4，红黑树什么时候会退化成链表当链表的长度小于6，且有在resize的时候才会根据UNTREEIFY_THRESHOLD进行转换。HashMap的负载因子是0.75,6/8=0.75,这个是为了满足这个实现来设计?还是是故意为之或者说是纯属巧合--留给你们去猜测5，Hash算法优化hash方法的源码如下：staticfinalinthash(Objectkey){inth;return(key==null)?0:(h=key.hashCode())^(h16)
}
这段代码的意思就是，key为null,返回0，key非空的时候，对key进行hash异或key进行hash向右移16位。异或原则就是，相同就是0，不同就是1.
例子：
10100100
0000
000001000011-?int值，32位
上面代码的目的就是把10100100的高16位和低16位进行异或。
为什么要这么做？
--为了减少hash碰撞
高低16位的异或运算可以最大程度让hash值不一样，最大程度的减少hash碰撞。
6，寻址算法优化
finalVputVal(inthash,Kkey,Vvalue,booleanonlyIfAbsent,booleanevict){NodeK,V[]tab;NodeK,Vp;intn,i;if((tab=table)==null
(n=tab.length)==0)n=(tab=resize()).length;if((p=tab[i=(n-1)hash])==null)//--重点