HashMap2倍扩容,为什么不用hash(key)%length存储,这样就不用必须2倍扩容了啊

Question

HashMap一定2倍扩容,因为存储位置由(length-1)&hash(key)确定,如果用hash(key)%length确定存储,不就不用必须2倍扩容了吗?可以随意扩容,为什么不采用?是因为hash(key)%length性能较(length-1)&hash(key)低?

Answer 1

按位和运算比求余运算快是一方面，还有很重要的一点就是这种扩容方式下对元素的重新分配操作更简单，尤其是在碰撞较多的情况下。原先在oldTab[i]位置的元素在resize后要么在newTab[i]，要么在newTab[i+oldCap],而且只有oldTab[i]上的元素会被分配到这两个位置对节点链表oldTab[i]做rehash时，只需要根据hash&oldCap是否等于0拆分成low、high两个链表，然后直接赋值newTab[i]=low,newTab[i+oldCap]=high即可。如果是随意扩容，rehash时就需要对每个元素做如下操作：算出在新数组中的位置j检查newTab[j]是否为空，如果为空则赋值到newTab[j]，否则用一个循环结构找到newTab[j]链表的末尾，将元素添加到链表末尾。*oldCap为扩容前数组大小*从java8开始,碰撞的元素还可能是以树的形式存储，处理方式略有差异