HashMap 原理（数据结构）
底层数据结构：数组+链表+红黑树
● 数组：存取元素时，利用 key 的 hashCode 来计算它在数组中的索引，这样在没有冲突的情况下，能让存取时间复杂度达到 O(1)
● 冲突：数组大小毕竟有限，就算元素的 hashCode 唯一，数组大小是 n 的情况下要放入 n+1 个元素，根据鸽巢原理，肯定会发生冲突
● 解决冲突：一种办法就是利用链表，将这些冲突的元素链起来，当然在在此链表中存取元素，时间复杂度会提高为 O(n)
接下来要能说出为什么在链表的基础上还要有红黑树
● 树化目的是避免链表过长引起的整个 HashMap 性能下降，红黑树的时间复杂度是 O(log{n})
有一些细节问题可以继续回答，比如树化的时机【进阶】
● 时机：在数组容量达到 >= 64 且 链表长度 >= 8 时，链表会转换成红黑树
● 如果树中节点做了删除，节点少到已经没必要维护树，那么红黑树也会退化为链表
HashMap 原理（扩容）
扩容因子：0.75 也就是 3/4
● 初始容量 16，当放入第 13 个元素时（超过 3/4）时会进行扩容
● 每次扩容，容量翻倍
● 扩容后，会重新计算 key 对应的桶下标（即数组索引）这样，一部分 key 会移动到其它桶中
HashMap 原理（方法执行流程）
以 put 方法为例进行说明
- 产生 hash 码。
a. 先调用 key.hashCode() 方法
b. 为了让哈希分布更均匀，还要对它返回结果进行二次哈希，这个结果称为 hash
c. 二次哈希就是把 hashCode 的高 16 位与低 16 位做了个异或运算 - 搞定数组。
a. 如果数组还不存在，会创建默认容量为 16 的数组，容量称为 n
b. 否则使用已有数组 - 计算桶下标。
a. 利用 (n - 1) & hash 得到 key 对应的桶下标（即数组索引）
b. 也可以用 hash % n 来计算，但效率比前面的方法低，且有负数问题
c. 用 (n - 1) & hash 有前提，就是容量 n 必须是 2 的幂（如 16，32，64 ...） - 计算好桶下标后，分三种情况
a. 如果该桶位置还空着，直接根据键值创建新的 Node 对象放入该位置即可
b. 如果该桶是一条链表，沿着链表找，看看是否有值相同的 key，有走更新，没有走新增
■ 走新增逻辑的话，是把节点链到尾部（尾插法）
■ 新增后还要检查链表是否需要树化，如果是，转成红黑树
■ 新增的最后要检查元素个数 size，如果超过阈值，要走扩容逻辑
c. 如果该桶是一棵红黑树，走红黑树新增和更新逻辑，同样新增的最后要看是否需要扩容
