Webpack5 入门与实战，前端开发必备技能

Java HashMap的常见问题——扩展、树形结构、死链问题 写在前面。

HashMap是一种常用的数据结构，在面试过程中经常被问到。本文对知识点做了问答分析，重点是哈希冲突、扩展死链、容量2的n次方等问题~

1.7和1.8有什么区别？ 1.7是数组+链表。 1.8是数组+链表【超过阈值就会变成红黑树】 如何解决哈希冲突问题 扩大电信容量 情况

链表长度超过8。 元素数量超过数组数量的75%。

树形规则 情况

链表长度超过8。 此时，查看数组长度是否超过64。如果是的话，它将被树化，否则，它将简单地被扩展。

为什么需要种树？ 事实上，正常元素不会超过阈值。只有插入一堆哈希值相同的重复元素，才能达到阈值。这简称为Dos攻击。 一旦元素多了，查找链表的效率远不如红黑树。 ♂爬树一定更好吗？ 不会，维护红黑树比链表占用空间大，而且当链表长度足够短时，查找链表的效率比红黑树高？？ 为什么选择0.75和8？

如果哈希值足够随机，它在哈希表中按照泊松分布。当加载因子为0.75时，长度超过8的链表的出现概率为0.0000006。选择树化阈值8以使树化概率足够小。

退化规则 扩展容量时链表的长度 移除节点。 root，root.left，root.right，root.left.left中有一个为空，也会退化为链表(见移除前的情况) 为什么需要第二个哈希？ 先得到key的hashCode的值h，然后将h和h右移16位进行异或运算。 本质上，一个数的最后x位的低16位与高16位进行XOR运算，因为在前面的(n-1) & hash计算中，只有hash变量的最后x位会参与运算。让高16位也参与哈希运算可以减少冲突。 为什么要用2的n次方？ 为了方便操作 只有2的n次方，去-1，才能用&代替%。 为了促进容量扩展 扩展容量时重新计算索引效率更高:hash & oldCap == 0的元素保留在原来的位置。 否则，新位置=旧位置+旧容量(旧容量:原始容量) 因为HashMap的初始容量是2的幂，扩展后的长度是原来的两倍，新的容量也是2的幂，所以元素要么在原来的位置，要么移动到原来位置的2的幂。 看这张照片。n是桌子的长度。 图A显示了扩展前确定索引的key1和key2的位置。 图b示出了扩展后由key1和key2确定的索引位置。

元素重新计算hash后，因为n变成了2倍，那么n-1的掩码范围在高位多了1位(红色)，所以新的索引会变成这样:

所以在扩容的时候，只需要看原hash值的新增位是0还是1[直接hash & oldCap，就可以知道是0还是1] 如果为0，则索引没有改变；如果为1，则成为原始索引+oldCap。 2的n次方可以吗？ 可以，因为2的n次方也会有缺陷。比如给定值都是偶数，而且无论如何哈希后的模数都是偶数，所以分布不均匀。

此时，如果以质数作为容量，则平均分配。

注意 第二个散列被设计成与容量是2的n次方的设计前提相匹配。如果哈希表的容量不是2的n次方，则第二次哈希是不必要的。 容量为2的n次方的设计在索引计算上效率更高，但是hash的分散性不好，需要二次hash作为补偿。不采用这种设计的典型例子是Hashtable。 并发扩展和数据丢失 主要是第一个节点吧？因为第一个来自新节点。 Jdk1.7并发扩展死链问题 在jdk1.7中，采用第一种插入方式。E指针表示当前要展开的节点，next表示下一个要展开的节点。插入E，直到E为空。 假设现在有两个线程1和2，您想要扩展一个Map。

线程1的局部变量e指向节点a，next指向节点b。 线程2的局部变量也是如此。这时候线程2先扩充容量，最后结果变成b->a因为是头插入法。 然而，此时，当我们来到线程1时，局部变量不会被改变。E还是指向A，next或者B，所以我们把A的头插上，把E更新为next，就成了B。 1线程继续插B，没问题，结果变成[b->a]。看似没有问题，但随后判断E已经没有下一个: 发现E的下一个是A，要继续在第一个插入A。插入A后发现A的下一个是B，就发了，没完没了。

download：Webpack5 入门与实战，前端开发必备技能朝辞白帝彩云间