拼多多8-3号后端机试记录

put添加元素的流程1 首先会去借助哈希值计算桶索引的值，运算函数为(n-1)&hash值进行与计算。：计算哈希值，jdk7之前是直接引用哈希值计算，而jdk8开始则借助哈希扰动的算法，原理呢就是将原哈希值向右移动16位，异或运算哈希值，将高位哈希值与地位哈希值都可以很好的参与到计算当中，减少哈希冲突的概率2 判断该桶索引位置是否为空，如果为空直接进行存放Node节点。如果不为空，需要遍历链表或者红黑树，去判断是否存在相同的key，如果不同则插入，相同则覆盖。：8开始为尾插，8之前为头插（多线程扩容可能会导致链表出现死循环的问题）插入新节点后3对数组的元素进行计数，当数组当中的元素数量大于负载因子与容量的乘积时，会触发扩容机制，两倍的扩容速度，扩容过程当中存在对元素桶索引的重新分配问题：在jdk7之前会使用(2n-1)&hash重新算一遍桶索引的位置（n为原数组长度）：但是在jdk8开始，将(2n-1)&hash进行拆分，拆成(n-1)&hash+n&hash=原索引位置+n&hash，在判断过程当中呢，实现对n&hash的计算即可，判断计算是否为零，为零则保留原索引，不为零则在原索引的基础之上加上旧数组长度，接着移动就简单了，将原先的链表拆分为两个临时链表，后续直接一次性挂载即可。4判断是否需要树化，先判断链表长度，在链表长度达到8的条件下，判断数组长度是否达到64，达到就将链表树化，没达到64就以2倍的速度进行扩容。