- HashMap 的底层数据结构
hashmap是k，v形式的数据存储结构，实际存储数据的是一个一个的Node
static class Node<k,v> implements Map.Entry<k,v> {
final int hash; //hash值
final K key; //key
V value; // value
Node<k,v> next; //指向下一个节点的指针
}
hashmap 数据结构是由数组+链表/红黑树来实现的
image.png
- 为什么要改成“数组+链表+红黑树”？
主要是为了提升在 hash 冲突严重时（链表过长）的查找性能，使用链表的查找性能是 O(n)，而使用红黑树是 O(logn) - 那在什么时候用链表？什么时候用红黑树？
插入，默认情况下是使用链表节点。当同一个索引位置的节点在新增后达到9个（阈值8）：如果此时数组长度大于等于 64，则会触发链表节点转红黑树节点（treeifyBin）；而如果数组长度小于64，则不会触发链表转红黑树，而是会进行扩容，因为此时的数据量还比较小。对于移除，当同一个索引位置的节点在移除后达到 6 个，并且该索引位置的节点为红黑树节点，会触发红黑树节点转链表节点（untreeify）。 - 为什么转换的阈值是8？
我们平时在进行方案设计时，必须考虑的两个很重要的因素是：时间和空间。对于 HashMap 也是同样的道理，简单来说，阈值为8是在时间和空间上权衡的结果。
理想情况下，使用随机的哈希码，节点分布在 hash 桶中的频率遵循泊松分布，按照泊松分布的公式计算，链表中节点个数为8时的概率为 0.00000006（跟大乐透一等奖差不多，中大乐透？不存在的），这个概率足够低了，并且到8个节点时，红黑树的性能优势也会开始展现出来，因此8是一个较合理的数字 - 为什么转为红黑树是8，红黑树转链表是6？
如果我们设置节点多于8个转红黑树，少于8个就马上转链表，当节点个数在8徘徊时，就会频繁进行红黑树和链表的转换，造成性能的损耗 - HashMap 的默认初始容量是多少？HashMap 的容量有什么限制吗？
默认初始容量是16。HashMap 的容量必须是2的N次方，HashMap 会根据我们传入的容量计算一个大于等于该容量的最小的2的N次方，例如传 9，容量为16。 - 为什么HashMap的容量必须是2的N次方？
计算索引位置的公式为：(n - 1) & hash，当 n 为 2 的 N 次方时，n - 1 为低位全是 1 的值，此时任何值跟 n - 1 进行 & 运算会等于其本身，达到了和取模同样的效果，实现了均匀分布。实际上，这个设计就是基于公式：x mod 2^n = x & (2^n - 1)，因为 & 运算比 mod 具有更高的效率。 - 为什么初始容量是16？
16是2的N次方，并且是一个较合理的大小。如果用8或32，我觉得也是OK的。实际上，我们在新建 HashMap 时，最好是根据自己使用情况设置初始容量，这才是最合理的方案。 - 为什么负载因子是0.75?
这个也是在时间和空间上权衡的结果。如果值较高，例如1，此时会减少空间开销，但是 hash 冲突的概率会增大，增加查找成本；而如果值较低，例如 0.5 ，此时 hash 冲突会降低，但是有一半的空间会被浪费，所以折衷考虑 0.75 似乎是一个合理的值。 -
插入的基本流程？
image.png - key的hash值如何计算？为什么？
key的hashcode的高16位与低16位异或产生的值
当table长度较小时，让高位也参与运算，获得更好的hash值 -
扩容的基本流程？
image.png
image.png - 红黑树和链表都是通过 e.hash & oldCap == 0 来定位在新表的索引位置，这是为什么？
