底层结构? 1.7 1.8 ?
    1.7 数组+链表 1.8 数组 +(链表+红黑树)

    运行原理
    put操作: 为了可以快速查找选择如下方式
    输入的key调用hashcode方法进行第一次运算得到hash值,然后再进行二次hash,接着用二次hash的值与map的容量进行取余操作,计算后的余数作为该字符串在map中的下标,

    为何使用红黑树?
    当链表过长时,会降低查询性能,加入红黑树就可以解决这个问题

    为何不一上来就树化?
    当链表较短时,查询速度要比树来得快,还有一个理由就是内存占用方面,树占用的内存要比链表多,所以没必要一上来就树化

    同一下标下的链表过长,怎么解决?

    • 当插入map的size的四分之三以上的元素时,map会自动扩容,解决链表过长的问题

    何时会树化?

    • 当原始hash码都相同时,扩容就无法解决链表过长的问题了,这时就要树化,前提条件是满足树化的阈值,阈值为8,链表长度大于8,并且容量大于等于64的场合,才会树化,容量不大于64,会继续尝试扩容
    • 红黑树特点: 父节点左边都比父节点本身小,右边都比父节点本身大,比较方式为,先比hash值大小,大小一样比较字符本身大小

    image.png

    索引计算优化?
    优化前提是容量必须为2的n次幂
    正常是用hash值,取余容量,但是也以优化成hash值按位&(容量-1)

    为何二次hash?
    让hash变的更均匀,保证链表高度不会超过阈值,防止超长列表的产生
    image.png

    image.png
    image.png

    image.png

    数据丢失
    处于多线程的模式下,当两个key计算下标相同时,后赋值的key会覆盖掉先赋值的key
    扩容死链

    image.png
    重写hashcode为了有更好的hash分布,重写equals是为了,当两个key计算出的索引都一样 需要进一步用equals比较是否为同一个对象,hashcode相同,equals不一定相同,equals相同,则hashcode一定相同