HashMap的底层原理
HashMap的底层原理
+ View Code
添加元素
+ View Code
这里我们的16，17到了后面去了，这涉及到哈希表的底层，set集合的底层其实也是hashmap
哈希桶也是有索引的，哈希桶的初始容量是十六
1<<4;是1左移四位，也就是1乘以2的4次方，>>表示右移除以。
假设这里有一个元素要进来想往hashmap里面存，先是用hashcode.equals判断是否有值然后通过put存放进去
通过计算哈希值来放入tab中也就等于我们的数组中
通过这个方法计算哈希值扰乱函数低十六位异或高十六位 这个操作叫做扰乱函数
将计算的哈希值右移16位，让哈希值尽量分散开，查询map的时候尽量快一点，所以也哈希表也叫散列表
异或相同为0不同为1
计算出来的哈希值这么大怎么将元素存入一个索引为0-15的哈希表去
长度必须是二的几次方
如果我们自定义的容量不是二的几次方也会强转为2的次方
这么做的目的就是为了计算存放索引
默认长度16的的2进制是10000 看源码的操作
这里将10000-1得到1111 再进行与操作 得到0101也就是5索引 这种操作叫做路由寻址
我们将元素存到5索引
假设这个又来个一个元素 通过计算也存到了5索引 就发生了哈希碰撞（哈希冲突）第一个存进去的元素后面有个拉链 将他们拉起来 1.7是头插法1.8是尾插法
如果我们的数组存满了就会扩容，比如16扩容成了32，不能让后面16位空着，要尽量让它散列，1.7会出现环形链表也就是著名的约瑟夫环问题。
在 Java 1.8 中，如果链表长度到8，数组容量到64，链表会树化；删除元素红黑树长度小于6，红黑树退化为链表;（这里的数组容量指的是数组长度，不是64个元素）
何时扩容 数组中 长度*加载因子（0.75)个位置上都有元素，再存会扩容
16乘以0.75等于12
+ View Code
+ View Code
+ View Code
扩容一下
+ View Code
在扩容的时候会将链表分成低位链和高位链，扩容时低位链不变，高位链分配是原索引加原长度（下图原索引为1原长度为16，扩容后分配到17索引）
如果在扩容的时候这个链表已经树化了，树里面也存放了计算上一个元素的地址值，虽然它是一棵树，但是它里面也有链表所用到的地址值
为什么链表长度到8了进化红黑树，不是7或者9呢，这就涉及到概率论：泊松分布
这个链表到8的概率其实是非常低的 ，Java是优先扩容的，而不是优先拉链，哈希碰撞的概率其实是很低的。
全图
来源：https://www.cnblogs.com/demowei/p/14771909.html