1 HashMap 结构

• 底层数据结构，1.7 和 1.8有什么不同

  ① 1.7 数组 + 链表， 1.8 数组 +（链表 | 红黑树）

• 为何要用红黑树，为何不一上来用红黑树，红黑树化的阈值为何是 8 ，何时会树化，何时会退化为链表？

 ① 红黑树用来避免Dos攻击，避免链表超长时性能下降，树化应当是偶然情况
  1） hash 表的查找，更新的时间复杂度是O(1)，而红黑树的查找，更新的时间复杂度是O(log₂ⁿ)，TreeNode 占用空间也比普通Noed的大，如非必要，尽量还是使用链表
  2）hash 值如果足够随机，则在hsah表内按泊松分布，在负载因子0.75的情况下，长度超过8的链表出现概率是0.00000006，选择8就是为了让树化几率足够小
 ② 树化两个条件: 链表长度超过树化阈值；数组容量>=64
 ③ 退化情况1：在扩容时如果拆分树时，树元素个数<=6则会退化链表
 ④ 退化情况2：remove 树节点时，若root、root.left、root.right、root.left.left有一个为空null，也会退化为链表

• 索引如果计算？hashCode都有了，为何还要提供hash()方法？数组容量为何是2的n次幂？

 ① 计算对象的hashCode(),再进行调用HashMap的hash()方法进行二次哈希，最后 &(capacity-1) 得到索引
 ② 二次hash()是为了综合高为数据，让哈希分布更为均匀
 ③ 计算索引时，如果是2的n次幂可以使用位与运算代替模式，效率更高；扩容时hash & oldCap == 0的元素留在原来位置，否则新位置 = 旧位置 + oldCap（旧的容量）
 ④ 但 ①、②、③都是为了配合容量为2的n次幂时的优化手段，例如Hashtable的容量就不是2的n次幂，并不能说哪种设计更优，应该是设计者综合了各种因素，最终选择了使用2的n次幂作为容量