八股
hashmap
定位:首先通过key的哈希值做扰动处理(高低16位进行异或,为了让高位也参与到计算下标中来),接着用哈希值与n-1进行与运算得到数组下标。(当n为2的某整数幂时,哈希值与n取模等价于上面的计算下标的方法,这也是为什么扩容要为2倍,因为可以更方便的计算扩容后新数组下标,当n的最高位为0时扩容后元素位置不变,为1时新位置为旧位置+老数组长度)
扩容:初始容量16,负载因子0.75,扩容后元素位置见上面
冲突:链表长度高于8且数组长度大于64转化为红黑树(小于6时退化成链表),否则优先扩容。
定位:首先通过key的哈希值做扰动处理(高低16位进行异或,为了让高位也参与到计算下标中来),接着用哈希值与n-1进行与运算得到数组下标。(当n为2的某整数幂时,哈希值与n取模等价于上面的计算下标的方法,这也是为什么扩容要为2倍,因为可以更方便的计算扩容后新数组下标,当n的最高位为0时扩容后元素位置不变,为1时新位置为旧位置+老数组长度)
扩容:初始容量16,负载因子0.75,扩容后元素位置见上面
冲突:链表长度高于8且数组长度大于64转化为红黑树(小于6时退化成链表),否则优先扩容。
全部评论
相关推荐