HashMap底层
介绍一下HashMap的底层数据结构？
jdk1.8底层是由“数组+链表+红黑树”组成，而在JDK1.8之前是由“数组+链表”组成。
为什么要改成“数组+链表+红黑树”？
主要是为了提升在hash冲突严重时（链表过长）的查找性能，使用链表的查找性能是O（n），而使用红黑树是O（logn）。
那在什么时候使用链表？什么时候使用红黑树？
对于插入，默认情况下是使用链表节点。当同一个索引位置的节点在新增后达到9个：如果此时数组长度大于等于64，则会出发链表节点转红黑树节点；而如果数组长度小于64，则不会触发链表转红黑树，而是会进行扩容，因此此时的数据量还是比较小。
对于移除，当同一个索引位置的节点在移除后达到6个，并且该索引位置的节点为红黑树节点，会触发红黑树节点转链表节点。
为什么链表转红黑树的阈值是8？
阈值为8是在时间和空间上权衡的结果。红黑树节点大小约为链表节点的2倍，在节点太少时，红黑树的查找性能优势并不明显，付出2倍空间的代价不值得。
理想情况下，使用随机的哈希码，节点分布在 hash 桶中的频率遵循泊松分布，按照泊松分布的公式计算，链表中节点个数为8时的概率为 0.00000006（跟大乐透一等奖差不多，中大乐透？不存在的），这个概率足够低了，并且到8个节点时，红黑树的性能优势也会开始展现出来，因此8是一个较合理的数字。
那为什么转回链表节点是用的6而不是复用8？
如果我们设置节点多于8个转红黑树，少于8个就马上转链表，当节点个数在8徘徊时，就会频繁进行红黑树和链表的转换，造成性能的损耗。
那 HashMap 有哪些重要属性？分别用于做什么的？
除了用来存储我们的节点 table 数组外，HashMap 还有以下几个重要属性：1）size：HashMap 已经存储的节点个数；2）threshold：扩容阈值，当 HashMap 的个数达到该值，触发扩容。3）loadFactor：负载因子，扩容阈值 = 容量 * 负载因子。
threshold 除了用于存放扩容阈值还有其他作用吗？
在我们新建 HashMap 对象时， threshold 还会被用来存初始化时的容量。HashMap 直到我们第一次插入节点时，才会对 table 进行初始化，避免不必要的空间浪费。
HashMap 的默认初始容量是多少？HashMap 的容量有什么限制吗？
默认初始容量是16。HashMap 的容量必须是2的N次方，HashMap 会根据我们传入的容量计算一个大于等于该容量的最小的2的N次方，例如传 9，容量为16。
你说 HashMap 的容量必须是 2 的 N 次方，这是为什么？
当 n 不为 2 的 N 次方时，hash 冲突的概率明显增大。
HashMap 的默认初始容量是 16，为什么是16而不是其他的？
我认为是16的原因主要是：16是2的N次方，并且是一个较合理的大小。如果用8或32，我觉得也是OK的。实际上，我们在新建 HashMap 时，最好是根据自己使用情况设置初始容量，这才是最合理的方案。
为什么负载因子是0.75而不是其他的？
这个也是在时间和空间上权衡的结果。如果值较高，例如1，此时会减少空间开销，但是 hash 冲突的概率会增大，增加查找成本；而如果值较低，例如 0.5 ，此时 hash 冲突会降低，但是有一半的空间会被浪费，所以折衷考虑 0.75 似乎是一个合理的值。
HashMap 的插入流程是怎么样的？
扩容（resize）流程介绍下？
HashMap 是线程安全的吗？
不是。HashMap 在并发下存在数据覆盖、遍历的同时进行修改会抛出 ConcurrentModificationException 异常等问题，JDK 1.8 之前还存在死循环问题。