一、底层数据结构，1.7和1.8有何不同？

    1. 1.7是数组+链表，1.8数组+(链表|红黑树)
    2. 为何要用链表+红黑树？

    image.png
    最初的情况：
    两次hash后，对hashMap长度取余，得到桶下标；
    最坏情况下，查找的时间复杂度是O(n)，而不是O(1)。
    优化(解决冲突)：
    元素个数初始为16 ，如果(元素个数大于hashMap长度的3/4)或(链表长度大于8且数组长度小于64),则先扩容；
    如果链长大于阈值8，且hashMap长度大于64，则会将链表树化。
    树化后的查找时间复杂度为O(ln n)

    1. 红黑树用来避免DoS攻击，防止链表超长时性能下降，树化是偶然情况；

    hash值如果足够随机，则在hash表内按泊松分布，在负载因子为0.75的情况下，树化概率为0.00000006，选择8就是为了让树化几率足够小。

    1. 红黑树何时退化成链表？

    ①退化情况1：在扩容时如果拆分树时，树元素个数<=6时，则会退化为链表；
    ②退化情况2：remove树节点时，若root,root.left,root.right,root.left.left有一个为null时，也会退化为链表。
    二、索引计算
    公式：计算对象的hashCode()，再调用HashMap的hash()方法，最后按位与(长度-1)，得到索引。
    二次哈希：二次扰动能让哈希值分布更均匀，链表长度更小。
    移动位置：扩容时，元素hash按位与oldCap == 0时，元素留在原来位置，否则新位置 = 旧位置 + oldCap
    使用质数作为hashmap长度，可以更均匀分布，但是使用2^n作为长度，可以使用位与运算代替取模，计算元素索引的效率更高。(Java注重性能，所以采用这种方式)
    三、put方法流程

    1. 懒惰创建数组，首次使用才创建，而不是一开始就有；
    2. 计算索引(桶下标)
    3. 如果桶下标没有占用，创建Node，占位返回；
    4. 如果有占用，

    ①如果是TreeNode，走红黑树逻辑；
    ②如果是Node，走链表逻辑，如果超过树化阈值，走树化逻辑。

    1. 返回前检查容量是否超过阈值，一旦超过进行扩容。
    2. 扩容：将元素先加到旧数组里，再迁移到新数组里。
    3. 1.7和1.8区别：

    链表：1.7是头插法，1.8是尾插法；
    扩容：1.7有空位即使达到阈值也不扩容，1.8直接扩容；
    移动位置：1.8会按位与，如果是0不移动，否则移动。
    四、扩容因子为什么默认是0.75f

    1. 在空间占用和查询时间之间取得较好的权衡；
    2. 大于这个值，空间节省了，但链表就会比较长，影响性能；
    3. 小于这个值，冲突减少了，但扩容会更频繁，空间占用多。

    五、多线程下的问题

    1. 并发丢失数据：两个相同桶下标的元素，同时put，会导致丢失其中一个；（1.7和1.8）
    2. 扩容死链：线程T1执行完扩容后，T2的指向形成环，造成死锁（1.7尾插法）

    六、Key能否为null，作为key的对象有什么要求?

    1. HashMap的key可以为null，但Map的其他实现则不然；
    2. key对象，必须实现hashCode和equals，并且key的内容不能修改；

    七、String对象的hashCode()如何设计，为啥每次乘31？
    散列公式：每个字符31^n-1 ，31^n-2 ….

    1. 31的散列效果最好；
    2. 乘法操作可变为移位操作。