hashmap底层使用数组+链表+红黑树实现
默认容量是16(必须是2的幂次)，最大容量是2的30次方，默认加载因子是0.75f
Q:为什么加载因子是0.75？
A：这段话的意思大概就是当加载因子取0.75时，泊松分布参数λ（λ表示单位时间内随机事件平均发生次数）能取0.5（不考虑方差），因此可以分别算出某个桶中装0,1,2,3,4,5,6,7,8个元素的概率，由图可知，某个桶中装8个元素的概率是0.00000006（几乎不可能），这也是为什么链表转红黑树的阈值设为8（其实7个节点的时候已经转换了）
因为红黑树结构比普通链表复杂，红黑树的大小是普通链表的两倍，当某个桶中元素总个数变小时（删除或者resize），就由红黑树转化为普通链表,理想情况下，红黑树结构很少使用（因为理想情况下一个桶中有8个元素概率太低了）
至于如何保证容量是2的幂次，是通过tableSizeFor()方法来实现的,所以，如果要指定容量的话，最好指定2的幂次方的容量
从hashmap的put()方法作为入口，逐步看hashmap原理
如果map中key已经存在，旧的value将会被覆盖，并可以返回旧的value
再来看putVal方法
1，第一个if表示如果table数组里面没有元素，那么就进行扩容（resize()）
这里说明了为什么要进行二倍扩容，因为容量是2的幂次方，所以当二倍扩容后，原来的元素不是在它之前的位置，就是在oldCap+之前的下标的位置
eg:
初始容量是16，下标为1的的位置有两个元素，他们的hash值分别为1和17，当数组二倍扩容后，容量变为32，hash值为1的元素仍然放在下标为1的位置，而hash值为17的元素将会放在下标为17的位置，（17=16+1，即当前的位置=旧数组的容量+之前的下标），为什么会出现这种结果呢？
由下标i=（length-1）&hash，
（16-1=15）的二进制是01111，（32-1=31）的二进制是11111，
1的二进制是0001，17的二进制是10001,
17&15=00001，17&31=10001
最开始17与1111（15）按位与最高位参与运算结果为0，而17与11111（31）按位与最高位参与运算结果为1，因此，第二次运算结果比第一次运算结果仅高位多了一个1， 正好是旧数组的长度，就出现了这种性质。
扩容的方式也是按上述原理进行的，元素不是在新数组的之前的下标位置就是在（旧数组的容量+之前的下标）的位置，值得注意的是，源码并没有重新计算每个元素的新下标值，而是通过判断
e.hash & oldCap 是否为0，若为0，说明在之前的下标位置，若不为0(为1)，说明在（旧数组的容量+之前的下标）的位置。
eg:
oldCap=16(10)=10000(2)
1&16=0
17&16=1
Q:为什么newThr也要扩大两倍？
A：threshold定义为容量*加载因子，例如容量等于16，加载因子为0.75，那么oldThr为16*0.75=12；当容量扩大两倍后，newThr=16*2*0.75=oldThr*2
Q:什么时候要进行扩容？
A：下面这段代码在putVal方法中，当size大于threshold时，需要进行扩容；第一次初始化时需要扩容，所以当容量越大，空的位置就越多，例如加载因子固定为0.75，有25%的位置是空的
2.第二个if表示已经扩容过了，但是数组中指定下标 i 位置并没有元素，那么将i算出来之后直接插入，i=(n-1) & hash;
n为数组的容量（2的幂次方），hash的计算方式为key.hashcode^(key.hashcode<<<16);并不是网上说的key的hashcode，为什么要这样设计呢，我个人感觉是为了产生更加随机的哈希值，尽可能减少冲突，key.hashcode^(key.hashcode<<<16) 翻译过来就是key.hashcode与它的高16位进行按位异或，为什么要使用按位异或，而不使用按位与或者按位或呢，因为按位与的结果更偏向于0，而按位或的结果偏向于1，很难产生更加随机的哈希值。key.hashcode和它的高16位进行按位异或主要是为了让高16位也参与运算，尽可能减少哈希冲突。
Q:若不让高16位参与运算会怎么样?
A:由下标i=（n-1）& hash可知，i 的结果主要依赖于n，例如n=16，hash=11110011，当进行运算的时候结果主要取决于hash的低4位，hash的高4位并不参与运算（尽管它是1），因此需要将key.hashcode和它的高16位进行按位异或，从而产生更加随机的低16位（可能作者也感觉hashMap容量很难大于2的16次方吧），与n进行按位与的时候能产生更加随机的值，减少哈希冲突。
3.第三个else语句主要用于对数组中指定下标已经有元素的情况进行一些操作，包括尾插，转红黑树（7个节点的时候开始转换，间接说明链表中只有2至6个节点，因为只有1个节点的时候是在数组中）
补充一下泊松分布：转载自泊松分布的现实意义是什么，为什么现实生活多数服从于泊松分布？ - 知乎：https://www.zhihu.com/question/26441147
1 甜在心馒头店
公司楼下有家馒头店：
每天早上六点到十点营业，生意挺好，就是发愁一个事情，应该准备多少个馒头才能既不浪费又能充分供应？
老板统计了一周每日卖出的馒头（为了方便计算和讲解，缩小了数据）：
均值为：
按道理讲均值是不错的选择，但是如果每天准备5个馒头的话，从统计表来看，至少有两天不够卖，
40%的时间不够卖：
你“甜在心馒头店”又不是小米，搞什么饥饿营销啊？老板当然也知道这一点，就拿起纸笔来开始思考
2 老板的思考
老板尝试把营业时间抽象为一根线段，把这段时间用T来表示：
然后把周一的三个馒头（“甜在心馒头”，有褶子的馒头）按照销售时间放在线段上：
把T均分为4个时间段（接下来会说明为什么分4段）：
此时，在每一个时间段上，要不卖出了（一个）馒头，要不没有卖出：
T内卖出3个馒头的概率就和抛了4次硬币（4个时间段），其中3次正面（卖出3个）的概率一样了。这样的概率通过二项分布来计算就是：
如果把周二的七个馒头放在线段上，分成四段就不够了：
从图中看，每个时间段，有卖出3个的，有卖出2个的，有卖出1个的，就不再是单纯的“卖出、没卖出”了。不能套用二项分布了。解决这个问题也很简单，把T分为20个时间段，那么每个时间段就又变为了抛硬币：
T内卖出7个馒头的概率就是（相当于抛了20次硬币，出现7次正面）：
为了保证在一个时间段内只会发生“卖出、没卖出”，干脆把时间切成n份：
越细越好，用极限来表示：
更抽象一点，T时刻内卖出k个馒头的概率为：
3 p 的计算
“那么”，老板用笔敲了敲桌子，“只剩下一个问题，概率p 怎么求？”在上面的假设下，问题已经被转为了二项分布。二项分布的期望为:
那么：
4 泊松分布
有了p=u/n之后，就有：
我们来算一下这个极限：
其中：
所以：
上面就是泊松分布的概率密度函数，也就是说，在T 时间内卖出k 个馒头的概率为：
（一般来说，我们会换一个符号，让），即：
这就是教科书中的泊松分布的概率密度函数。
5 馒头店的问题的解决
老板依然蹙眉，不知道啊，没关系，刚才不是计算了样本均值：
可以用它来近似：
于是：（hashMap中0.5也是这么出来的吧，即加载因子为0.75时取0.5）
画出概率密度函数的曲线就是：
可以看到，如果每天准备8个馒头的话，那么足够卖的概率就是把前8个的概率加起来：
这样93%的情况够用，偶尔卖缺货也有助于品牌形象。
