meta|Java集合面试题看这篇就够了( 五 )

hash & oldCap == 0 的元素留在原来位置，否则 新位置 = 旧位置 + oldCap

当根据 key 的 hash 值寻址计算确定桶位下标 index 时，如果HashMap 的数组长度 tab.length 是 2 的 n 次幂数，那么就可以保证新插入数组中的数据均匀分布，每个桶位都有可能分配到数据，而如果数组长度不是 2 的 n 次幂数，那么就可能导致一些桶位上永远不会被插入到数据，反而有些桶位频繁发生 hash 冲突，导致数组空间浪费，冲hash 突概率增加。

14.说说HashMap的put方法执行流程？

计算key的hash值
如果桶（数组）数量为0 ，则初始化桶
如果key所在的桶没有元素，则直接插入
如果key所在的桶中的第一个元素的key与待插入的key相同，说明找到了元素，转后续流程（9）处理
如果第一个元素是树节点，则调用树节点的putTreeVal()寻找元素或插入树节点
如果不是以上三种情况，则遍历桶对应的链表查找key是否存在于链表中
如果找到了对应key的元素，则转后续流程（9）处理
如果没找到对应key的元素，则在链表最后插入一个新节点并判断是否需要树化
如果找到了对应key的元素，则判断是否需要替换旧值，并直接返回旧值
如果插入了元素，则数量加1并判断是否需要扩容

15.说说HashMap的get方法执行流程？

计算key的hash值
找到key所在的桶及其第一个元素
如果第一个元素的key等于待查找的key ，直接返回
如果第一个元素是树节点就按树的方式来查找
否则就按链表方式查找
如果都没有，返回null

16.说说HashMap的resize方法执行过程？

如果使用是默认构造方法，则第一次插入元素时初始化为默认值，容量为 16 ，扩容门槛为12
如果使用的是非默认构造方法，则第一次插入元素时初始化容量等于扩容门槛，扩容门槛在构造方法里等于传入容量向上最近的2的n次方
如果旧容量大于0 ，则新容量等于旧容量的2倍，但不超过最大容量2的30次方，新扩容门槛为旧扩容门槛的2倍
创建一个新容量的桶
搬移元素，原链表分化成两个链表，低位链表存储在原来桶的位置，高位链表搬移到原来桶的位置加旧容量的位置

17.HashMap什么时候会树化？必须满足两个条件：
>8
>=64

当链表长度超过树化阈值 8 时，先尝试扩容来减少链表长度，如果数组容量已经 >=64 ，才会进行树化。
???面试官追问：那什么时候树化退化？
<= 6

18.HashMap底层为什么选择红黑树而不用其他树，比如二叉查找树？二叉查找树在特殊情况下也会变成一条线性结构，和原先的长链表存在一样的深度遍历问题，查找性能慢，
使用红黑树主要是为了提升查找数据的速度，红黑树是平衡二叉树的一种，插入新数据（新数据初始是红色结点插入）后会通过左旋，右旋，变色等操作来保持平衡，解决单链表查询深度的问题。
???面试官追问：那为什么要将链表中转红黑树的阈值设为8？
之所以以 8 为树化门槛，是因为经过大量测试， 8 这个值是最合适的。理想情况下，使用随机的哈希码，节点分布在 hash 桶中的频率遵循泊松分布，按照泊松分布的公式计算，长度超过 8 的链表出现概率是