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