一、HashMap底层数据结构
JDK1.7及之前：数组+链表
JDK1.8：数组+链表+红黑树
JDK1.7 到 JDK1.8 这其中HashMap的性能也只提高了7%~8% 左右

HashMap添加元素分析

当添加元素时，会通过哈希值和数组长度计算计算下标来准确定位该元素应该put的位置，通常我们为了使元素时分布均匀会使用取模运算，用一个值去模上总长度，例如：index=hashCode % arr.length（实际并非这样，后面讲解）,计算出index后，就会将该元素添加进去，理想状态下是将每个值都均匀的添加到数组中。问题是不可能达到这样的理想状态，这时候就会产生哈希冲突，例如：小龙女通过计算添加到了数组3号位置，但是此时杨过这个元素通过计算产生了一个与小龙女相同的索引位置，这是就产生了哈希冲突

为什么数组的长度必须是2的指数次幂

这里的阈值使用了一个tableSizefor方法，它的作用是返回一个大于输入参数且最*的2的整数次幂的数

看一下tableSizefor方法如下，这里使用的是位运算，假设n的二进01xxx…xxx，接着对n右移1位001xx…xxx，再位或：011xx…xxx；对n右移2为00011…xxx，再位或：01111…xxx，此时前面已经有四个1了，再右移4位且位或可得8个1，同理，有8个1，右移8位肯定会让后八位也为1。综上可得，该算法让最高位的1后面的位全变为1。最后再让结果n+1，即得到了2的整数次幂的值了。cap-1再赋值给n的目的是让找到的目标值大于或等于原值

，数组一旦达到容量的阈值的时候就需要对数组进行扩容。那么扩容就意味着要进行数组的移动，数组一旦移动，每移动一次就要重回记算索引，这个过程中牵扯大量元素的迁移，就会大大影响效率。那么如果说我们直接使用与运算，这个效率是远远高于取模运算的

为什么加载因子是0.75

加载因子如果定的太大，会产生大量的哈希碰撞，同时产生更多的链表

但如果设置的过小，查询效率很高，但消耗了大量空间。

为什么链表长度大于等于8时转成了红黑树

这里要提到一个概率论中的泊松分布，因为链表长度大于等于8时转成红黑树正是遵循泊松分布，先来看一下泊松分布
链表中元素个数为8时的概率已经非常小。
另一方面红黑树均查找长度是log(n)，长度为8的时候，*均查找长度为3
如果继续使用链表*，*均查找长度为8/2=4，这才有转换为树的必要。